# 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

1.  $$E( X_{n+1} | X_{n})$$?
2.  $$E( X_{n+1})$$?
3.  $$\text{Var}( X_{n+1} | X_{n})$$?
4. $$\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:

1. $$P(G=n)$$ for $$n=2,3,\dots$$
2. $$\mathbf{E}(G)$$
3. $$\mathrm{Var}(G)$$

[Pittman p220, #18]

## Hitting Zero

Consider a random walk making $$2n$$ steps, and let $$T$$ be the first
$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

1. $$\mathbf{E}\Big( |S_{2k}| \ \Big|\ |S_{2k−1}| = r\Big) = r$$;
2. $$\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}.$$