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

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.

• There was a typo, and also I fixed your link :) -- in particular, the typo may have been causing confusion, since how it was we always have $T = 0$! – Sam T Mar 13 at 21:52

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.