%International Journal of Modern Physics C in LaTex
%--- updated on 11/7/96
%--- revised 3/16/97
\documentstyle[twoside,expsfig]{article}
%--------------------NEW ADDITIONS TO EXISTING ARTICLE.STY---------------------
\catcode`\@=11
\long\def\@makefntext#1{
\protect\noindent \hbox to 3.2pt {\hskip-.9pt
$^{{\eightrm\@thefnmark}}$\hfil}#1\hfill} %CAN BE USED
\def\thefootnote{\fnsymbol{footnote}}
\def\@makefnmark{\hbox to 0pt{$^{\@thefnmark}$\hss}} %ORIGINAL
\def\ps@myheadings{\let\@mkboth\@gobbletwo
\def\@oddhead{\hbox{}
\rightmark\hfil\eightrm\thepage}
\def\@oddfoot{}\def\@evenhead{\eightrm\thepage\hfil
\leftmark\hbox{}}\def\@evenfoot{}
\def\sectionmark##1{}\def\subsectionmark##1{}}
%--------------------START OF IJMPC1.STY---------------------------------------
%THIS STYLE FILE (IJMPC1.STY) IS FOR REFERENCES FROM 1--9 ITEMS ONLY
%THIS STYLE FILE WILL PRODUCE
%$^1$ IN BODY TEXT AND 1. AT REFERENCE SECTION
\oddsidemargin=\evensidemargin
\addtolength{\oddsidemargin}{-30pt}
\addtolength{\evensidemargin}{-30pt}
%------------------------------------------------------------------------------
\newcommand{\symbolfootnote}{\renewcommand{\thefootnote}
{\fnsymbol{footnote}}}
\renewcommand{\thefootnote}{\fnsymbol{footnote}}
\newcommand{\alphfootnote}
{\setcounter{footnote}{0}
\renewcommand{\thefootnote}{\sevenrm\alph{footnote}}}
%------------------------------------------------------------------------------
%NEWLY-DEFINED SECTION COMMANDS
\newcounter{sectionc}\newcounter{subsectionc}\newcounter{subsubsectionc}
\renewcommand{\section}[1] {\vspace{12pt}\addtocounter{sectionc}{1}
\setcounter{subsectionc}{0}\setcounter{subsubsectionc}{0}\noindent
{\tenbf\thesectionc. #1}\par\vspace{5pt}}
\renewcommand{\subsection}[1] {\vspace{12pt}\addtocounter{subsectionc}{1}
\setcounter{subsubsectionc}{0}\noindent
{\bf\thesectionc.\thesubsectionc. {\kern1pt \bfit #1}}\par\vspace{5pt}}
\renewcommand{\subsubsection}[1] {\vspace{12pt}\addtocounter{subsubsectionc}{1}
\noindent{\tenrm\thesectionc.\thesubsectionc.\thesubsubsectionc.
{\kern1pt \tenit #1}}\par\vspace{5pt}}
\newcommand{\nonumsection}[1] {\vspace{12pt}\noindent{\tenbf #1}
\par\vspace{5pt}}
%NEW MACRO TO HANDLE APPENDICES
\newcounter{appendixc}
\newcounter{subappendixc}[appendixc]
\newcounter{subsubappendixc}[subappendixc]
\renewcommand{\thesubappendixc}{\Alph{appendixc}.\arabic{subappendixc}}
\renewcommand{\thesubsubappendixc}
{\Alph{appendixc}.\arabic{subappendixc}.\arabic{subsubappendixc}}
\renewcommand{\appendix}[1] {\vspace{12pt}
\refstepcounter{appendixc}
\setcounter{figure}{0}
\setcounter{table}{0}
\setcounter{lemma}{0}
\setcounter{theorem}{0}
\setcounter{corollary}{0}
\setcounter{definition}{0}
\setcounter{equation}{0}
\renewcommand{\thefigure}{\Alph{appendixc}.\arabic{figure}}
\renewcommand{\thetable}{\Alph{appendixc}.\arabic{table}}
\renewcommand{\theappendixc}{\Alph{appendixc}}
\renewcommand{\thelemma}{\Alph{appendixc}.\arabic{lemma}}
\renewcommand{\thetheorem}{\Alph{appendixc}.\arabic{theorem}}
\renewcommand{\thedefinition}{\Alph{appendixc}.\arabic{definition}}
\renewcommand{\thecorollary}{\Alph{appendixc}.\arabic{corollary}}
\renewcommand{\theequation}{\Alph{appendixc}.\arabic{equation}}
% \noindent{\tenbf Appendix \theappendixc. #1}\par\vspace{5pt}}
\noindent{\tenbf Appendix \theappendixc #1}\par\vspace{5pt}}
\newcommand{\subappendix}[1] {\vspace{12pt}
\refstepcounter{subappendixc}
\noindent{\bf Appendix \thesubappendixc. {\kern1pt \bfit #1}}
\par\vspace{5pt}}
\newcommand{\subsubappendix}[1] {\vspace{12pt}
\refstepcounter{subsubappendixc}
\noindent{\rm Appendix \thesubsubappendixc. {\kern1pt \tenit #1}}
\par\vspace{5pt}}
%------------------------------------------------------------------------------
%FOLLOWING THREE COMMANDS ARE FOR `LIST' COMMAND.
\topsep=0in\parsep=0in\itemsep=0in
\parindent=15pt
%------------------------------------------------------------------------------
\newcommand{\textlineskip}{\baselineskip=13pt}
\newcommand{\smalllineskip}{\baselineskip=10pt}
%------------------------------------------------------------------------------
%MACRO FOR COPYRIGHT BLOCK
\def\eightcirc{
\begin{picture}(0,0)
\put(4.4,1.8){\circle{6.5}}
\end{picture}}
\def\eightcopyright{\eightcirc\kern2.7pt\hbox{\eightrm c}}
\newcommand{\copyrightheading}[1]
{\vspace*{-2.5cm}\smalllineskip{\flushleft
{\footnotesize International Journal of Modern Physics C, #1}\\
{\footnotesize $\eightcopyright$\, World Scientific Publishing
Company}\\
}}
%------------------------------------------------------------------------------
%MACRO FOR PUBLISHER INFORMATION SECTION
\newcommand{\pub}[1]{{\begin{center}\footnotesize\smalllineskip
Received #1\\
\end{center}
}}
\newcommand{\publisher}[2]{{\begin{center}\footnotesize\smalllineskip
Received #1\\
Revised #2
\end{center}
}}
%------------------------------------------------------------------------------
%MARCO FOR ABSTRACT BLOCK
\def\abstracts#1#2#3{{
\centering{\begin{minipage}{4.5in}\baselineskip=10pt\footnotesize
\parindent=0pt #1\par
\parindent=15pt #2\par
\parindent=15pt #3
\end{minipage}}\par}}
%------------------------------------------------------------------------------
%MARCO FOR KEYWORDS BLOCK
\def\keywords#1{{
\centering{\begin{minipage}{4.5in}\baselineskip=10pt\footnotesize
{\footnotesize\it Keywords}\/: #1
\end{minipage}}\par}}
%------------------------------------------------------------------------------
%NEW MACROS FOR BIBLIOGRAPHY
\newcommand{\bibit}{\nineit}
\newcommand{\bibbf}{\ninebf}
\renewenvironment{thebibliography}[1]
{\frenchspacing
\ninerm\baselineskip=11pt
\begin{list}{\arabic{enumi}.}
{\usecounter{enumi}\setlength{\parsep}{0pt}
\setlength{\leftmargin 12.7pt}{\rightmargin 0pt} %FOR 1--9 ITEMS
% \setlength{\leftmargin 17pt}{\rightmargin 0pt} %FOR 10--99 ITEMS
% \setlength{\leftmargin 22pt}{\rightmargin 0pt} %FOR 100+ABOVE ITEMS
\setlength{\itemsep}{0pt} \settowidth
{\labelwidth}{#1.}\sloppy}}{\end{list}}
%------------------------------------------------------------------------------
%LIST ENVIRONMENTS
\newcounter{itemlistc}
\newcounter{romanlistc}
\newcounter{alphlistc}
\newcounter{arabiclistc}
\newenvironment{itemlist}
{\setcounter{itemlistc}{0}
\begin{list}{$\bullet$}
{\usecounter{itemlistc}
\setlength{\parsep}{0pt}
\setlength{\itemsep}{0pt}}}{\end{list}}
\newenvironment{romanlist}
{\setcounter{romanlistc}{0}
\begin{list}{$($\roman{romanlistc}$)$}
{\usecounter{romanlistc}
\setlength{\parsep}{0pt}
\setlength{\itemsep}{0pt}}}{\end{list}}
\newenvironment{alphlist}
{\setcounter{alphlistc}{0}
\begin{list}{$($\alph{alphlistc}$)$}
{\usecounter{alphlistc}
\setlength{\parsep}{0pt}
\setlength{\itemsep}{0pt}}}{\end{list}}
\newenvironment{arabiclist}
{\setcounter{arabiclistc}{0}
\begin{list}{\arabic{arabiclistc}}
{\usecounter{arabiclistc}
\setlength{\parsep}{0pt}
\setlength{\itemsep}{0pt}}}{\end{list}}
%------------------------------------------------------------------------------
%FIGURE CAPTION
\newcommand{\fcaption}[1]{
\refstepcounter{figure}
\setbox\@tempboxa = \hbox{\footnotesize Fig.~\thefigure. #1}
\ifdim \wd\@tempboxa > 5in
{\begin{center}
\parbox{5in}{\footnotesize\smalllineskip Fig.~\thefigure. #1}
\end{center}}
\else
{\begin{center}
{\footnotesize Fig.~\thefigure. #1}
\end{center}}
\fi}
%TABLE CAPTION
\newcommand{\tcaption}[1]{
\refstepcounter{table}
\setbox\@tempboxa = \hbox{\footnotesize Table~\thetable. #1}
\ifdim \wd\@tempboxa > 5in
{\begin{center}
\parbox{5in}{\footnotesize\smalllineskip Table~\thetable. #1}
\end{center}}
\else
{\begin{center}
{\footnotesize Table~\thetable. #1}
\end{center}}
\fi}
%------------------------------------------------------------------------------
%MACROS FOR SETTING \cite{x} OR \citeup{x}
\def\@citex[#1]#2{\if@filesw\immediate\write\@auxout
{\string\citation{#2}}\fi
\def\@citea{}\@cite{\@for\@citeb:=#2\do
{\@citea\def\@citea{,}\@ifundefined
{b@\@citeb}{{\bf ?}\@warning
{Citation `\@citeb' on page \thepage \space undefined}}
{\csname b@\@citeb\endcsname}}}{#1}}
\newif\if@cghi
\def\cite{\@cghitrue\@ifnextchar [{\@tempswatrue
\@citex}{\@tempswafalse\@citex[]}}
\def\citelow{\@cghifalse\@ifnextchar [{\@tempswatrue
\@citex}{\@tempswafalse\@citex[]}}
\def\@cite#1#2{{$\null^{#1}$\if@tempswa\typeout
{IJCGA warning: optional citation argument
ignored: `#2'} \fi}}
\newcommand{\citeup}{\cite}
%------------------------------------------------------------------------------
%FOR SUB/SUPERSCRIPT BOLDFACED + ITALICS
\def\pmb#1{\setbox0=\hbox{#1}
\kern-.025em\copy0\kern-\wd0
\kern.05em\copy0\kern-\wd0
\kern-.025em\raise.0433em\box0}
\def\mbi#1{{\pmb{\mbox{\scriptsize ${#1}$}}}}
\def\mbr#1{{\pmb{\mbox{\scriptsize{#1}}}}}
%------------------------------------------------------------------------------
%FOR FNSYMBOL FOOTNOTE AND ALPH{FOOTNOTE}
\def\fnm#1{$^{\mbox{\scriptsize #1}}$}
\def\fnt#1#2{\footnotetext{\kern-.3em
{$^{\mbox{\scriptsize #1}}$}{#2}}}
%------------------------------------------------------------------------------
%FOR CREATING THE OPENING PAGE NUMBER
\def\fpage#1{\begingroup
\voffset=.3in
\thispagestyle{empty}\begin{table}[b]\centerline{\footnotesize #1}
\end{table}\endgroup}
%------------------------------------------------------------------------------
%MACRO FOR RUNNINGHEAD
\def\runninghead#1#2{\pagestyle{myheadings}
\markboth{{\protect\footnotesize\it{\quad #1}}\hfill}
{\hfill{\protect\footnotesize\it{#2\quad}}}}
\headsep=15pt
%------------------------------------------------------------------------------
\font\tenrm=cmr10
\font\tenit=cmti10
\font\tenbf=cmbx10
\font\bfit=cmbxti10 at 10pt
\font\ninerm=cmr9
\font\nineit=cmti9
\font\ninebf=cmbx9
\font\eightrm=cmr8
\font\eightit=cmti8
\font\eightbf=cmbx8
\font\sevenrm=cmr7
\font\fiverm=cmr5
%------------------------------------------------------------------------------
\newtheorem{theorem}{\indent Theorem}
%OR \newtheorem{theorem}{Theorem}[sectionc] WHICH HAS SECTION NUMBER
\newtheorem{lemma}{Lemma}
%OR USE \newtheorem{lemma}{Lemma}[sectionc]
\newtheorem{definition}{Definition}
\newtheorem{corollary}{Corollary}
%USERS CAN ADD ON THEIR OWN NEW THEOREM-LIKE ENVIRONMENTS.
\newcommand{\proof}[1]{{\tenbf Proof.} #1 $\Box$.}
%--------------------END OF IJMPC1.STY-----------------------------------------
%--------------------START OF DATA FILE----------------------------------------
\textwidth=5truein
\textheight=7.8truein
%------------------------------------------------------------------------------
%DEFINITIONS
\def\qed{\hbox{${\vcenter{\vbox{ %HOLLOW SQUARE
\hrule height 0.4pt\hbox{\vrule width 0.4pt height 6pt
\kern5pt\vrule width 0.4pt}\hrule height 0.4pt}}}$}}
\renewcommand{\thefootnote}{\fnsymbol{footnote}} %USE SYMBOLIC FOOTNOTE
\def\bsc{{\sc a\kern-6.4pt\sc a\kern-6.4pt\sc a}} %LATEX LOGO
\def\bflatex{\bf L\kern-.30em\raise.3ex\hbox{\bsc}\kern-.14em
T\kern-.1667em\lower.7ex\hbox{E}\kern-.125em X}
%------------------------------------------------------------------------------
\begin{document}
\runninghead{Anomalies in Simulations of Nearest Neighbor Ballistic
Deposition}{Anomalies in Simulations of Nearest Neighbor Ballistic
Deposition}
\normalsize\textlineskip
\thispagestyle{empty}
\setcounter{page}{1}
\copyrightheading{} %{Vol. 0, No. 0 (1993) 000--000}
\vspace*{0.88truein}
\fpage{1}
\centerline{\bf ANOMALIES IN SIMULATIONS}
\vspace*{0.035truein}
\centerline{\bf OF NEAREST NEIGHBOR BALLISTIC DEPOSITION}
\vspace*{0.37truein}
\centerline{\footnotesize Raissa M. D'Souza}
\vspace*{0.015truein}
\centerline{\footnotesize\it Department of Physics, and Lab for
Computer Science, MIT}
\baselineskip=10pt
\centerline{\footnotesize\it Cambridge, MA, 02139,
U.S.A.}
\baselineskip=10pt
\centerline{\footnotesize\it E-mail: raissa@mit.edu}
\vspace*{0.225truein}
\publisher{(received date)}{(revised date)}
\vspace*{0.21truein}
\abstracts{
Ballistic Deposition (BD) is a prototypical model for interface
growth and for dynamic scaling behavior in non-equilibrium systems.
BD is typically investigated with computer simulations where
randomness is replaced by use of deterministic Pseudo Random Number
Generators (PRNGs). In this study of BD, several results
discrepant with the prevailing paradigm, were observed.
First, the value of the
roughness exponent, $\chi$, obtained is below the value for a random
walk (i.e. $\chi < 1/2$). The value $\chi = 1/2$
is predicted by the KPZ equation, and many models of
growth obtain this exponent. Second, height fluctuations of the
growing interface appear
not to satisfy simple scaling. Third, a decrease in the surface
roughness is observed in a conjectured steady state regime.
Computer implementations of BD may be responsible for the discrepancies.
A coupling between the BD algorithm and a PRNG algorithm
is identified, and statistically discrepant results are obtained
for an implementation with a different PRNG.
}{}{}
%\vspace*{10pt}
%\keywords{The contents of the keywords}
%\textlineskip %) USE THIS MEASUREMENT WHEN THERE IS
%\vspace*{12pt} %) NO SECTION HEADING
\vspace*{1pt}\textlineskip %) USE THIS MEASUREMENT WHEN THERE IS
\section{Overview} %) A SECTION HEADING
\vspace*{-0.5pt}
\noindent
Understanding growth patterns, both of
clusters and solidification fronts, has
become an increasingly interesting problem, relevant to
non-equilibrium processes in general.$^{1,2,3}$
Dynamic scaling characterizes many of these processes, and
Ballistic Deposition$^4$ (BD) is a prototypical model for this class
of system, and for interface growth in general. In the BD model
free particles, following ballistic trajectories, encounter the active
growth interface of the substrate at which point they aggregate.
The resulting growth patterns are compact clusters with a rough surface,
which may be an accurate model of thin film growth. The active
growth interface exhibits dynamic scaling behavior.
BD has been investigated for more than a decade and the
findings have defined pathways for countless successive
studies of growth processes.$^{5,6,7}$ However it is disconcerting
that a true consensus has never been reached on the value of the
roughness exponent, $\chi$ (defined in detail below). Several
anomalies were observed in the implementation of BD reported in this
study, namely a growth
surface not described by simple scaling, a roughness exponent below the
theoretically predicted value, and a decrease in the surface roughness
in a conjectured steady state regime.
Coupling to PRNGs is observed, which may resolve the anomalies and
discrepancies in past work, and challenges the implicit assumption that
randomness can be replaced by deterministic Pseudo Random Number
Generators (PRNGs).
The organization of the manuscript is as follows. It begins with a
brief overview of the BD algorithm and of existing theories. The
implementation details and results are then discussed.
Pathological situations which may cause
long crossover times or a change in exponents are
investigated. For example, long range spatial and/or temporal
correlations in the pseudorandom sequence of numbers employed are
sought for, but no evidence of such two-point
correlations is found. Yet a dynamics in the value of the surface
roughness is observed in a conjectured steady state regime, and a
different dynamics is observed for an implementation with a different
PRNG. We thus conclude that the BD model couples
sensitively to, as yet undetermined,
non-randomness of pseudorandom sequences,
even sequences which pass all standard statistical tests.
\section{Review of past work}
The surface configuration for BD is completely described by the height,
$h(x,t)$, along each position, $x$, of an underlying substrate, with
$t$ denoting the time duration of growth. Throughout this paper
growth on a one-dimensional substrate (of length
$L$) is considered, for which exact
theoretical predictions exist. The surface evolves as follows. A
column along the substrate is chosen at random and a particle is added
to the surface of that column at the height:
\begin{equation}
h(x,t'+1) = max[h(x-1,t'),h(x,t')+1,h(x+1,t')].
\end{equation}
(The deposited particle occupies the
highest empty site with one or more occupied nearest neighbor sites.)
Here $t'$ is the number of individual deposition events and is
proportional to $t$ ($t = t'/L$).
Beginning with an initially flat substrate, the width of the active
growth interface, $\xi(L,t)$, increases from zero to an asymptotic
value which depends on the underlying, finite size, length scale, $L$.
A measure of $\xi(L,t)$ is the
standard deviation of the surface heights, $\{h(x,t)\}$,
\begin{equation}
\xi^{2}(L,t) = \frac{1}{L} \sum_{x=1}^{L} (h(x,t) - \overline{h(t)})^{2},
\end{equation}
where $\overline{h(t)}$ is the mean height of the surface at time
$t$.
It was pointed out by Family and Vicsek$^8$ that the scaling forms for
the growth and saturation of the width of the interface can be
described by a scaling ansatz, similar to that applicable to critical
systems;
\begin{equation}
\xi(L,t) = L^{\chi} f(t/ L^{z}),
\end{equation}
where $f(x) \sim x^{\beta}$ for $x \ll 1$
and $f(x) = const$ for $x \gg 1$.
For short times, the width of
the interface should increase as $\xi \sim t^{\beta}$.
In the asymptotic regime the width of
the interface should scale as $\xi \sim L^{\chi}$.
An analytical theory by Kardar, Parisi and Zhang (KPZ)$^{9}$
describes the evolution of fluctuations on growing surfaces
using a symmetry motivated differential equation:
\begin{equation}
\frac{\partial h}{\partial t} = \nu \nabla^{2} h + \frac{\lambda}{2}
(\nabla h)^{2} + \eta({\bf x},t).
\end{equation}
Here, $\nu$ is related to surface relaxations,
$(\lambda/2) (\nabla h)^{2}$
is introduced to account for lateral coarsening,
and $\eta({\bf x},t)$ is white noise.
In one dimension, the values of the scaling exponents can be obtained
exactly from KPZ theory: $\chi=1/2$ and $\beta = 1/3$. Note that
$\xi(L,t) \sim L^{1/2}$ is equivalent to a random walk.
While these exponents agree very well with simulations of several
growth models (e.g. Restricted Solid on Solid (RSOS)$^{10}$, discussed
further in the conclusions), it
is puzzling that the reported values of the roughness
exponent, $\chi$, obtained for the BD model have
all been less than the theoretically predicted value.
Moreover the reported values of
$\chi$ have a substantial range (greater than 15\% of the
lowest value), (for a summary see Table 1).
\begin{table}[htbp]
\tcaption{A table of scaling exponents for two growth models,
BD and RSOS, as determined by selected numerical investigations.
Error bars are included when available.}
\centerline{\footnotesize\smalllineskip
\begin{tabular}{|l|l|l|l|}
\hline
\multicolumn{4}{|c|}{Scaling Exponents from Selected Numerical Simulations}
\\
\hline \hline
{Model}
&{Reference}
&{$\beta$}
&{$\chi$}
\\
\hline \hline
BD & FV85$^{8}$ & $0.30 \pm 0.02$ & $0.42 \pm 0.03$ \\ \cline{2-4}
\ \ & MRSB86$^{11}$ & $0.331 \pm 0.006$ & $0.47$ \\ \cline{2-4}
\ \ & M93$^5$ & $0.33$ & $0.45$ \\ \cline{2-4}
\ \ & HHZ95$^7$ & $0.31$ & not reported \\ \cline{2-4}
\ \ & This study & $0.31 \pm 0.02$ & $\chi_{loc\ }$ $0.42 \pm 0.02$ \\
\ \ & \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ & \ \ & $\chi_{glob}$ $0.455 \pm 0.015$\\ \hline
% \ \ & \ \ & \ \ & \ \ \\
RSOS & KK89$^{10}$ & $0.332 \pm 0.005$ & $0.50$ \\ \hline
% \ \ & \ \ & \ \ & \ \ \\
KPZ Theory & KPZ86$^{9}$ & $1/3$ & $1/2$ \\ \hline
\end{tabular}}
\end{table}
\textheight=7.8truein
\setcounter{footnote}{0}
\renewcommand{\thefootnote}{\alph{footnote}}
\section{Implementation and Results}
\noindent
In this study of BD, initially flat substrates of length
varying from $L=127$ to $L=2047$ are considered. At each
update a pseudo random number (PRN) is generated indicating which
site along the substrate will have the next event. A particle is added
to that column at a height described by Equation 1.
The source for PRNs is a C library subroutine
``random()''$^{12}$, which is a non-linear additive
feedback PRNG, initialized with a 256 bit seed, giving
a repeat period of $2^{64}$ numbers.
The lowest 20 to 24 bits of each returned number were shifted off,
leaving only the highest (and least correlated) bits.
Many PRNGs were investigated before this variant of random() was
chosen, as it performed best in initial tests.
All of the simulations were
carried out on a desktop workstation, with the runs on the shortest
length substrates requiring a few hours, and the runs on the longest, a
few days.
The dynamic scaling exponent, $\beta$, is determined using a plot of
the width of the interface, $\xi(L,t)$, versus the time
into the simulation, for all of the substrate lengths $L$.
Note one unit of time is $L$ particle depositions.
Consistent with previous studies (see Table 1) the results are
$\beta = 0.29 \pm 0.01$ for times $3 \leq t
< 100$, and $\beta = 0.31 \pm 0.02$ for times $100 \leq t
< 2000$. We chose to report the value for the longer times, as the
scaling interval is of greater absolute size.
Determination of the asymptotic
roughness exponent $\chi$ is not as straightforward.
The primary complication is that $\xi \sim L^{\chi}$ only in the regime
where the correlation length has reached the full
system size ($t \gg L^{z}$), which can be computationally prohibitive
for large substrate lengths. The conservative estimate of time for
``relaxation'', $\tau = 10L^{z=\frac{5}{3}}$ is employed (which
exceeds the expected scaling of $z = 3/2$).
This time corresponds to an average surface height
$\bar{h} = 20L^{\frac{5}{3}}$.
Once in this regime, the
local roughness of the surface is investigated
by studying ``windows'' of length $l < L$ (i.e $\xi(l,t)$ for $l < L$).
Finite size effects (imposed by periodic boundary conditions) cause
a rounding of these curves, restricting the scaling
regime to lengths $l < L/2$, where self-affine scaling suggests
$\xi(l,t) \sim l^{\chi }$.
The BD local surface roughness is compared to that of a random walk.
We calculate the expectation value of the local surface roughness of a
random walk over the ensemble of all possible walks of total length $L$:
\begin{equation}
<\xi(l,t)_{rwalk}^{2}> = <\frac{1}{l} \sum_{x=1}^{l} \left(h(x) -
\overline{h_l}\right) ^2>.
\end{equation}
Here $h(x+1)=h(x)+\delta_{x}$, $\delta_x=\pm 1$,
$\sum_{x=1}^{(L-1)} \delta_x = 0$ (which implements periodic boundary
conditions), and the correlations between $\delta_x's$ are assumed uniform.
This yields the scaling relation
\begin{equation}
<\xi(l,t)_{rwalk}^{2}> \sim l\left(1 - \frac{l}{2L}\right),
\end{equation}
for $l, L \gg 1$. The second term in Equation 6 represents a finite
size correction to scaling. Comparison with our results for BD is shown
in Figure 1, where the prefactor for the random walk in
Equation 6 was selected so as to agree with the BD simulations at the
shortest lengths.
The two curves are very distinct; Both appear to exhibit scaling
behavior over more than one decade, however the scaling exponents
differ. If the $\delta_x's$ are
chosen in agreement with the empirically obtained step height
distribution of the BD simulations, no {\em ad hoc}
prefactor is needed and similar results are obtained.
\begin{figure}[htbp]
\hfill\vbox{\psfig{figure=fig1.ps,height=6cm}}\hfill
\fcaption{The width of the growth interface plotted as a function
of increasing window size, for the BD
simulations and a theoretical calculation of a random walk with
periodic boundary conditions.}
\end{figure}
From curves of $\xi(l,t)$
in the asymptotic regime, three distinct scaling behaviors can be
identified. For $3 \leq l < 20$ the relation
$\xi(l,t) \sim l^{\chi_{loc_{0}}}$ is obtained, with $\chi_{loc_{0}} =
0.35 \pm 0.01$. For $30 < l < 400$ the relation
$\xi(l,t) \sim l^{\chi_{loc}}$ is obtained, with $\chi_{loc} = 0.42
\pm 0.02$. Looking only at the longest length from each substrate
the relation $\xi(L,t) \sim L^{\chi_{glob}}$ is obtained, with
$\chi_{glob} = 0.455 \pm 0.015$. The data for all substrate lengths is
shown in Figure 2, along with a comparison to
the equivalent data for a random walk with periodic boundary
conditions. For the random walk, only one scaling relation can
be extracted $\xi(l,t) = l^{1/2}$, for both $l \leq L/2$ and $l = L$.
\begin{figure}[htbp]
\hfill\vbox{\psfig{figure=fig2.ps,height=7cm}}\hfill
\fcaption{The width of the growth interface plotted as a function
of increasing window size for the longest times simulated. The data
from all five substrate lengths are included. Dependent upon the range
of lengths we examine, three apparent scaling exponents may be
obtained, as indicated by the solid lines. The insert is the
corresponding data for a random walk with
periodic boundary conditions.}
\end{figure}
In an attempt to formulate a consistent scaling picture, we collapse
the data from the five different length substrates, using Equation 3
(see Figure 3). For $\xi(L,t)$
collapse is achieved by plotting $\xi(L,t)/L^{\chi_{glob}}$ vs
$t/L^{z}$, with the exponents $\chi_{glob} = 0.45 \pm 0.02$ and
$z = 1.45 \pm 0.03$. For $\xi(l,t)$, with
$l=0.1L$, collapse is achieved by plotting $\xi(l,t)/l^{\chi_{loc}}$
vs $t/l^{z}$, with the exponents $\chi_{loc} = 0.40 \pm 0.02$ and
$z = 1.41 \pm 0.03$.
\begin{figure}[htbp]
\hfill\vbox{\psfig{figure=fig3.ps,height=7cm}}\hfill
\fcaption{The scaling function, $f(\frac{t}{l^{z}})$, determined
for data sampled at $l=0.1L$ and at $l=L$. For the data sampled at
$l=0.1L$ collapse is achieved with the exponents $\chi_{loc} = 0.40
\pm 0.02$ and $z = 1.41 \pm 0.03$. For data sampled at $l=L$ collapse
is achieved with $\chi_{glob} = 0.45 \pm 0.02$ and $z = 1.45 \pm 0.03$}
\end{figure}
Exponents obtained by the collapse are consistent with
those obtained by a linear fit and with those reported in previous
studies (see Table 1). The measurement
of $\chi_{loc}$ agrees with the FV85$^{8}$ measurement of $\chi$. The
measurement of $\chi_{glob}$ is consistent with the M93$^{5}$ and
the MRSB86$^{11}$ measurements of $\chi$.
However, these results are puzzling on three counts. First
$\chi_{loc} \neq \chi_{glob}$ -- the surface is not
self affine. Second, all of the exponents obtained are below the
value predicted by the KPZ theory. Third, the characteristic
identity $\chi + z = 2$ is {\em not} obeyed.
These are not only violations of the KPZ scaling, but
also most of its extensions (e.g. Medina, {\it et al.}$^{13}$).
Thus we are lead to ask, what kind of continuum model could explain a
decrease in the values of the scaling exponents (i.e. a hypo-rough
surface)?
\section{Possible resolutions}
One possibility is that the model suffers from a long crossover regime.
For example the Wolf-Villain model of growth has
a length dependence in the adjacent
step height distribution, which persists for long times
($t \sim 10^{4}$), and long lengths ($L \sim 256$)$^{14}$.
The step height distribution for the
BD model is a well behaved quantity, which reaches a steady state,
length independent, value within the completion of a few monolayers.
With reference to the work on crossover, it has been suggested
that the structure
factor is the only way of accurately determining exponents.$^{15}$
The structure factor is related to the Fourier
transform of the height-height correlation function
\begin{equation}
S({\bf k},t) = <\hat{h}({\bf k},t)\hat{h}({\bf -k},t))>,
\end{equation}
with $\hat{h}({\bf k},t) = L^{-d/2} \sum_{{\bf x}}[h({\bf x},t) -
\overline{h(t)}] e^{i{\bf k \cdot x}}$.
Crossover behavior is manifested by a change in the scaling
exponent of $S({\bf k},t)$ vs ${\bf k}$.
There is no evidence of crossover in $S({\bf k},t)$ for our data,
including the longest lengths and longest times simulated.
The exponent obtained is consistent with $\chi_{glob} = 0.45$.
A second possibility is an intrinsic width correction,$^{16}$ as
introduced by Kertesz and Wolf to the Eden Model. This correction
accounts for voids in the bulk, and allows for a clear scaling regime
to be obtained for the Eden model in 2+1
and 3+1 dimensions.$^{17}$ Introducing such a
correction to our data destroys the scaling regime.
A third possibility is correlated noise. There has been
extensive past theoretical and numerical work into growth models with
positively correlated noise (Medina, {\it et al.}, is the first
study).$^{13,5,7}$
For noise with long-range correlations
in space and/or time, the noise term
in Equation 3 is of the form $<\eta({\bf x},t)> = 0$, with
\begin{equation}
<\eta({\bf k},\omega) \eta({\bf k'},\omega)> = 2D(k,\omega)
\delta^{d-1}({\bf k}+{\bf k'})\delta(\omega + \omega'),
\end{equation}
where the noise spectrum $D(k,\omega)$ has power-law singularities of
the form $D(k,\omega) \sim |{\bf k}|^{-2 \rho} \omega^{-2
\theta}$. For uncorrelated noise, the noise spectrum is a constant.
As shown in the original study,$^{13}$ for spatially correlated
noise (i.e $\rho > 0, \theta = 0$), $\chi$ increases and $z$
decreases, preserving the identity of Galilean invariance, $\chi + z =
2$. An extension to anti-correlated noise (i.e. $(\rho,\theta) < 0$)
may show a decrease in the values of the scaling exponents and a
breaking of that identity.
It is clear that extreme forms of anti-correlated noise will result in
a flat interface; Consider sequential updating of a BD growth
algorithm, this generates a perfectly flat interface at each timestep.
Hence it is reasonable that correlations in the noise may change the
roughness of the surface.
We have conducted extensive tests to identify potential long-range spatial
and/or temporal correlations in the PRNs generated by the function
call random(). The PRNs produced pass every
mathematical and physically motivated test, including
those directly relevant to the growth algorithm.
The Fourier transform of the noise in each column, and along the
columns of the substrate, produce flat, white-noise spectra.
The number of calls to each column are Poisson distributed (as
discussed below). Waiting times between successive
calls to each column are exponentially distributed.
The simulated space was divided into checkerboard
sublattices, but no discrepancy between events on even
or odd numbered sites was found.
The autocorrelation function for every property of the generated
surface tested is a simple decaying exponential.
There is no bias for relevant successive events to be in the same
column or left or right neighboring columns.
Other researchers have recently pointed out some physical
models which manifest the pathologies of certain PRNGs.$^{18}$
The PRNs produced by random() pass even those sensitive tests.
Nonetheless, a systematic decrease in the width of the BD growth
interface is observed in the ``asymptotic'' regime (Figure 4).
For the longer lengths simulated, the decrease occurs even before
the strictly defined asymptotic regime. In order to bound the
decrease outside of statistical error, 200 independent runs on
substrates of lengths $L=127$ and $L=511$ are studied. Note that all
the data reported so far were obtained with 20 independent runs on
each substrate length, and all error bars reported are statistical.
A plot of $\xi(l,t)$ vs $l$, during the four greatest
times, on the $L=127$ substrate, is shown in
Figure 4. As the time increases,
$\xi(l,t)$ decreases systematically. The error bars should be noted;
The value of $\xi(l,t)$ for the longest time
is over four standard errors away from the value for the shortest
time. This effect may be due to anti-correlation in the system
(where system refers to the BD algorithm coupled to the PRNG
algorithm). The effect of anti-correlation in the PRNG on a growth
algorithm is illustrated by a simple Poisson process, the Random
Deposition (RD) model. Implementing RD also serves as a check of the
BD computer code.
\begin{figure}[htbp]
\hfill\vbox{\psfig{figure=fig4.ps,height=7cm}}\hfill
\fcaption{The width of the growth interface versus increasing window
size, plotted for subsequent time steps into the
BD simulation. It can be seen that as time increases, the width of the
interface decreases systematically. The inset plot is the width of
the interface for the largest window size, $l = L$, plotted with increasing
time. Note the error bars included on all points.}
\end{figure}
In the RD model the site filled by deposition is the next
available height in the active column (not even nearest
neighbor interactions exist). No boundary conditions are needed
and hence there is no dependence on $L$.
The surface height values should theoretically be Poisson distributed:
($\xi \sim t^{1/2}$, for all $t$). Figure 5 is of $\xi(t)$ vs $t$ for
an RD algorithm implemented by altering only one line of our
BD code (that line describing Equation 1).
Two different PRNGs were used: random() (described earlier),
and rand(), a 16 bit version of the standard C-library
subroutine.$^{19}$ At the close of one repeat cycle, rand() has
sampled all numbers evenly, yielding a flat surface for RD.
The results using random() agree with theory
out to the longest times simulated, yet a systematic decrease is
observed using rand(), as it is for the BD model using random().
As mentioned, the repeat period of random() is on the
order of $10^{19}$, almost ten orders of magnitude greater than the
total number of calls made to it.
\begin{figure}[htbp]
\hfill\vbox{\psfig{figure=fig5.ps,height=6cm}}\hfill
\fcaption{The width of the growth interface versus the
number of function calls for simulations of RD
using two different PRNGs. The solid line
corresponds to the result for ideal random numbers, $\xi \propto
t^{1/2}$. The cycle length of rand() is apparent since the
interface width decreases to zero at the end of a cycle.}
\end{figure}
To quantify that the decrease of the surface roughness is a result of
evolving the system with random() the full BD simulations were run,
using the identical code, but a different PRNG, ran2()$^{20}$ (which
combines two distinct types of PRNGs in an attempt to eliminate
correlations inherent to each one separately). The systematic decrease
was not observed, but several unsystematic fluctuations in the value
of $\xi(l,t)$, outside of statistical error bounds, were
observed. Selecting individual time samples for each length
substrate, it is possible to construct a
scaling curve, with the scaling exponents $\chi_{loc}
= 0.45 \pm 0.01$, and $\chi_{glob} = 0.51 \pm 0.02$.
Note that these are statistical error bounds, which do not address the
issue of fluctuations. Constructing the curve with statistical
outliers, changes the values of the exponents. We do not assert that
these exponents are the ``true exponents'', but instead wish to
focus on the fact that different PRNGs yield different results for an
identical system, implemented with the identical code.
As such, the more revealing comparison is between average values
obtained by the two different PRNGs. For example, the average
asymptotic values of $\xi(L,t)$ differ by more than three
standard errors. A ``t-test''
comparing these average values fails at the $99\%$ confidence
level$^{21}$. Statistically discrepant results for average values and
a statistically distinct dynamics for the interface width fluctuations
show a breakdown of basic sampling assumptions, and moreover, that the
observed dynamics is not inherent to the BD model. Assuming the
dynamics does not reside in the PRNGs, it must reside in a coupling
between the BD and PRNG algorithms. This is in line with the
observation that the short time scaling exponent ($\beta$) is not
effected, but the asymptotic scaling exponent ($\chi$) is;
The effects of coupling may take some time accumulate.
A detailed statistical analysis quantifying the breakdown of sampling
assumptions and ergodic exploration of phase space is reported
elsewhere.$^{22}$
\section{Discussion and Conclusions}
\noindent
It is reasonable that the BD algorithm is more sensitive to
correlations in PRNs than standard Monte Carlo (MC) algorithms.
In standard MC, comparison to the Boltzmann probability causes
rejection of some PRNs produced. In BD, all PRNs are used (in the
sequence produced). It should be noted that in restricted models of
growth (where physical constraints cause rejection of PRNs),
such as RSOS, the theoretically predicted scaling exponents are
recovered with great precision in numerical simulations.
It may be interesting to implement the BD algorithm with random
rejection of PRNs. In addition, we have been considering the use of
massive physical simulations (run on a special purpose cellular
automata machine$^{23}$) which have a vast amount of initial state,
as a source of randomness.
BD is a sensitive physical test for correlations present
in pseudorandom sequences, and it would be desirable to identify the
exact nature of the correlations detected.
Discrepancies in the reported values for the roughness exponent $\chi$,
and anomalies found in this study, may be attributed to distinct
couplings between the BD and the PRNG algorithms.
Disagreement in results generated by two different PRNGs is
strong evidence for this and, more importantly, shows the
dynamics observed in the asymptotic regime are not inherent to the BD
model itself. Results from previous studies of BD have not indicated
which PRNG was used, in addition many of these past simulations
utilized power of two substrate lengths ($L = 2^{n}$),
a system size for which PRNGs manifest their greatest
pathologies.$^{24}$
As of yet we are not able to identify the universality class of the
BD model. A non-self affine growth surface may be due to unidentified
crossover behavior, but it appears that coupling to the
PRNG algorithms becomes dominant before the steady state regime is
achieved.
\nonumsection{Acknowledgements}
\noindent
The author would like to thank Y. Bar-Yam, M. Kardar, and M. Smith for
countless, helpful discussions. This work was supported by NSF
grants, numbers DMR-93-03667 and DMS-95-96217, and by DARPA
contract number DABT63-95-C-0130.
\nonumsection{References}
\begin{thebibliography}{000}
\bibitem{1}
F. Family and T. Vicsek, {\bibit Dynamics of Fractal Surfaces}
(World Scientific, Singapore, 1991).
\bibitem{2}
A. Barabasi and U. E. Stanley, {\bibit Fractal Concepts in Surface Growth}
(Press Syndicate of the Univ of Cambridge, New York, 1995).
\bibitem{3}
C. Godr\`{e}che, (ed.) {\bibit Solids Far From Equilibrium}
(Cambridge University Press, Cambridge, 1992).
\bibitem{4}
M. J. Vold, {\bibit Jour. Colloid Sci.} {\bibbf 14}, 168 (1959).
\bibitem{5}
P. Meakin, {\bibit Physics Reports} {\bibbf 235}, 189 (1993).
\bibitem{6}
J. Villain, {\bibit Journal de Physique I} {\bibbf 1}, 19 (1991).
\bibitem{7}
T. Halpin-Healy and Y. Zhang, {\bibit Physics Reports}
{\bibbf 254(4-6)}, 215 (1995).
\bibitem{8}
F. Family and T. Vicsek, {\bibit Jour. of Phys. A} {\bibbf 18},
L75 (1985).
\bibitem{9}
M. Kardar, G. Parisi, and Y. Zhang, {\bibit Phys. Rev. Let.}
{\bibbf 56(9)}, 889 (1986).
\bibitem{10}
J. Kim and J. Kosterlitz, {\bibit Phys. Rev. Let.} {\bibbf 62(19)},
2289 (1989).
\bibitem{11}
P. Meakin, P. Ramanlal, L. Sander, and R. Ball, {\bibit Phys. Rev. A}
{\bibbf 34(4)}, 5103 (1986).
\bibitem{12}
{\bibit GNU C Library, Sun Release 4.1}
(Original code is copyright Regents of the University of California, 1983).
\bibitem{13}
E. Medina, T. Hwa, M. Kardar, and Y. Zhang, {\bibit Phys. Rev. A}
{\bibbf 39(6)}, 3053 (1989).
\bibitem{14}
M. Schroeder, J. Shore, M. Siegert, D. Wolf, and M. Plischke,
% M. Schroeder, {\bibit et al.},
{\bibit Europhys. Lett.} {\bibbf 24(7)}, 563 (1993).
\bibitem{15}
M. Siegert, {\bibit Phys. Rev. E} {\bibbf 53(4)}, 3209 (1996).
\bibitem{16}
J.G. Zabolitzky and D. Stauffer, {\bibit Phys. Rev. A} {\bibbf 34(2)},
1523 (1986).
\bibitem{17}
J. Kertesz and D. Wolf, {\bibit J. Phys. A} {\bibbf 21}, 747 (1988).
\bibitem{18}
I. Vattulainen, T. Ala-Nissila, and K. Kankaala, {\bibit Phys. Rev. Let.}
{\bibbf 73}, 2513 (1994).
\bibitem{19}
{\bibit GNU C Library, Sun Release 4.1}
\bibitem{20}
W.H. Press {\em etal.}, {\bibit Numerical Recipes in C: the art of
scientific computation, 2nd ed.} (Cambridge University Press, 1992).
\bibitem{21}
W. Feller, {\bibit Introduction to Probability and Statistics} (John
Wiley \& Sons, Inc., New York, 1979).
\bibitem{22}
R.M. D'Souza, Y. Bar-Yam, and M. Kardar, {\bibit Manuscript in
progress}.
\bibitem{23}
N. Margolus, in A. Lawniczak, and R. Kapral, (eds.)
{\bibit Pattern Formation and Lattice-Gas Automata}
(American Mathematical Society, 1994).
\bibitem{24}
D. E. Knuth, {\bibit The Art of Computer Programming}
(Addison-Wesley, Reading, 1973).
\end{thebibliography}
\end{document}