View source for Bernoulli random walk

A [[Random walk|random walk]] generated by [[Bernoulli trials|Bernoulli trials]]. The example of a Bernoulli random walk may be used to explain certain basic features of more general random walks. In particular, even in this very simple scheme there appear properties of  "randomness"  which are intuitively paradoxical.

Thus, a Bernoulli random walk may be described in the following terms. A particle moves  "randomly"  along the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015660/b0156601.png" />-axis over a lattice of points of the form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015660/b0156602.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015660/b0156603.png" /> is an integer, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015660/b0156604.png" />). The motion begins at the moment <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015660/b0156605.png" />, and the location of the particle is noted only at discrete moments of time <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015660/b0156606.png" />. At each step the value of the coordinate of the particle increases or decreases by a magnitude <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015660/b0156607.png" /> with probabilities <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015660/b0156608.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015660/b0156609.png" />, respectively, irrespective of the nature of the previous motion. Thus, shifts in the positive and in the negative directions ( "successes"  and  "failures" ) are described by a Bernoulli trial scheme with probability of success <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015660/b01566010.png" />. The Bernoulli random walk is usually represented geometrically: take the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015660/b01566011.png" />-axis as the abscissa, and the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015660/b01566012.png" />-axis as the ordinate (cf. Fig. a, showing the initial segment of the graph of a random walk of a particle beginning to move from zero).

<img style="border:1px solid;" src="https://www.encyclopediaofmath.org/legacyimages/common_img/b015660a.gif" />

Figure: b015660a

The initial segment of the graph representing the motion of a particle performing a Bernoulli random walk.

Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015660/b01566013.png" /> be the random variable corresponding to the displacement of the particle in the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015660/b01566014.png" />-th step. Then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015660/b01566015.png" /> is a sequence of independent random variables. The coordinate of the randomly-moving particle at the moment <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015660/b01566016.png" /> is equal to the sum <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015660/b01566017.png" />. This is why the graph of a Bernoulli random walk is an illustrative representation of the behaviour of the cumulative sums of random variables; moreover, many typical features of the fluctuations are preserved for the sums of much more general random variables as well. This graph also shows the changes in the capital at the disposal of one of the players in the classical ruin problem (the formulas giving the probabilities of numerous events taking place in the course of a Bernoulli random walk were in fact developed in connection with this problem).

A Bernoulli random walk is used in physics as a rough description of one-dimensional diffusion processes (cf. [[Diffusion process|Diffusion process]]) and of the [[Brownian motion|Brownian motion]] of material particles under collisions with molecules.

Important facts involved in a Bernoulli random walk will be described below. In so doing, it is assumed that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015660/b01566018.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015660/b01566019.png" />.

Probabilities of returning. Let the walk begin from zero. The probability of at least one return to zero then is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015660/b01566020.png" />, that is, one in the symmetric case <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015660/b01566021.png" />, and less than one if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015660/b01566022.png" />. In the symmetric case the values of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015660/b01566023.png" /> (i.e. the time elapsed until the first return to zero) and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015660/b01566024.png" /> (the time between the first and the second return to zero), etc., are independent random variables with an infinite mathematical expectation. The time elapsed until the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015660/b01566025.png" />-th return, i.e. the sum <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015660/b01566026.png" />, increases as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015660/b01566027.png" />, while the average number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015660/b01566028.png" /> of returns during <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015660/b01566029.png" /> steps is given by the formula

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015660/b01566030.png" /></td> </tr></table>

which increases as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015660/b01566031.png" />:

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015660/b01566032.png" /></td> </tr></table>

The consequence is paradoxical: In a symmetric Bernoulli random walk, the intervals ( "waves" ) between the successive returns to zero on the graph are surprisingly long (Fig. b).

<img style="border:1px solid;" src="https://www.encyclopediaofmath.org/legacyimages/common_img/b015660b.gif" />

Figure: b015660b

Graphs of three Bernoulli random walks: each one was observed during 200,000 units of time.

Another related feature is that the least probable values of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015660/b01566033.png" /> (the fraction of time that the graph is above the abscissa) are those close to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015660/b01566034.png" />. More exactly, the following theorem is valid: If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015660/b01566035.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015660/b01566036.png" />, then the formula

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015660/b01566037.png" /></td> </tr></table>

where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015660/b01566038.png" />, gives the probability <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015660/b01566039.png" /> of the equality <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015660/b01566040.png" />. A corollary is the so-called arcsine law: For each <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015660/b01566041.png" /> the probability of the inequality <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015660/b01566042.png" /> tends to

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015660/b01566043.png" /></td> </tr></table>

It is possible to prove, starting from this fact, that during 10,000 steps the particle remains on the positive side more than 9930 units of time with a probability <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015660/b01566044.png" />, i.e. roughly speaking, such a graph will be observed not less frequently than in one case out of ten (even though this seems absurd at first sight).

Maximum deviation. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015660/b01566045.png" /> or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015660/b01566046.png" />, the randomly-moving particle will move towards <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015660/b01566047.png" /> or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015660/b01566048.png" /> with probability one. Thus, if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015660/b01566049.png" />, one defines the random variable

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015660/b01566050.png" /></td> </tr></table>

and then the probability of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015660/b01566051.png" /> is

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015660/b01566052.png" /></td> </tr></table>

A bounded Bernoulli random walk. One often considers a Bernoulli random walk in the presence of absorbing or reflecting barriers. For instance, let the walk begin from zero. The presence of an absorbing barrier at a point <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015660/b01566053.png" /> is manifested by that, on reaching this point, the particle ceases to move. In the presence of a reflecting barrier at the point <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015660/b01566054.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015660/b01566055.png" /> an integer, the particle will move from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015660/b01566056.png" /> to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015660/b01566057.png" /> with probability <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015660/b01566058.png" />, and will remain in place with probability <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015660/b01566059.png" />. Finite-difference equations are a principal tool in computing the probabilities of the absorption and of attaining specified points. For instance, let the absorbing barrier be located at the point <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015660/b01566060.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015660/b01566061.png" />). If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015660/b01566062.png" /> is the probability of a particle located at <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015660/b01566063.png" /> at the moment of time <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015660/b01566064.png" /> to be absorbed before or at the moment <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015660/b01566065.png" />, then the following equation is valid

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015660/b01566066.png" /></td> </tr></table>

with the following obvious boundary conditions:

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015660/b01566067.png" /></td> </tr></table>

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015660/b01566068.png" /></td> </tr></table>

The solution of this problem for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015660/b01566069.png" /> was known to A. de Moivre and to P. Laplace. The Laplace formula is:

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015660/b01566070.png" /></td> <td valign="top" style="width:5%;text-align:right;">(*)</td></tr></table>

where

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015660/b01566071.png" /></td> </tr></table>

The transition to diffusion processes. As an example, let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015660/b01566072.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015660/b01566073.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015660/b01566074.png" />. Then, as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015660/b01566075.png" />, many probabilities, calculated for a Bernoulli random walk, tend to limits which are equal to the respective probabilities of a Brownian motion. As an example, consider the probability of a particle, which has departed from zero, reaching a barrier located at a point <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015660/b01566076.png" /> before or at the moment <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015660/b01566077.png" />. The limit transition from formula (*), for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015660/b01566078.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015660/b01566079.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015660/b01566080.png" />, gives the magnitude

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015660/b01566081.png" /></td> </tr></table>

which is equal to the probability that the coordinate <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015660/b01566082.png" /> of a particle executing a Brownian motion satisfies the inequality

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015660/b01566083.png" /></td> </tr></table>

i.e. to the probability that the particle is absorbed at the barrier <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015660/b01566084.png" />. For the sake of a more or less complete description of such limit relationships it is expedient to adopt a general standpoint and to consider the transition from the discrete process of  "cumulative sums"  to a continuous random process (cf. [[Limit theorems|Limit theorems]]).

The scheme of a Bernoulli random walk is very useful in explaining the characteristic features of the behaviour of sums of random variables such as the [[Strong law of large numbers|strong law of large numbers]] and the [[Law of the iterated logarithm|law of the iterated logarithm]].

====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top"> W. Feller, [[Feller, "An introduction to probability theory and its  applications"|"An introduction to probability theory and its  applications"]], '''1''', Wiley (1957) pp. Chapt.14</TD></TR></table>