Home » Basic probability » Random Walk
Category Archives: Random Walk
Random Walk
Let \(\{Z_1, Z_2, \dots, Z_n,\dots\} \) be a sequence of i.i.d random variables such that
\[ P( Z_k = a ) = \begin{cases} \frac14 & \text{ If } a=1 \\\frac14 & \text{ If } a=0\\\frac12 & \text{ If } a=-1 \end{cases}\]
If \(X_{n+1} = X_n + Z_n\) and \(X_0=1\) what is
- \( E( X_{n+1} | X_{n}) \)?
- \( E( X_{n+1}) \)?
- \( \text{Var}( X_{n+1} | X_{n}) \)?
- \( \text{Var}( X_{n+1} )\)?
Notice that \(X_n\) depends only \(Z_{n-1},Z_{n-2},\dots,Z_1\) and hence \(X_n\) is independent of \(Z_n\) !
Up by two
Suppose two teams play a series of games, each producing a winner and a loser, until one time has won two more games than the other. Let \(G\) be the number of games played until this happens. Assuming your favorite team wins each game with probability \(p\), independently of the results of all previous games, find:
- \(P(G=n) \) for \(n=2,3,\dots\)
- \(\mathbf{E}(G)\)
- \(\mathrm{Var}(G)\)
[Pittman p220, #18]
Hitting Zero
Consider a random walk making \(2n\) steps, and let \(T\) be the first
return to its starting point, that is
\[T =\ min\{1 ≤ k ≤ 2n : S_k = 0\},\]
and \(T = 0\) if the walk does not return to zero in the first \(2n steps.
Show that for all \( 1 ≤ k ≤ n\) we have,
\[P(T = 2k) =\frac1{2k − 1} \begin{pmatrix} 2k\\k\end{pmatrix} 2^{-2k}\]
[Meetster Ex 3.3.2]
Expected value of Random Walk
Consider a random walk \(S_i\), which begins at zero, and makes \(2n\) steps.
Let \(k < n\). Show that
- \(\mathbf{E}\Big( |S_{2k}| \ \Big|\ |S_{2k−1}| = r\Big) = r\);
- \( \mathbf{E}\Big(|S_{2k+1}| \ \Big|\ |S_{2k}| = r\Big) = 1 \text{ if } r = 0, \text{ and } \mathbf{E}\Big(|S_{2k+1}| \ \Big|\ |S_{2k}| = r\Big) = r\text{ otherwise}.\)
