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 at 0:35
  • No, It was edited. It is with $S_T=N$ – Jhon Kevin Astoquillca Aguilar Sep 12 at 3:51
up vote 0 down vote accepted

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.)

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.