Simple random walk on $\mathbb Z$; Coupling Argument

Question

I am reading the proof of Theorem 3.1 from these notes and I am stuck at one point.

Let $X_1, X_2, X_3, ...$ be i.i.d random variable valued in $\{1, -1\}$ each distributed uniformly. Let $S_n=\sum_{i=1}^n X_i$. So $S_n$ is the position at time $n$ of a particle walking on $\mathbb Z$ which starts at $0$ and moves either right or left (one step at a time) with probability half each.

So $S=(S_n)_{n=1}^\infty$ is the simple random walk on $\mathbb Z$ starting at $0$. Let $k$ be an even integer and let $S'=(S_n')_{n=1}^\infty$ be the simple random walk on $\mathbb Z$ starting at $k$ and independent of $S$.

Let $\mu_n$ and $\mu_n'$ be the distributions of $S_n$ and $S_n'$ respectively.

Goal. To show that $\lim_{n\to \infty}\|\mu_n-\mu_n'\|_{TV} = 0$

where "TV" denotes the total variation distance.

Define $T=\min\{n\geq 0:\ S_n = S_n'\}$. Let $\hat{\mathbb P}$ be the joint distribution of $S_n$ and $S_n'$.

Then (here is where I am stuck) $$\|\mu_n-\mu_n'\|_{TV} \leq 2\hat{\mathbb P}(T>n)$$

$\bullet$ One thing that bothers me in the above is that the expression $\hat{\mathbb P}(T>n)$ is not making sense to me since $\hat{\mathbb P}$ is a probability measure on $\mathbb N_0\times \mathbb N_0$ and $T$ is a map whose domain is not $\mathbb N_0\times \mathbb N_0$. I am assuming that by $\hat{\mathbb P}(T>n)$ the author really means $\mathbb P(T>n)$, where $\mathbb P$ is the probability measure on the common (hidden) probability space which is the domain of each $S_n, S_n'$, and $T$. (If I am wrong then please correct me).

$\bullet$ The other thing is how do we get this inequality. I think the author has used the fact that the joint distribution of $S_n$ and $S_n'$ is a coupling of $S_n$ and $S_n'$ and hence (twice) the coupling distance exceeds the total variation distance. But I don't see how this applies. What I get from what I just said is that $$\|\mu_n-\mu_n'\|_{TV}\leq 2\mathbb P(S_n\neq S_n')$$ But the event $\{T>n\}$ is contained in the event $\{S_n\neq S_n'\}$. So I am not able to get the desired inequality.

Answer 1

Regarding your first question, about $\hat {\mathbb P}$, note that the lecture notes say "joint distribution of $(S,S')$", not "joint distribution of $S_n$ and $S_n'$". In order to know if $T > n$ or not, one needs to know $(S_1, ..., S_n, S_1', ..., S_n')$. So, just like $\mathbb P$ is really a distribution on the path $S$, but in particular one can look at all paths with $S_n = x$, for example, $\hat{\mathbb P}$ is a distribution on the pairs of paths $(S,S')$. In general, I would suggest that one doesn't have to worry too much about the underlying space, just think of $\hat{\mathbb P}$ as "basically the same as $\mathbb P$, but just with two walks".

Regarding the second question, for any coupling $(X,X')$ of two distributions $\mu$ and $\mu'$, and any event $A$, we have $$ \mu(A) - \nu(A) = P(X \in A) - P(X' \in A) \le P(X \in A, \, Y \notin A) \le P(X \ne Y). $$ See Theorem 2.4 in your linked lecture notes.

Answer 2

About the inequality, $||\mu_n-\mu_n^\prime||_{TV}\leq 2\mathbb{\hat{P}}(T>n)$, it's a bit more involved since by the given definition $T$ is not the coupling time of $S$ and $S^\prime$ (coupling time $\tau=\min\{n\geq 0:S_m=S_m^\prime\text{ for all } m\geq n\}$) . As you have correctly said $||\mu_n-\mu_n^\prime||_{TV}\leq 2\mathbb{\hat{P}}(S_n\neq S_n^\prime)$ and $\mathbb{\hat{P}}(S_n\neq S_n^\prime)\geq\mathbb{\hat{P}}(T>n)$ which does not give the inequality. So construct another random walk $S^{\prime\prime}$ such that it is in distribution same as $S$ and $T$ is coupling time of $S^{\prime\prime}$ and $S^\prime$. Define $S^{\prime\prime}=(S_n^{\prime\prime})_{n\geq 0}$ as below, $$ S_n^{\prime\prime} = \begin{cases} S_n \text{ if } n\leq T\\ S_n^{\prime}\text{ otherwise.} \end{cases} $$ Since $T$ is a stopping time for both $S$ and $S^\prime$, by strong markov property, $S^{\prime\prime}\overset{d}{=}S$. It is easy to see $T$ is coupling time of $S^{\prime\prime}$ and $S^\prime$. Thus, $$ ||\mu_n-\mu_n^\prime||_{TV}\leq 2\mathbb{\hat{P}}(S_n^{\prime\prime}\neq S_n^\prime)\leq2\mathbb{\hat{P}}(T>n) $$ since $\{S_n^{\prime\prime}\neq S_n^\prime\}\subseteq\{T>n\}$.