Kink movements and percolation in the binary additive cellular automaton

We show that under the Bernoulli initial condition two kinks in the cellular automaton (CA) 18/256 will annihilate each other with probability one. It turns out that there is an equivalent statement in terms of percolation in the simple binary additive CA. Namely, under the Bernoulli initial condition, l's do not percolate in the binary additive CA.     

The dynamics of defect ensembles in one-dimensional cellular automata

We investigate the dynamics of ensembles of diffusive defects in one-dimensional deterministic cellular automata. The work builds on earlier results on individual random walks in cellular automata. Here we give a natural condition guaranteeing diffusive behavior also in the presence of other defects. Simple branching and birth mechanisms are introduced and prototype classes of cellular automata exhibiting weakly interacting walks capable of annihilation and coalescence are studied. Their equilibrium behavior is also characterized. The design principles of cellular automata with desired diffusive interaction properties become transparent from this analysis.     

Transient solution of a random walk with chemical rule

Conolly et al. [Math. Scientist 22 (1997) 83-91] have obtained the transient distribution for a random walk moving on the integers -∞<k<∞ of the real line. Their analysis is based on a generating function technique. In this paper, an alternative technique is used to derive elegant explicit expressions for the transient state distribution of an infinite random walk having “chemical” rule and starting initially at any arbitrary integer position (say i). As a special case of our result, Conolly et al.'s (1997) solution is easily obtained. Moreover, the transient solution of the infinite symmetric continuous random walk is also presented. Finally, numerical values testing the quality of our analytical results are illustrated.     

Random walk in a random medium in one dimension

Applying scaling and universality arguments, the long-time behavior of the probability distribution for a random walk in a one-dimensional random medium satisfying Sinai's constraint is obtained analytically. The convergence to this asymptotic limit and the fluctuations of this distribution are evaluated by solving numerically the stochastic equations for this walk.     

Quantum field as a quantum cellular automaton: The Dirac free evolution in one dimension

We present a quantum cellular automaton model in one space-dimension which has the Dirac equation as emergent. This model, a discrete-time and causal unitary evolution of a lattice of quantum systems, is derived from the assumptions of homogeneity, parity and time-reversal invariance.     

An improved cellular automaton model with the consideration of a multi-point tollbooth

Based on the classical Nagel–Schreckenberg model, we in this paper propose an improved cellular automaton (CA) model to study the influences of a multi-point tollbooth on traffic flow. The numerical results show that the multi-point tollbooth can be looked at as a bottleneck and that it can improve the road capacity compared with other tolling stations, which shows that the proposed model is more effective than other traffic flow models. In addition, the results can help readers to better understand the effects of a multi-point tollbooth on traffic flow and help traffic engineers to reasonably design the tolling station.     

Solution of the persistent, biased random walk

The solution of the one-dimensional persistent, biased random walk is found. Its finite differences equation is derived and shown to be satisfied by the said solution.     

The exact probability distribution of a two-dimensional random walk

A calculation is made of the exact probability distribution of the two-dimensional displacement of a particle at timet that starts at the origin, moves in straight-line paths at constant speed, and changes its direction after exponentially distributed time intervals, where the lengths of the straight-line paths and the turn angles are independent, the angles being uniformly distributed. This random walk is the simplest model for the locomotion of microorganisms on surfaces. Its weak convergence to a Wiener process is also shown.     

Loop-erased self-avoiding random walk in two and three dimensions

If(n) is the position of the self-avoiding random walk in ^d obtained by erasing loops from simple random walk, then it is proved that the mean square displacementE(¦(n)¦²) grows at least as fast as the Flory predictions for the usual SAW, i.e., at least as fast asn ^3/2 ford=2 andn ^6/5 ford=3. In particular, if the mean square displacement of the usual SAW grows liken ^1.18... ind=3, as expected, then the loop-erased process is in a different universality class.     

A myopic random walk on a finite chain

We solve analytically the problem of a biased random walk on a finite chain of ‘sites’ (1,2,…,N) in discrete time, with ‘myopic boundary conditions’—a walker at 1 (orN) at timen moves to 2 (orN − 1) with probability one at time (n + 1). The Markov chain has period two; there is no unique stationary distribution, and the moments of the displacement of the walker oscillate about certain mean values asn → ∞, with amplitudes proportional to 1/N. In the continuous-time limit, the oscillating behaviour of the probability distribution disappears, but the stationary distribution is depleted at the terminal sites owing to the boundary conditions. In the limit of continuous space as well, the problem becomes identical to that of diffusion on a line segment with the standard reflecting boundary conditions. The first passage time problem is also solved, and the differences between the walks with myopic and reflecting boundaries are brought out.     

Directional quantum random walk induced by coherence

Quantum walk (QW), which is considered as the quantum counterpart of the classical random walk (CRW), is actually the quantum extension of CRW from the single-coin interpretation. The sequential unitary evolution engenders correlation between different steps in QW and leads to a non-binomial position distribution. In this paper, we propose an alternative quantum extension of CRW from the ensemble interpretation, named quantum random walk (QRW), where the walker has many unrelated coins, modeled as two-level systems, initially prepared in the same state. We calculate the walker's position distribution in QRW for different initial coin states with the coin operator chosen as Hadamard matrix. In one-dimensional case, the walker's position is the asymmetric binomial distribution. We further demonstrate that in QRW, coherence leads the walker to perform directional movement. For an initially decoherenced coin state, the walker's position distribution is exactly the same as that of CRW. Moreover, we study QRW in 2D lattice, where the coherence plays a more diversified role in the walker's position distribution.     

One-dimensional random walk with self-interaction

A standard random walk on a one-dimensional integer lattice is considered where the probability ofk self-intersections of a path =(0, (1),..., (n) is proportional toe ^–k . It is proven that for <0,n ^–1/3(n) converges to a certain continuous random variable. For >0 the formulas are given for the asymptotic Westerwater velocity of a generic path and for the variance of the fluctuations about the asymptotic motion.     

Environment-dependent continuous time random walk

A generalized continuous time random walk model which is dependent on environmental damping is proposed in which the two key parameters of the usual random walk theory: the jumping distance and the waiting time, are replaced by two new ones: the pulse velocity and the flight time. The anomalous diffusion of a free particle which is characterized by the asymptotical mean square displacement <x²(t)>～t^α is realized numerically and analysed theoretically, where the value of the power index α is in a region of 0 < α < 2. Particularly, the damping leads to a sub-diffusion when the impact velocities are drawn from a Gaussian density function and the super-diffusive effect is related to statistical extremes, which are called rare-though-dominant events.     

An isotropic cellular automaton for excitable media

We propose a new cellular automaton (CA) model, which reproduces isotropic time-evolution patterns observed in the Belousov-Zhabotinsky reaction. Although several CA models have been proposed exhibiting isotropic patterns of the reaction, most of them need complicated rules and a large number of neighboring cells. Our model can produce isotropic patterns from a simple probabilistic rule among a few (4 or 8) neighboring cells.     

Phase coexistence induced by a defensive reaction in a cellular automaton traffic flow model

Traffic flow modeling is an elusive example for the emergence of complexity in dynamical systems of interacting objects. In this work, we introduce an extension of the Nagel-Schreckenberg (NaSch) model of vehicle traffic flow that takes into account a defensive driver’s reaction. Such a mechanism acts as an additional nearest-neighbor coupling. The defensive reaction dynamical rule consists in reducing the driver’s velocity in response to deceleration of the vehicle immediately in front of it whenever the distance is smaller than a security minimum. This new mechanism, when associated with the random deceleration rule due to fluctuations, considerably reduces the mean velocity by adjusting the distance between the vehicles. It also produces the emergence of bottlenecks along the road on which the velocity is much lower than the road mean velocity. Besides the two standard phases of the NaSch model corresponding to the free flow and jammed flow, the present model also exhibits an intermediate phase on which these two flow regimes coexist, as it indeed occurs in real traffics. These findings are consistent with empirical results as well as with the general three-phase traffic theory.     

Two-state random walk model of lattice diffusion. 1. Self-correlation function

Diffusion with interruptions (arising from localized oscillations, or traps, or mixing between jump diffusion and fluid-like diffusion, etc.) is a very general phenomenon. Its manifestations range from superionic conductance to the behaviour of hydrogen in metals. Based on a continuous-time random walk approach, we present a comprehensive two-state random walk model for the diffusion of a particle on a lattice, incorporating arbitrary holding-time distributions for both localized residence at the sites and inter-site flights, and also the correct first-waiting-time distributions. A synthesis is thus achieved of the two extremes of jump diffusion (zero flight time) and fluid-like diffusion (zero residence time). Various earlier models emerge as special cases of our theory. Among the noteworthy results obtained are: closed-form solutions (ind dimensions, and with arbitrary directional bias) for temporally uncorrelated jump diffusion and for the ‘fluid diffusion’ counterpart; a compact, general formula for the mean square displacement; the effects of a continuous spectrum of time scales in the holding-time distributions, etc. The dynamic mobility and the structure factor for ‘oscillatory diffusion’ are taken up in part 2.     

Towards the bi-directional cellular automaton model with perception ranges

The traditional cellular automaton (CA) model assumes that drivers only receive information from the preceding vehicles, e.g. the brake light information. However, in reality, drivers not only perceive information from downstream but can also get upstream information, e.g. the honk stimulation. The CA model involving traffic information from downstream and upstream is called the bi-directional CA model here. Meanwhile, with the introduction of Connected Vehicle Technologies, the perception range of drivers is expected to significantly increase which can lead to more informed driving behavior. Such an impact cannot be easily modeled by traditional one-directional CA models. In this study, the perception ranges of both the brake light effect and honk stimulation are introduced into the bi-directional CA model. Fundamental diagrams and spatial–temporal diagrams are then analyzed and two methods, i.e. the traffic flow interruption effect and microscopic analysis of time series data, are utilized to distinguish the synchronized traffic flow. Further numerical results illustrate that the perception range and slow-to-start sensitivity threshold are two important factors to reproduce the synchronized flow, and consideration of the honk information and the larger perception range both benefit the stability of traffic flow, which implies the potential significance of the application of Connected Vehicle Technologies.     

Fractal behavior in trapping and reaction: A random walk study

We investigate the trapping of a random walker in fractal structures (Sierpinski gaskets) with randomly distributed traps. The survival probability is determined from the number of distinct sites visited in the trap-free fractals. We show that the short-time behavior and the long-time tails of the survival probability are governed by the spectral dimensiond. We interpolate between these two limits by introducing a scaling law. An extension of the theory, which includes a continuous-time random walk on fractals, is discussed as well as the case of direct trapping. The latter case is shown to be governed by the fractal dimensiond.