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.

  • $\begingroup$ 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$! $\endgroup$ – 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.


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.