The probability of comparing two stopping times in simple random walk

110 Views Asked by At

For a simple random walk $\{X_n\}$ starting at point zero, let $T_k=\inf\{n>0|X_n=k\}$. What's probability that $P\{T_k<T_0|X_0=0\}$ for $k\ne 0$?

Note that $X_n=\sum_{i=1}^{n}\xi_i$ where $P\{\xi_i=1\}=p$, $P\{\xi_i=-1\}=1-p$ and $\{\xi_i\}$ is i.i.d. sequence.

1

There are 1 best solutions below

4
On BEST ANSWER

I assume you mean $T_y =\inf\{n>0 : X_n = y\}$ and $p = P( X_1 = 1 | X_0 = 0)$. For $y = 1$ we have by distinguishing the first step $P( T_y < T_0 | X_0 = 0) = P( X_1 = 1 | X_0 = 0) = p$. ($y = -1$ is analogue, such that $P( T_y < T_0 | X_0 = 0) = 1 - p$)

Define $T^E_y =\inf\{n\ge 0 : X_n = y\}$

Let $y > 1 $ and $f(z) := P( T^E_y < T^E_0 | X_0 = z)$ for $z \in \{0 , \ldots , y\}$. Again by the first step argument $$P( T_y < T_0 | X_0 = 0) = P( X_1 = 1 | X_0 = 0) P( T^E_y < T^E_0 | X_1 = 1) = p \cdot f(1)$$ Thus we are interested in $f(1)$. Again by first step argument we get the recursion formula $$f(z) = p f(z+1) + (1-p) f(z-1)$$ for $z \in \{1 , \ldots , y-1\}$ and we know that obviously $f(0) = 0$ and $f(y) =1$. The formula above yields that $f(z+1) - f(z) = \frac{1-p}p (f(z) - f(z-1)) = \left( \frac{1-p}p\right)^z f(1)$. Thus for $z= y-1$: $$1= f(y) = \sum_{z=0}^{y-1} f(z+1) - f(z) = f(1) \sum_{z=0}^{y-1} \left( \frac{1-p}p\right)^z = \begin{cases} f(1) \frac{1 - (\frac{1-p}{p})^y}{1 - \frac{1-p}{p}} &: p\neq \frac 1 2 \\ f(1) y &: \text{else}\end{cases}$$ Therefore $$f(1) = \begin{cases} \frac{2p-1}{p(1 - (\frac{1-p}{p})^y)} &: p\neq \frac 1 2\\ \frac 1 y &: \text{else} \end{cases}$$