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}.\)