0
$\begingroup$

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?

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

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}$

$\endgroup$
3
  • $\begingroup$ Is it possible that the statement becomes true for $k\geq 2$ or something similar? $\endgroup$ – Zhaoting Wei Apr 18 at 4:23
  • $\begingroup$ 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$ $\endgroup$ – Rahul Madhavan Apr 18 at 5:22
  • $\begingroup$ Note that expected hitting time is $\frac{n(n)}{4}$ see : math.stackexchange.com/questions/1533005/… with x = $\frac{n}{2}$ $\endgroup$ – Rahul Madhavan Apr 18 at 5:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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