Existence of separators for biased random walk.

Question

Let us consider a biased random walk in $\mathbf{Z}$ whose step-lengths satisfy $\mathbf{P}(\xi = +1) = p > \mathbf{P}(\xi = -1) = q$ (with $p+q = 1$).

A value $k \in \mathbf{Z}$ is a "separator" of the random walk if the random walk started before $k$ passes through $k$ only once.

By the strong Markov property $\mathbf{P}_k(0 \text{ is separator}) = \mathbf{P}_0(\text{The random walk never returns to zero}).$ Denote by $A_k$ the probability of the random walk, started at $k \neq 0,$ to never visit zero and $A_0$ be the probability of never return to zero. By the strong law of large numbers, $A_k = 0$ for all $k$ negative. Now, using first step analysis is easy to deduce $A_{k + 1} = q A_k + pA_{k + 2}$ for $k \geq 1,$ $A_0 = p A_1$ and $A_1 = p A_2.$ Then, we have $$A_{k + 2} - A_{k + 1} = \dfrac{q}{p}(A_{k + 1} - A_k) \quad (k \geq 1).$$ It is easy to show $A_{k+2}-A_{k+1}=(\frac{q}{p})^{k+1} A_1$ which then leads to, by means of a telescopic sum, $$A_k=\dfrac{1}{p} \left[ \sum_{j=0}^k \left( \dfrac{q}{p} \right)^j \right] A_0.$$ This shows that $A_k \to \dfrac{1}{p} \dfrac{1}{1 - \frac{q}{p}} A_0 = \dfrac{1}{p-q}A_0.$

My intuition suggests strongly that $A_k \to 1.$ How to prove this formally?

Having this, I can conclude $A_0 = p - q,$ which is very reasonable. So, the probability of zero being separator, starting at $k < 0$ is simply $p - q.$

Consider now the set $\mathrm{X}_a = \{a\text{ is a separator}\}.$ The previous can be restated as $$\mathbf{P}_0(\mathrm{X}_a) = p - q$$ for every $a \geq 0.$

Can I use the previous formula to conclude $\mathbf{P}_0\left(\bigcup\limits_{a = 0}^N \mathrm{X}_a\right) \to 1$ as $N \to \infty$?

Answer 1

You can show that $$ (1-A_k)=(1-A_1)^k\qquad\text{for all $k\ge 1$}\tag{$*$} $$ Why? You know $1-A_k$ is the probability of starting from $k$ and eventually hitting $0$. This is equal to the probability of starting from $k$ and moving eventually to $k-1$, then starting from $k-1$ and moving eventually to $k-2$, then $\dots$ then starting from $1$ and moving to $0$. But moving from $i$ to $i-1$ is the same as moving from $1$ to $0$, so each event in that list of $k$ events has probability $(1-A_1)$.

Plugging $(*)$ with $k=2$ and $k=3$ into $$ A_2=pA_3+qA_1, $$ you can solve for $A_1$. You will find that $A_1<1$, so that $(*)$ implies $A_k\to 1$ as $k\to\infty$ .

Answer 2

I found a nice solution after a while.

My first question is yes. The reason is much simpler than not. It is well known that for an irreducible Markov chain that is is recurrent we have that: for whatever the initial state $k$ may be and whatever another stat $o$ may be, the probability of starting at $k$ and eventually reaching $o$ is one.

To my second question. We consider $\alpha_n = \mathbf{P}_0\left( \bigcup\limits_{a=0}^n \mathrm{X}_a^\complement\right)$ and notice that $(\alpha_n)$ is increasing and therefore convergent. We show now that $(\alpha_{n^2})$ converges to 1. To see this simply notice that

$$0 \leq 1 - \alpha_{n^2} \leq \mathbf{P}_0\left( \bigcup\limits_{a=0}^n \mathrm{X}_{an}^\complement\right).$$

We can define now stopping times $\tau_p$ to be the first entrance to state $p$ and measurable times $\theta_p$ which are the first returns to $p.$ Then we divide $$\begin{align*} \mathbf{P}_0\left( \bigcup\limits_{a=0}^n \mathrm{X}_{an}^\complement\right) &= \mathbf{P}_0\left( \bigcup\limits_{a=0}^n \mathrm{X}_{an}^\complement \cap\{\theta_0 < \tau_n \leq \theta_n < \tau_{2n}\leq \theta_{2n}<\ldots<\tau_{n^2}\leq\theta_{n^2}<\infty\}\right)\\ &+\mathbf{P}_0\left( \bigcup\limits_{a=0}^n \mathrm{X}_{an}^\complement \cap\bigcup_{j=1}^n\{\tau_j < \theta_{(j-1)n}\}\right)\\ &\leq\mathbf{P}_0\left(\theta_0 < \tau_n \leq \theta_n < \tau_{2n}\leq \theta_{2n}<\ldots<\tau_{n^2}\leq\theta_{n^2}<\infty\right) + \sum_{j=1}^n\mathbf{P}_0(\tau_j<\theta_{(j-1)n})\\ &\mathop{=}^\triangle \gamma_n +\sum_{j=1}^n \omega_j. \end{align*}$$

To deal with $\gamma_n$ simply use conditional expectation conditioning on the sigma field generated by $S_0,\xi_1, \ldots, \xi_{\tau_n}$ to reach the inequality $\gamma_n\leq(1-(p-q))\gamma_{n-1}$ and so $\gamma_n \to 0$ (exponentially fast!)

Observe that $\omega_j \leq \mathbf{P}_0(\text{The random walk will ever hit} -n)$ and this is well known to be $(\frac{q}{p})^n$ and clearly $n(\frac{q}{p})^n \to 0$ as well. Q.E.D.