Interesting random walk question with differing probabilities

104 Views Asked by At

Consider a random walk on the integers on the interval $[-N, N].$ For each $n \in [-N, 0],$ the walk is a simple symmetric random walk. For each $n \in [1, N]$, the probability of moving to the right is $1/4$ and the probability of moving to the left is $3/4.$ If the random walk starts at $0$, I want to show that as $N \rightarrow \infty,$ the probability of reaching the left end before the right end tends to $1.$

I know there are a lot ways to solve this, but I wanted to see if my argument was correct.

Shift the random walk up to $[0,2N]$ so then the random walk starts at $N.$ Now, $\text{just}$ consider the random walk on $[N, 2N].$ Then, $$P( \text{random walk ever reaches $2N$ starting at $N$}) = \left ( \frac{p}{q} \right ) ^N = \left ( \frac{1}{3} \right ) ^ N \rightarrow 0 \ \text{as} \ N \rightarrow \infty.$$

Since the random walk below $N$ is just a simple symmetric random walk, it is recurrent and thus $$ P( \text{random walk reaches $2N$ before 0}) \leq P( \text{random walk ever reaches $2N$ starting at $N$}) \rightarrow 0 \ \text{as} \ N \rightarrow \infty.$$ Thus, $$P( \text{random walk reaches $0$ before $2N$}) \rightarrow 1 \ \text{as} \ N \rightarrow \infty.$$ Is this idea valid?

1

There are 1 best solutions below

0
On

I don't think you can so naively split the walk into two walks.

There is a way to split the walks, but it requires a little more work.

Let a walk on the integers start at $1.$ Let $r$ be the probability on each step that you add $-1,$ with $+1$ being probability $1-r.$

Let $q_{N,r}$ be the probability of reaching $N$ before reaching $0.$

Then if $p_N$ is the probability for your question or reaching $N$, then the probability that starting at $0$, you get to $N$ without passing through $0$ again is $\frac12q_{N,3/4}.$ The probability that you pass through $0$ again is $\frac12\left(1-q_{N,1/2}+1-q_{N,3/4}\right).$

So you get: $$p_{N}=\frac12 q_{n,3/4}+\frac12(2-q_{N,1/2}-q_{N,3/4})p_N$$ Solving, you get: $$p_N=\frac{q_{N,3/4}}{q_{N,3/4}+q_{N,1/2}}$$so we need to somehow get bounds on $q_{N,r}.$

We will do so by induction.

When $N=1,$ $q_{1,r}=1,$ since you are already at $N.$

Now we try to compute $q_{N+1,r}$ in terms of $q_{N,r}.$

If you are at $2,$ the probability you reach $N+1$ before $1$ is just $q_{N,r}.$ So:

$$q_{N+1,r}=(1-r)q_{N,r}+(1-r)(1-q_{N,r})q_{N+1,r}$$

Solving again, we get:

$$q_{N+1,r}=\frac{(1-r)q_{N,r}}{1-(1-r)(1-q_{N,r})}=\frac{q_{N,r}}{\frac r{1-r}+q_{N,r}}$$

When $r=1/2,$ $\frac r{1-r}=1,$ and you get: $$q_{N,1/2}\geq \frac1{2^{N-1}}$$

When $r=3/4,$ $\frac{r}{1-r}=3,$ and you get: $$q_{N,3/4}\leq \frac1{3^{N-1}}$$

From here, you get: $$p_N=\frac{q_{N,3/4}}{q_{N,3/4}+q_{N,1/2}}\leq \left(\frac23\right)^{N-1}\to 0.$$