A drunk man is at the 17th meter of a 100-meter-long bridge. He has 0.5 probability of moving forward or backward one meter each step.
What is the expected number of steps he takes to reach either the beginning or the end of the bridge?
Solution:
The martingale stops at $n$ is also a martingale. Let $N =$ stop time.
$E[S^2_N – N] = E[p_a *83^2 + (1-p_a )* 17^2]-E[N] = S_0^2-0 = 0. \rightarrow E[N] = 1441$.
Confusion: I understand $E[Martingale] = E[M_0]$, but how come $E[S_N^2 – N] =0?$
Best Answer
Since your main confusion seems to be over $E(S_n^2-n) = 0$ for any $n$, I will give an explanation for you. We start by rewriting $S_n^2$, namely
$$S_n^2 = \left(\sum_{i=1}^nX_i\right)^2 = \sum_{i=1}^nX_i^2 + \sum_{i\neq j}X_iX_j,$$ thus we can rewrite the expectation by
\begin{align}E(S_n^2-n) &= E\left(\sum_{i=1}^nX_i^2\right) + E\left(\sum_{i\neq j}X_iX_j\right) - E(n)\\ &= \sum_{i=1}^nE\left(X_i^2\right) + \sum_{i\neq j}E\left(X_iX_j\right) - n.\end{align}
Now, we note by independence of the steps that $X_i \perp X_j, i \neq j$, hence $E(X_iX_j) = E(X_i)E(X_j) = 0$. And, because $X_i \in \{-1,1\}$, we have that $X_i^2 = 1$, thus we get that
\begin{align}E(S_n^2-n) &= \sum_{i=1}^nE\left(X_i^2\right) + \sum_{i\neq j}E\left(X_iX_j\right) - n\\ &=\sum_{i=1}^n1 + \sum_{i\neq j}0 - n = n-n = 0. \end{align}
EDIT:
Now, consider a random $N$ with $P(N=n) = p_n, n \in \mathbb{N}$. There are two easy ways of seeing that this result extends from $n \in \mathbb{N}$ to $N$.
Method 1:
We have that $E(S_N^2-N | N = n) = E(S^2_n - n) = 0$ by above. Therefore, $$E(S_N^2 - N) = \sum_{i=1}^\infty E(S_N^2-N | N = n) p_n = \sum_{i=1}^\infty0\cdot p_n = 0.$$
Method 2:
By the same expansion as before, we have that $$E(S_N^2-N) = \sum_{i=1}^NE\left(X_i^2\right) + \sum_{i\neq j}E\left(X_iX_j\right) - E(N),$$ but by Wald's equation we have that this first sum is simply $E(N)E(X_1^2) = E(N)\cdot 1 = E(N)$, hence the result follows immediately.