# How to prove $\mathbb{P}\{T_A>kN\}\leq (1-1/2d)^k$ for a simple random walk in $\mathbb{Z}^d$?

I am reading Gregory F. Lawler's Random Walk and the Heat Equation. In page 49, there is

Exercise 1.22. Suppose $$S_n$$ is a simple random walk in $$\mathbb{Z}^d$$ and $$A\subset \mathbb{Z}^d$$ is a finite subset with $$N$$ points. Let $$T_A$$ be the smallest $$n$$ such that $$S_n\not\in A$$. Show that $$\mathbb{P}\{T_A>kN\}\leq \Big(1-\frac{1}{2d}\Big)^k.$$ Since the problem does not specify what is the starting point, I think the result is true for any $$S_0$$.

How to prove this result?

• my recollection is: try to prove it for $d=1$ and get a contradiction. I found a lot of errors in that book. – user8675309 Apr 16 at 2:16

To Prove: $$\mathbb{P}\{T_A>kN\}\leq \left(1-\frac{1}{2d}\right)^k$$.

First we do this for 1 dimensional case and then extend

Assumption: Let the points in A be contiguous. Further, let us start from the center of this interval. Any other case will have a higher probability that we hit the edges of the wall before $$N$$ steps, so this is a conservative estimate. As per this assumption, we start at 0, and the points are arranged as $$\frac{N}{2}$$ to the right and $$\frac{N}{2}$$ to the left.

Case 1: First for simplicity, set $$k=1$$ and $$d =1$$. Then we want to show that $$\mathbb{P}\{T_A>N\} \leq \frac{1}{2}$$.

We will assume this for now, and at the end show a counter example.

Case 2: Now consider the case where $$d=1$$ and $$k>1$$.

Inductive Proof: In time the first time period $$n$$, we have a probability of 50% of hitting the edge of $$A$$. This is irrespective of where in $$A$$ we started. After the first time period, the $$SRW$$ may be at a distance $$[0,\frac{N}{2}]$$ from the edge of $$A$$.

Given another time period $$n$$, atleast 50% of these random walks will hit the edge of $$A$$. So only $$50%$$ of the $$50%$$ will remain without hitting the edge of $$A$$.

Similarly, we can extend the argument. If $$\mathbb{P}\{T_A>Nk\} \leq \frac{1}{2^k}$$, then $$\mathbb{P}\{T_A>N(k+1)\} \stackrel{?}{\leq} \frac{1}{2^{k+1}}$$. The answer is yes, because \begin{align*} \mathbb{P}\{T_A>N(k+1)\} &= \mathbb{P}\{T_A>N(k)\}\mathbb{P}\{T_A>N\}\\ &<\frac{1}{2^k}\times \frac{1}{2} \\ &= \frac{1}{2^{k+1}} \end{align*}

Case 3: Now consider the case when $$k=1$$ and $$d>1$$.

We will assume for now that $$\mathbb{P}\{T_A>N\}\leq \left(1-\frac{1}{2d}\right)$$

Case 4: This is a similar inductive argument as case 2. If at time $$N$$, the SRW stays in $$A$$ with probability at least $$\left(1-\frac{1}{2d}\right)$$, then in time $$2N$$, it stays in $$A$$ with probability at least $$\left(1-\frac{1}{2d}\right)^2$$. Similarly, if $$\mathbb{P}\{T_A>Nk\} \leq \left(1-\frac{1}{2d}\right)^k$$, then \begin{align*} \mathbb{P}\{T_A>N(k+1)\} &= \mathbb{P}\{T_A>N(k)\}\mathbb{P}\{T_A>N\}\\ &<\left(1-\frac{1}{2d}\right)^k\times \left(1-\frac{1}{2d}\right) \\ &= \left(1-\frac{1}{2d}\right)^{k+1} \end{align*}

Counter Example:

Let $$A = \{-2,-1,0,1,2\}, N = |A| = 5$$. We wanted to show $$\mathbb P(T_A > N)\leq \frac{1}{2}$$. We will show $$\mathbb P(T_A \leq N)\leq \frac{1}{2}$$ implying that $$\mathbb P(T_A > N)> \frac{1}{2}$$

Let $$S_n$$ be the steps over 5 steps. We check if Random walk has gone out of A.

$$\begin{array}{|c|c|c|c|c|c|} \hline S_1 &S_2 &S_3 &S_4 &S_5 & \text{Gone out of A?}\\ \hline -1 & -2 & -3 & -4 & -5 & TRUE \\ \hline -1 & -2 & -3 & -4 & -3 & TRUE \\ \hline -1 & -2 & -3 & -2 & -3 & TRUE \\ \hline -1 & -2 & -3 & -2 & -1 & TRUE \\ \hline -1 & -2 & -1 & -2 & -3 & TRUE \\ \hline -1 & -2 & -1 & -2 & -1 & FALSE \\ \hline -1 & -2 & -1 & 0 & -1 & FALSE \\ \hline -1 & -2 & -1 & 0 & 1 & FALSE \\ \hline -1 & 0 & -1 & -2 & -3 & TRUE \\ \hline -1 & 0 & -1 & -2 & -1 & FALSE \\ \hline -1 & 0 & -1 & 0 & -1 & FALSE \\ \hline -1 & 0 & -1 & 0 & 1 & FALSE \\ \hline -1 & 0 & 1 & 0 & -1 & FALSE \\ \hline -1 & 0 & 1 & 0 & 1 & FALSE \\ \hline -1 & 0 & 1 & 2 & 1 & FALSE \\ \hline -1 & 0 & 1 & 2 & 3 & TRUE \\ \hline 1 & 0 & -1 & -2 & -3 & TRUE \\ \hline 1 & 0 & -1 & -2 & -1 & FALSE \\ \hline 1 & 0 & -1 & 0 & -1 & FALSE \\ \hline 1 & 0 & -1 & 0 & 1 & FALSE \\ \hline 1 & 0 & 1 & 0 & -1 & FALSE \\ \hline 1 & 0 & 1 & 0 & 1 & FALSE \\ \hline 1 & 0 & 1 & 2 & 1 & FALSE \\ \hline 1 & 0 & 1 & 2 & 3 & TRUE \\ \hline 1 & 2 & 1 & 0 & -1 & FALSE \\ \hline 1 & 2 & 1 & 0 & 1 & FALSE \\ \hline 1 & 2 & 1 & 2 & 1 & FALSE \\ \hline 1 & 2 & 1 & 2 & 3 & TRUE \\ \hline 1 & 2 & 3 & 2 & 1 & TRUE \\ \hline 1 & 2 & 3 & 2 & 3 & TRUE \\ \hline 1 & 2 & 3 & 4 & 3 & TRUE \\ \hline 1 & 2 & 3 & 4 & 5 & TRUE \\ \hline overall&&&&&\text{14 out of 32 go out of A}\\ \hline \end{array}$$

Therefore, $$\mathbb P [ T_A \leq N] < \frac{1}{2}\implies\mathbb P [ T_A > N] \geq \frac{1}{2}$$

• Is it possible that the statement becomes true for $k\geq 2$ or something similar? – Zhaoting Wei Apr 18 at 4:23
• A statement is either true or not. In this case it is not true. Particularly the first part. In fact I was trying to prove $k=1$ case for a long time (by induction, integrating the distribution of stopping times, etc), before I realized the statement is wrong - when i started trying to construct a counterexample. It may be the case that it is true for large n. I have not gone through the literature for this - what you are looking for (to prove) is median hitting time for $[-n,n]$ is less than $2n$ – Rahul Madhavan Apr 18 at 5:22
• Note that expected hitting time is $\frac{n(n)}{4}$ see : math.stackexchange.com/questions/1533005/… with x = $\frac{n}{2}$ – Rahul Madhavan Apr 18 at 5:26