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