# Conditional probability in gambling game

I think I'm not understanding how it works: Let $(X_n)_n$ a simple random walk in $\mathbb{Z}$, $\mathbb{P}(X_n=+1)=\mathbb{P}(X_n=-1)=.5$ and $S_n=\sum^n_{k=1} X_k$, $T=\min\{n\in \mathbb{N}: S_n \in \{0,N\} \}$. Then $$F(x)=\frac{1}{2}F(x+1)+\frac{1}{2}F(x-1)$$ where $F(x)=\mathbb{P}(S_T=N|S_0=x)$ and $x\in [1,2,...,N-1]$

My attempt: Conditioning with respect to $X_1$ $$F(x)=\mathbb{P}(S_T=N|X_1=1|S_0=x)\mathbb{P}(X_1=1|S_0=x) + \mathbb{P}(S_T=N|X_1=-1|S_0=x)\mathbb{P}(X_1=-1|S_0=x)$$ Then $$F(x)=\mathbb{P}(S_T=N|X_1=1,S_0=x)\frac{1}{2} + \mathbb{P}(S_T=N|X_1=-1,S_0=x)\frac{1}{2}$$ Now, $\{X_1=1,S_0=x\}\neq\{S_1=x+1\}$ because $\{X_1=-1,S_0=x+2\} \subset \{S_1=x+1 \}$

How can I show: $\mathbb{P}(S_T=N|X_1=1,S_0=x)=\mathbb{P}(S_T=N|S_0=x)$ strong Markov property? I don't know how use it here.

• Which is exactly the definition of $F(x)$? Is it $$F(x)=\mathbb{P}(S_{\color{red}{N}}=N|S_0=x)\ ?$$ – dan_fulea Sep 12 '18 at 0:35
• No, It was edited. It is with $S_T=N$ – Jhon Kevin Astoquillca Aguilar Sep 12 '18 at 3:51

To see what kind of problem we have, let us consider some particular cases for the value of $N\ge 1$, and we consider the event $A_N$ of all paths of the process $S$, that start in $x\in(0,N)$ and end in either $0$ or $N$ for the first time at point $N$. So we can consider instead of $\Bbb Z$ the following simpler "cyclic" model with an absorbent state:

0   1   2   3       x          N-2 N-1  N
o---o---o---o---o---o---o---o---o---o---o
\                                     /
\                                   /
\---> ABSORPTION State = (*) <----/

• The case $N=2$ is simple, $F(x)=0$ for all $x=0,1,2$, because we reach $0,N$ either at step zero ($x=0,2$), or at step one $x=1$.

• We consider the case $N=3$. Then $F(0)=F(3)=0$, since we reach one of the end states $0,3$ at step zero, then the only "good paths" that reach an end state at step $3$ are $1210$ and $2123$. So $F(1)=F(2)=1/2^3$. The relation $2F(x)=F(x-1)+F(x+1)$ is thus not satisfied for $x=1,2$.

• We consider the case $N=4$. Then $F(0)=F(4)=0$, since we reach one of the end states $0,3$ at step zero, then the only "good paths" that reach an end state at step $4$ are

01234 (time line)

1---- (for parity reasons)
21210
21234
23210
23234
3---- (for parity reasons)


so $F(0)=F(1)=F(3)=F(4)=0$, and $F(2)=4\cdot 1/2^4$. The relation $2F(x)=F(x-1)+F(x+1)$ is again not satisfied for $x=1,2,3$.

• A similar counting for $N=5$ gives the paths in $A_5$

121210
123210
212345
232345
234345
321210
323210
343210
432345
434345


so $F(1) = 2/2^5$, $F(2) = 3/2^5$, $F(3) = 3/2^5$, $F(4)=2/2^5$. Again, we have problems to check the relation.

• Last special case, $N=6$:

2121210
2123210
2123456
2321210
2323210
2323456
2343210
2343456
2345456
4321210
4323210
4323456
4343210
4343456
4345456
4543210
4543456
4545456


and again, the parity reason makes $F(1)=F(3)=F(5)=0$, and counting the above paths, $F(2)=F(4)= 6/2^6$.

A "similar relation" that may rather hold is the following one. We define: $$F_M(x)=\Bbb P(S_T=M|S_0=x)\ ,$$ i.e. the probability that starting from $x$ (with $0<x<n$) we reach either $0$ or $N$ after exactly $M\ge0$ steps. Then $$F_M(x)=\frac 12F_{M-1}(x-1)+\frac 12F_{M-1}(x+1)\ .$$ (In words, to get in exactly $M$ steps from $x$ to an end point (zero or $N$), we pass in one step from $x$ to one of its neighbours, $x\pm1$, then need further exactly $M-1$ steps to reach an end point.)