computationalphysics

final :random system

abstract

• random walks
• self-avoiding walks
• random walks and diffusion
• diffusion, entropy，and the arrow of time
• cluster growth models : Eden model and DLA(diffusion-limited aggregation)

mainbody

• code for random walks
• code for self-avoiding random walks
• code for random walks and diffusion （$\frac{D\Delta t}{(\Delta x)^2}=0.5$）
• code for diffusion and entropy
• code for DLA cluster
  

  ---

1.random walks

random walk is a mathematical object which describes a path that consists of a succession of random steps. For example, the path traced by a molecule as it travels in a liquid or a gas, the search path of a foraging animal, superstring behavior, the price of a fluctuating stock and the financial status of a gambler can all be approximated by random walk models, even though they may not be truly random in reality. As illustrated by those examples, random walks have applications to many scientific fields including ecology, psychology, computer science, physics, chemistry, and biology, and also to economics. Random walks explain the observed behaviors of many processes in these fields, and thus serve as a fundamental model for the recorded stochastic activity. As a more mathematical application, the value of pi can be approximated by the usage of random walk in agent-based modelling environment. The term random walk was first introduced by Karl Pearson in 1905.
Various types of random walks are of interest, which can differ in several ways. The term itself most often refers to a special category of Markov chains or Markov processes, but many time-dependent processes are referred to as random walks, with a modifier indicating their specific properties. Random walks (Markov or not) can also take place on a variety of spaces: commonly studied ones include graphs, others on the integers or the real line, in the plane or in higher-dimensional vector spaces, on curved surfaces or higher-dimensional Riemannian manifolds, and also on groups finite, finitely generated or Lie. The time parameter can also be manipulated. In the simplest context the walk is in discrete time, that is a sequence of random variables $(X_t) = (X1, X2,...)$ indexed by the natural numbers. However, it is also possible to define random walks which take their steps at random times, and in that case the position $X_t$ has to be defined for all times t ∈ [0,+∞). Specific cases or limits of random walks include the Lévy flight and diffusion models such as Brownian motion.
Random walks are a fundamental topic in discussions of Markov processes. Their mathematical study has been extensive. Several properties, including dispersal distributions, first-passage or hitting times, encounter rates, recurrence or transience, have been introduced to quantify their behaviour.

• random walk with a specific step-length
  
• random walk with a random step-length
  
  

  ---

2. self-avoiding walks

In mathematics, a self-avoiding walk (SAW) is a sequence of moves on a lattice (a lattice path) that does not visit the same point more than once. This is a special case of the graph theoretical notion of a path. A self-avoiding polygon (SAP) is a closed self-avoiding walk on a lattice. SAWs were first introduced by the chemist Paul Flory[dubious – discuss] in order to model the real-life behavior of chain-like entities such as solvents and polymers, whose physical volume prohibits multiple occupation of the same spatial point. Very little is known rigorously about the self-avoiding walk from a mathematical perspective, although physicists have provided numerous conjectures that are believed to be true and are strongly supported by numerical simulations.
In computational physics a self-avoiding walk is a chain-like path in $R^2$ or $R^3$ with a certain number of nodes, typically a fixed step length and has the imperative property that it doesn't cross itself or another walk. A system of self-avoiding walks satisfies the so-called excluded volume condition. In higher dimensions, the self-avoiding walk is believed to behave much like the ordinary random walk. SAWs and SAPs play a central role in the modelling of the topological and knot-theoretic behaviour of thread- and loop-like molecules such as proteins. SAW is a fractal. For example, in d = 2 the fractal dimension is 4/3, for d = 3 it is close to 5/3,while for d ≥ 4 the fractal dimension is 2. The dimension is called the upper critical dimension above which excluded volume is negligible. A SAW that does not satisfy the excluded volume condition was recently studied to model explicit surface geometry resulting from expansion of a SAW.

PS:in this simulation programme,self-avoiding just means no-heading-back,which is something different from that in Nicholas J.Giodano's computational physics.This explains why the green-plot is lower than $y=x^{1.5}$ plot.

---

3.random walks and diffusion

As for a individual random walker,$P(i,j,k,n)$ is the probability to find the particle at the site$(i,j,k)$ at time $n$.Since we are on a simple cubic lattice,there are 6different nearest neightbor sites.If the walker is on one of these sites at time $n-1$,there is a probability of 1/6 that it will then move to site$(i,j,,k)$ at time $n$. Hence,the total probability to arrive at $(i,j,k)$ is:

$$P(i,j,k,n)=\frac{1}{6}[P(i+1,j,k,n-1)+P(i-1,j,k,n-1)+\\ P(i,j+1,k,n-1)+P(i,j-1,k,n-1)+P(i,j,k+1,n-1)+P(i,j,k-1,n-1)]$$
Rearranging the equation,and it suggests takking the continuum limit,which lead to $$\frac{\partial P(x,y,z,,t)}{\partial t}=D\nabla^2P(x,y,z,t)$$
where $D=(1/6)(\Delta x)^2/\Delta t$ in this approxiamtion.This derivation shows the close connection between the random walks and diffusion.The density $\rho$ obeys teh same equation: $$\frac{\partial \rho}{\partial t}=D\nabla^2\rho$$
convert this equation above to one dimension and rewrite it in a finite-difference version:
$$\frac{\rho (i,n+1)-\rho (i,n)}{\Delta t}=\frac{\rho (i+1,n)-2\rho (i,n)+\rho(i-1,n)}{\Delta x^2}$$
Rearranging to express teh density at time step $n+1$ in terms of $\rho$ at step $n$,we find:
$$\rho(i,n+1)=\rho(i,n)+\frac{D\Delta t}{(\Delta x)^2}[\rho(i+1,n)+\rho(i-1,n)-2\rho(i,n)]$$ If we aare given the initial distribution of the cream partials,$\rho(x,t=0)$,we can use this equationn to solve for $\rho$ at future times.
In addition,to guarantee numerical stability we must make sure that the space and time steps satisfy $$\Delta t\leq(\Delta x)^2/(2D)$$

The plots above is time evolution claculated from diffusion equation in one dimension.the initial condition is:$\rho(t=0,x=250)=1$ and $\rho(t=0,x\neq250)=0$,It depict that the solution of diffusion is a Gaussian-distribution.

The plots above is time evolution claculated from random walks of 5000 particles in one dimension,the initial condition is all the particles are located at $x=50$,its depict that the distributions of random-walk particles are fluctuations around Gaussian-distribution.

---

4.diffusion, entropy，and the arrow of time

The movement of a single atom, ion, or molecule within a mixture just appears random when viewed in isolation. The movement of a substance within a mixture by “random walk” is governed by the kinetic energy within the system that can be affected by changes in concentration, pressure or temperature.

Now,we are going to simulate a cream-in-your-coffee problem in a numerical way with 'random-walks' algorithm.we also can consider it from the point of view of nonequilibrium statistical mechanics and use to to illustrate how a system approach equlilibrium.

The pictures above are simulation of cream diffusing in coffee.For simplicity we consider a two-dimension cup with an initial square cream distribution,and the collision of particles are ignored.

Here we want to carry this example one step further,and discuss how it related to the second law of thermodynamics and the manner in which systems approach equilibrium.For this it is useful to consider the entropy of the system.Roughly speaking,entropy is a manner of teh amount of disorder.A perfectly ordered system has zero entropy,while a disordered one has a large entropy.furthermore,statistical physics tells us that the entropy of a closed system will either remain the same or increase with time.
my silulation illustrates these ideas very nicely.As time passes the particles spread to fill the cup and their arrangement becomes more disordered.We can make this description quantitatively by calculating the entropy explicitly.To do this we recall the statistical definition of entropy $S$ is :

$$S=-\sum_iP_ilnP_i$$

the plot above is entropy as a function of time for cream mixing in coffee,calculated from the simulation of cream-in-your-coffee.the reason why in this plot $S(t=0)\neq0$ is that in this simulation programme,at t=0 the distribution has already updated for one time.

---

5.cluster growth models : Eden model and DLA(diffusion-limited aggregation)

• Eden model
  The Eden growth model describes the growth of specific types of clusters such as bacterial colonies and deposition of materials. These clusters grow by random accumulation of material on their boundary. These are also an example of a surface fractal. The model is named after Murray Eden.

• DLA cluster

  Diffusion-limited aggregation (DLA) is the process whereby particles undergoing a random walk due to Brownian motion cluster together to form aggregates of such particles. This theory, proposed by T.A. Witten Jr. and L.M. Sander in 1981, is applicable to aggregation in any system where diffusion is the primary means of transport in the system. DLA can be observed in many systems such as electrodeposition, Hele-Shaw flow, mineral deposits, and dielectric breakdown.
  The clusters formed in DLA processes are referred to as Brownian trees. These clusters are an example of a fractal. In 2-D these fractals exhibit a dimension of approximately 1.71 for free particles that are unrestricted by a lattice, however computer simulation of DLA on a lattice will change the fractal dimension slightly for a DLA in the same embedding dimension. Some variations are also observed depending on the geometry of the growth, whether it be from a single point radially outward or from a plane or line for example. Two examples of aggregates generated using a microcomputer by allowing random walkers to adhere to an aggregate (originally (i) a straight line consisting 1300 particles and (ii) one particle at center) are shown on the right.
  A DLA obtained by allowing random walkers to adhere to a straight line. Different colors indicate different arrival time of the random walkers.
  A DLA consisting about 33,000 particles obtained by allowing random walkers to adhere to a seed at the center. Different colors indicate different arrival time of the random walkers.
  Computer simulation of DLA is one of the primary means of studying this model. Several methods are available to accomplish this. Simulations can be done on a lattice of any desired geometry of embedding dimension, in fact this has been done in up to 8 dimensions, or the simulation can be done more along the lines of a standard molecular dynamics simulation where a particle is allowed to freely random walk until it gets within a certain critical range at which time it is pulled onto the cluster. Of critical importance is that the number of particles undergoing Brownian motion in the system is kept very low so that only the diffusive nature of the system is present.

the plots above is a simulation of DLA growth.the rules for DLA clusters are as follows.We start with a seed particle at the origin.We then release a particle at a randomly chosen location$(x,y)$that is some distance away from the seed and let it perform a random walk.If this walker lands on a perimeter site (the unocupied sites taht are nearest neighbors of occupied sites ),it sticks there and becomes part of the cluster.

conclusion

acknowledgement

• Nicholas J.Giodano's computational physics.
• wikipedia-random walk