0

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$?

wrek
  • 485

2 Answers2

1

It's not a constant. It's a random variable. The fact is that $Sn^2 - n $ is also a martingale. So it's expected value is constant and equal to 0.

user436884
  • 11
  • Just wondering. Is it true that the expectation of a martingale is always 0? I am asking expectation, not conditional expectation. – wrek Apr 15 '17 at 00:27
  • @wrek you may find this related Q&A helpful: https://math.stackexchange.com/q/1197194/342780 – David Apr 15 '17 at 09:42
  • An expectation of a Martingale isn't always 0. It depends on the first value S0. – user436884 Apr 15 '17 at 15:27
  • @David, thanks for your reply. I am wondering $M_0$ of your link is the initial value of the martingale,right? – wrek Apr 19 '17 at 21:56
  • @user436884, in this case, the first value $S_0$ is the initial value of the martingale, right? – wrek Apr 19 '17 at 21:56
  • @wrek that's correct – David Apr 19 '17 at 21:57
  • @David, if that's the case, how do I know the initial value of $E[S_n^2 -N]$ of my part b? – wrek Apr 19 '17 at 21:59
  • @wrek what is the definition of $S_n$ in this problem? – David Apr 19 '17 at 22:02
  • $S_n$ is the simple random walk and that $S_n= X_1 + X_2 +X_3.....$ @David – wrek Apr 19 '17 at 22:03
  • And also, you assume the current position (the 17th meter ) to be 0, and the problem becomes a symmetric random walk that stops at either 83 or -17. – wrek Apr 19 '17 at 22:06
  • 1
    @wrek right, so $S_1^2 = X_1^2$. Since $X_1 \in {-1,1}$ we have that $X_1^2 = 1$. Hence, $S_1^2 = 1$. Thus, $\mathbb{E}(S_1^2 - 1) = 1 - 1 = 0$. – David Apr 19 '17 at 22:08
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$$

mathreadler
  • 25,824