# Gambler's ruin: Distribution of the maximum fortune along the game conditioned to lose

I having troubles with this problem:

Let $(X_n)$ a gambler's ruin Markov chain on $\{0,\dots,N\}$ i.e. a Markov chain with state set $E=\{0,\dots,N\}$ and probability transitions $$p(k,k+1)= \frac{1}{2}, \ p(k,k-1)= \frac{1}{2} \text{ if }k \neq 0,N$$ and $$p(0,0)=p(N,N)=1$$ Let $$\tau = \inf\{n ≥ 0 \colon X_n = 0 \vee X_n=N\}$$ be the stopping time for which the game ends.

I need to find the probability $$P_k\left(\sup_{n \leq \tau}X_n = j \ \bigg\vert \ X_\tau = 0\right) \quad k\in \{1,\dots,N-2\}$$ i.e. I need to find the distribution of the maximum fortune along the game conditioned to lose. I have no clue how to even begin, I try to use martingale theory but with no good results.

Any help will be appreciated.

Letting $M=\sup_{n\le\tau}X_n$, start by finding $P_k(M\ge j|X_{\tau}=0)$. We have that $M\ge j$ precisely when $X_n$ hits $j$ before $0$. Let $\tau_k=\inf\{n\ge1:X_n=k\}$. Then $$P_k(M\ge j|X_{\tau}=0)=P_k(\tau_j<\tau_0|\tau_0<\tau_N)=\frac{P_k(\{\tau_j<\tau_0\}\cap\{\tau_0<\tau_N\})}{P_k(\tau_0<\tau_N)}$$ Using the Strong Markov property, you can show that $$P_k(\{\tau_j<\tau_0\}\cap\{\tau_0<\tau_N\})= P_k(\tau_j<\tau_0)P_{j}(\tau_{0}<\tau_N).$$ Intuitively, this is true since, in order to eventually attain $j$ wealth and eventually go broke, you need to first attain $j$ wealth, then starting from $j$, end up broke.
In order to find $P_k(\tau_j<\tau_0)$, we use Wald's equation on $E_k[X_{\tau_0\wedge \tau_j}-k]$, where $a\wedge b=\min(a,b)$. We can do this since $\tau_0\wedge\tau_j$ is a stopping time, and $X_n-k$ is a sum of independent random variables (provided $X_0=k$). Since each $E[X_n-X_{n-1}]=0$, we have $$E_k[X_{\tau_0\wedge \tau_j}-k] =E[X_1-X_0]\cdot E[\tau_j\wedge\tau_0] =0,$$ so $E_k[X_{\tau_0\wedge \tau_j}]=k$. But we can compute this expected value another way: $$E_k[X_{\tau_0\wedge \tau_j}] =P(\tau_j<\tau_0)\cdot j+P(\tau_0<\tau_j)\cdot0 =j\cdot P(\tau_j<\tau_0).$$ Combining these, we get $P_k(\tau_j<\tau_0)=\frac{k}{j}$. Thus, $$P_k(M\ge j|X_{\tau}=0) =\frac{P_k(\tau_j<\tau_0)P_{j}(\tau_{0}<\tau_N)}{P_k(\tau_0<\tau_N)} =\frac{(k/j)\cdot(1-j/N)}{(1-k/N)}=\frac{k(N-j)}{j(N-k)}$$ Finally, using $$P_k(M=j|X_{\tau}=0)=P_k(M\ge j|X_{\tau}=0)-P_k(M\ge j+1|X_{\tau}=0)$$ we get $$P_k(M=j)|X_{\tau}=0)=\frac{k}{N-k}\left(\frac{N-j}{j}-\frac{N-j-1}{j+1}\right)=\frac{Nk}{j(j+1)(N-k)}$$