The simple random walk process is a minor modification of the Bernoulli trials process. Nonetheless, the process has a number of very interesting properties, and so deserves a section of its own. In some respects, it's a discrete time analogue of the Brownian motion process.
Suppose that \(\bs{U} = (U_1, U_2, \ldots)\) is a sequence of independent random variables, each taking values 1 and \(-1\) with probabilities \(p \in [0, 1]\) and \(1 - p\) respectively. Let \(\bs{X} = (X_0, X_1, X_2, \ldots)\) be the partial sum process associated with \(\bs{U}\), so that \[ X_n = \sum_{i=1}^n U_i, \quad n \in \N \] The sequence \(\bs{X}\) is the simple random walk with parameter \(p\).
We imagine a person or a particle on a horizontal number line, so that at each discrete time step, the walker moves either one unit to the right (with probability \(p\)) or one unit to the left (with probability \(1 - p\)), independently from step to step. The walker could accomplish this by tossing a coin with probability of heads \(p\) at each step, to determine whether to move right or move left. Other types of random walks, and additional properties of this random walk, are studied in the chapter on Markov chains.
The mean and standard deviation, respectively of a step \(U\) are
Let \(I_j = \frac{1}{2}\left(U_j + 1\right)\) for \(j \in \N_+\). Then \(\bs{I} = (I_1, I_2, \ldots)\) is a Bernoulli trials sequence with success parameter \(p\).
Note that \(I_j = 1\) if \(U_j = 1\) and \(I_j = 0\) if \(I_j = -1\).
In terms of the random walker, \(I_j\) is the indicator variable for the event that the \(j\)th step is to the right.
Let \(R_n = \sum_{i=1}^n I_j\) for \(n \in \N\), so that \( \bs{R} = (R_0, R_1, \ldots) \) is the partial sum process associated with \( \bs{I} \). Then
In terms of the walker, \(R_n\) is the number of steps to the right in the first \(n\) steps.
\(X_n\) has probability density function \[ \P(X_n = k) = \binom{n}{(n + k) / 2} p^{(n + k)/2} (1 - p)^{(n-k) / 2}, \quad k \in \{-n, -n + 2, \ldots, n - 2, n\}\]
The mean and variance of \(X_n\) are
Suppose now that \(p =\frac{1}{2}\). In this case, \(\bs{X} = (X_0, X_1, \ldots)\) is called the simple symmetric random walk. The symmetric random walk can be analyzed using some special and clever combinatorial arguments. But first we give the basic results above for this special case.
For each \(n \in \N_+\), the random vector \(\bs{U}_n = (U_1, U_2, \ldots, U_n)\) is uniformly distributed on \(\{-1, 1\}^n\), and therefore \[ \P(\bs{U}_n \in A) = \frac{\#(A)}{2^n}, \quad A \subseteq S \]
\(X_n\) has probability density function \[ \P(X_n = k) = \binom{n}{(n + k) / 2} \frac{1}{2^n}, \quad k \in \{-n, -n + 2, \ldots, n - 2, n\} \]
The mean and variance of \(X_n\) are
In the random walk simulation, select the final position. Vary the number of steps and note the shape and location of the probability density function and the mean\(\pm\)standard deviation bar. For selected values of the parameter, run the simulation 1000 times and compare the empirical density function and moments to the true probability density function and moments.
In the random walk simulation, select the final position and set the number of steps to 50. Run the simulation 1000 times and compute and compare the following:
Open the random walk simulation and the standard Brownian motion simulation and select the final position for each. For the random walk, set the number of steps to 100. Run both simulations and note the similarities in the sample paths and in the distributions.
Consider again the simple, symmetric random walk. Let \(Y_n = \max\{X_0, X_1, \ldots, X_n\}\), the maximum position during the first \(n\) steps. Note that \(Y_n\) takes values in the set \(\{0, 1, \ldots, n\}\). The distribution of \(Y_n\) can be derived from a simple and wonderful idea known as the reflection principle.
Let \(n \in \N\) and \(y \in \{0, 1, \ldots, n\}\).
Note first that \(Y_n \ge y\) if and only if \(X_i = y\) for some \(i \in \{0, 1, \ldots, n\}\). Suppose that \(k \le y \le n\). For each path that satisfies \(Y_n \ge y\) and \(X_n = k\) there is another path that satisfies \(X_n = 2 y - k\). The second path is obtained from the first path by reflecting in the line \(x = y\), after the first path hits \(y\). Since the paths are equally likely, \[ \P(Y_n \ge y, X_n = k) = \P(X_n = 2 y - k), \quad k \le y \le n \] Hence it follows that \[ \P(Y_n = y, X_n = k) = \P(X_n = 2 y - k) - \P[X_n = 2 (y + 1) - k], \quad k \le y \le n \] The result now follows by summing over \(k\). Note that the sum of the terms on the right is a collapsing sum.
In the random walk simulation, select the maximum value variable. Vary the number of steps and note the shape and location of the probability density function and the mean/standard deviation bar. Now set the number of steps to 30 and run the simulation 1000 times. Compare the relative frequency function and empirical moments to the true probability density function and moments.
For every \(n\), the probability density function of \(Y_n\) is decreasing.
The last result is a bit surprising; in particular, the single most likely value for the maximum (and hence the mode of the distribution) is 0.
Explicitly compute the probability density function, mean, and standard deviation of \(Y_5\).
Open the random walk simulation and the standard Brownian motion simulation and select the maximum position for each. For the random walk, set the number of steps to 100. Run both simulations and note the similarities in the sample paths and in the distributions.
A fair coin is tossed 10 times. Find the probability that the difference between the number of heads and the number of tails is never greater than 4.
\(\P(Y_{10} \le 4) = 57 / 64\)
Consider again the simple, symmetric random walk. Our next topic is the last visit to 0 during the first \(2 n\) steps: \[ Z_{2 n} = \max \left\{ j \in \{0, 2, \ldots, 2 n\}: X_j = 0 \right\}, \quad n \in \N \] Note that since visits to 0 can only occur at even times, \(Z_{2 n}\) takes the values in the set \(\{0, 2, \ldots, 2 n\}\). This random variable has a strange and interesting distribution known as the discrete arcsine distribution. Along the way to our derivation, we will discover some other interesting results as well.
The probability density function of \(Z_{2 n}\) is \[ \P(Z_{2 n} = 2 k) = \binom{2 k}{k} \binom{2 n - 2 k}{n - k} \frac{1}{2^{2 n}}, \quad k \in \{0, 1, \ldots, n\} \]
Note that \[ \P(Z_{2 n} = 2 k) = \P(X_{2 k} = 0, X_{2 k+1} \ne 0, \ldots, X_{2 n} \ne 0), \quad k \in \{0, 1, \ldots, n\} \] From independence and symmetry it follows that \[ \P(Z_{2 n} = 2 k) = \P(X_{2 k} = 0) \P(X_1 \ne 0, X_2 \ne 0, \ldots, X_{2 n - 2 k} \ne 0), \quad k \in \{0, 1, \ldots, n\} \] We know the first factor on the right from the distribution of \(X_{2 k}\). Thus, we need to compute the second factor, the probability that our random walk never returns to 0 during a time interval. Using results for the maximum position in we have \[ \P(X_1 \le 0, X_2 \le 0, \ldots, X_{2 j} \le 0) = \P(Y_{2 j} = 0) = \ \binom{2 j}{j} \frac{1}{2^{2 j}} \] From symmetry (which is just the reflection principle at \(y = 0\)), it follows that \[ \P(X_1 \ge 0, X_2 \ge 0, \ldots, X_{2 n} \ge 0) = \binom{2 n}{n} \frac{1}{2^{2 n}} \] Next, \(\{X_1 \gt 0, X_2 \gt 0, \ldots, X_{2 j} \gt 0\} = \{X_1 = 1, X_2 \ge 1, \ldots, X_{2 j} \ge 1\}\). From independence and symmetry, \[ \P(X_1 \gt 0, X_2 \gt 0, \ldots, X_{2 j} \gt 0\) = \P(X_1 = 0) \P(X_1 \ge 0, X_2 \ge 0, \ldots, X_{2 j - 1} \ge 0) \] But \(X_{2 j - 1} \ge 0\) implies \(X_{2 j} \ge 0\). Hence \[ \P(X_1 \gt 0, X_2 \gt 0, \ldots, X_{2 j} \gt 0) = \binom{2 j}{j} \frac{1}{2^{2 j + 1}} \] From symmetry, \[ \P(X_1 \ne 0, X_2 \ne 0, \ldots, X_{2 j} \ne 0) = \binom{2 j}{j} \frac{1}{2^{2 j}} \]
The probability density function of \(Z_{2 n}\) is symmetric about \(n\) and is \(u\)-shaped:
In particular, 0 and \(2 n\) are the most likely values and hence are the modes of the distribution. The discrete arcsine distribution is quite surprising. Since we are tossing a fair coin to determine the steps of the walker, you might easily think that the random walk should be positive half of the time and negative half of the time, and that it should return to 0 frequently. But in fact, the arcsine law implies that with probability \(\frac{1}{2}\), there will be no return to 0 during the second half of the walk, from time \(n + 1\) to \(2 n\), regardless of \(n\), and it is not uncommon for the walk to stay positive (or negative) during the entire time from 1 to \(2 n\).
The mean and variance of \(Z_{2 n}\) are
Part (a) follows from symmetry and part (b) by identities for binomial coefficients.
In the random walk simulation, choose the last visit to 0 and then vary the number of steps with the scrollbar. Note the shape and location of the probability density function and the mean \(\pm\) standard deviation bar. For various values of the parameter, run the simulation 1000 times and compare the empirical density function and moments to the true probability density function and moments.
The skewness and kurtosis of \(Z_{2 n}\) are
Part (a) follows from symmetry and part (b) by the standard formulas for kurtosis in terms of the moments: \begin{align*} \E\left(Z_{2 n}^3\right) &= (5 n^3 + 3 n^2) / 2 \\ \E\left(Z_{2 n}^4\right) &= (35 n^4 + 30 n^3 + n^2 - n) / 8 \end{align*}
Explicitly compute the probability density function, mean, variance, skewness, and kurtosis of \(Z_{10}\).
Open the random walk simulation and the standard Brownian motion simulation and select the last zero for each. For the random walk, set the number of steps to 100. Run both simulations and note the similarities in the sample paths and in the distributions.
For \(t \in (0, \infty)\), the time of the last zero in standard Brownian motion on the interval \([0, t]\) has the usual continuous arcsine distribution on the interval \([0, t]\). So the term discrete arcsine distribution is appropriate.
Suppose that in an election, candidate \(A\) receives \(a\) votes and candidate \(B\) receives \(b\) votes where \(a \gt b\). Assuming a random ordering of the votes, what is the probability that \(A\) is always ahead of \(B\) in the vote count? This is an historically famous problem known as the Ballot Problem, that was solved by Joseph Louis Bertrand in 1887. The ballot problem is intimately related to simple random walks.
Comment on the validity of the assumption that the voters are randomly ordered for a real election.
The ballot problem can be solved by using a simple conditional probability argument to obtain a recurrence relation. Let \(f(a, b)\) denote the probability that \(A\) is always ahead of \(B\) in the vote count.
\(f\) satisfies the initial condition \(f(1, 0) = 1\) and the following recurrence relation: \[ f(a, b) = \frac{a}{a + b} f(a - 1,b) + \frac{b}{a + b} f(a, b - 1) \]
This follows by conditioning on the candidate that receives the last vote.
The probability that \(A\) is always ahead in the vote count is \[ f(a, b) = \frac{a - b}{a + b} \]
In the ballot experiment, vary the parameters \(a\) and \(b\) and note the change the ballot probability. For selected values of the parameters, run the experiment 1000 times and compare the relative frequency to the true probability.
In an election for mayor of a small town, Mr. Smith received 4352 votes while Ms. Jones received 7543 votes. Compute the probability that Jones was always ahead of Smith in the vote count.
\(3191 / 11895 \approx 0.2683\)
Consider again the simple random walk in \(\bs{X}\) with parameter \(p\).
Given \(X_n = k\),
For \(k \gt 0\), \[ \P(X_1 \gt 0, X_2 \gt 0, \ldots, X_{n - 1} \gt 0 \mid X_n = k) = \frac{k}{n} \]
In the ballot experiment, vary the parameters \(a\) and \(b\) and note the change the ballot probability. For selected values of the parameters, run the experiment 1000 times and compare the relative frequency to the true probability.
An American roulette wheel has 38 slots; 18 are red, 18 are black, and 2 are green. Fred bet $1 on red, at even stakes, 50 times, winning 22 times and losing 28 times. Find the probability that Fred's net fortune was always negative.
\(3 / 25\)
Roulette is studied in more detail in the chapter on games of chance.
Consider again the simple random walk with parameter \(p\), as in the last subsection. Let \(T\) denote the time of the first return to 0: \[ T = \min\{n \in \N_+: X_n = 0\} \] Note that returns to 0 can only occur at even times; it may also be possible that the random walk never returns to 0. Thus, \(T\) takes values in the set \(\{2, 4, \ldots\} \cup \{\infty\}\).
The probability density funtion of \(T\) is given by \begin{align*} \P(T = 2 n) &= \binom{2 n}{n} \frac{1}{2 n - 1} p^n (1 - p)^n, \quad n \in \N_+ \\ \P(T = \infty) &= |2 p - 1| \end{align*}
For \(n \in \N_+\) \[ \P(T = 2 n) = \P(T = 2 n, X_{2 n} = 0) = \P(T = 2 n \mid X_{2 n} = 0 ) \P(X_{2 n} = 0) \] From the ballot problem, \[ \P(T = 2 n \mid X_{2 n} = 0) = \frac{1}{2 n - 1} \]
So only in the symmetric case (\(p = \frac 1 2\)) does \(T\) have a true (non-defective) distribution on \(\{2, 4, \ldots\}\). However, even in this case \(\E(T) = \infty\).
Fred and Wilma are tossing a fair coin; Fred gets a point for each head and Wilma gets a point for each tail. Find the probability that their scores are equal for the first time after \(n\) tosses, for each \(n \in \{2, 4, 6, 8, 10\}\).
\(f(2) = 1 / 2\), \(f(4) = 1 / 8\), \(f(6) = 1 / 16\), \(f(8) = 5 / 128\), \(f(10) = 7 / 512\)