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 probability that he will make it to the end of the bridge before the beginning ?
What is the expected number of steps he takes to reach either the beginning or the end of the bridge?
Solution:
Part 1). This is a martingale and that $E[S_n] = 0 = p_a * 83 + (1-p_a)*(-17) =0. \rightarrow p_a =0.17$.
Part 2). 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] =0. \rightarrow E[N] = 1441$.
Confusion.
I don't understand how come you can treat $N$ as a constant. Shouldn't $N$ also be a random variable since you don't know the number of steps to get to the beginning or the end of the bridge? Also, how come $E[S^2_N - N] =0$? Is it because that $E[S^2_N - N] = E[S^2_N]-E[N] = Var(S_N)-N$. And because $Var(S_n) = n$, thus, you have $E[S^2_N]-E[N] = N- N = 0$?
I would build intuition for this with Markov chains in matrices.
You can consider the smaller example of 6 "stepped" track:
$${\bf P} = \frac{1}{2}\left[\begin{array}{cccccc}2&1&0&0&0&0\\0&0&1&0&0&0\\0&1&0&1&0&0\\0&0&1&0&1&0\\0&0&0&1&0&0\\0&0&0&0&1&2\end{array}\right]$$
You can then by checking eigenvectors for ${\bf P}^T$ for $\lambda=1$. They are both linear functions $$\text{eigenvectors , }\lambda = 1\cases{[0\,1\,2\,3\,4\,5]^T\\ [5\,4\,3\,2\,1\,0]^T}$$
The second part of the question the estimated value is just the product $[1,0,0,0,0,1]{\bf T}{\bf v}$ where $\bf v$ is drunkard probability distribution ${\bf P}_m$ is P but removed endpoints $({\bf P_m})_{11} = 0, ({\bf P_m})_{66} = 0$
$${\bf T} = \sum_k (k-1){{\bf P}_m}^k$$