Recurrence and rates of convergence

You will get more from the exercises by trying them before looking at the solutions!

  1. Recall that the total variation distance between two probability distributions \(\mu\) and \(\nu\) on \(\mathcal{X}\) is given by \[\text{dist}_{\text{TV}}(\mu, \nu) \;=\; \sup_{A \subseteq \mathcal{X}}\{\mu(A)-\nu(A)\}\,.\] Show that this is equivalent to the distance (note the absolute value signs!) \[\sup_{A \subseteq \mathcal{X}}|\mu(A)-\nu(A)|\,.\]

Hint: Consider \(A^c\).

Solution: If \(A\subseteq \mathcal{X}\) then \(A^c \subseteq\mathcal{X}\). And if \(\pi(A)-\nu(A)\) is negative, then \(\pi(A^c)-\nu(A^c)\) is positive, since \[\pi(A^c)-\nu(A^c) = 1-\pi(A) - (1-\nu(A)) = \nu(A)-\pi(A).\] Thus the supremum of \(\pi(A)-\nu(A)\) over all subsets \(A\) of \(\mathcal X\) is always achieved when \(\pi(A)-\nu(A)\) is positive.

  1. Show that if \(\mathcal{X}\) is discrete, then \[\text{dist}_{\text{TV}}(\mu, \nu) = \tfrac12 \sum_{y\in\text{X}}|\mu(y)-\nu(y)|\,.\] (Here we do need to use the absolute value on the RHS!)
    Hint: consider \(A=\{y: \mu(y)>\nu(y)\}\).

Further hint: Show that for \(A\) as above and any \(B\subseteq\mathcal{X}\), we have \(\mu(B)-\nu(B)\le \mu(A)-\nu(A)\), and \(\nu(B)-\mu(B)\le \nu(A^c)-\mu(A^c)\).

Solution: As in the hints, note that since \(\mu(y)-\nu(y)>0\) for all \(y\in A\) and \(\nu(y)-\mu(y)\ge 0\) for all \(y\in A^c\), \[\mu(B)-\nu(B) = \sum_{y\in B}(\mu(y)-\nu(y)) \le \sum_{y\in A\cap B} (\mu(y)-\nu(y)) \le \sum_{y\in A} (\mu(y)-\nu(y)) = \mu(A)-\nu(A).\] and similarly, \[\nu(B)-\mu(B)\le \nu(A^c) - \mu(A^c).\] Thus \[\sup_{B \subseteq \mathcal{X}}\{\mu(B)-\nu(B)\} = \mu(A)-\nu(A),\] and by question 1 above we also have \[\sup_{B\subseteq \mathcal{X}}\{\mu(B)-\nu(B)\} = \sup_{B\subseteq \mathcal{X}}|\mu(B)-\nu(B)| = \sup_{B\subseteq \mathcal{X}}\{\nu(B)-\mu(B)\} = \nu(A^c)-\mu(A^c).\] Therefore, averaging the two lines above, \[\sup_{B \subseteq \mathcal{X}}\{\mu(B)-\nu(B)\} = \frac{1}{2}(\mu(A)-\nu(A)+\nu(A^c)-\mu(A^c))\] and since every \(y\in\mathcal{X}\) is in exactly one of \(A\) or \(A^c\), this equals \[\frac{1}{2}\sum_{y\in\mathcal{X}}|\mu(y)-\nu(y)|.\]

  1. Suppose now that \(\mu\) and \(\nu\) are density functions on \(\mathbb{R}\). Show that \[\text{dist}_{\text{TV}}(\mu, \nu) = 1 - \int_{-\infty}^\infty \min\{\mu(y),\nu(y)\} dy \,.\] Hint: remember that \(|\mu-\nu| = \mu+\nu - 2\min\{\mu,\nu\}\).

  2. Consider a Markov chain \(X\) with continuous transition density kernel. Show that it possesses many small sets of lag 1.

Hint: Suppose the transition density kernel of \(X\) is \(p:\mathbb{R}\times\mathbb{R}\to [0,\infty)\). For any \(x\in\mathbb{R}\), there must be some \(y\in\mathbb{R}\) such that \(p(x,y)>0\), and then since \(p\) is continuous, there must be \(\varepsilon>0\) such that \(p(x',y')>p(x,y)/2\) for all \(x'\in [x-\varepsilon,x+\varepsilon]\) and \(y'\in[y-\varepsilon,y+\varepsilon]\). Use these objects to create \(E\), \(\alpha\) and \(\nu\).

Solution: Fix \(x\in\mathbb{R}\) and then \(\varepsilon>0\) as in the hint. Let \(E=[x-\varepsilon,x+\varepsilon]\), and \(\alpha = \varepsilon p(x,y)\). Finally let \(\nu\) be uniform on \([y-\varepsilon,y+\varepsilon]\).

For any \(x'\in E\) and \(A\subset\mathbb{R}\), \[\begin{align*} \operatorname{\mathbb{P}}\left(X_{1}\in A | X_0 = x'\right) = \int_A p(x',y') dy' &\ge \int_{A\cap[y-\varepsilon,y+\varepsilon]} p(x',y') dy' \\ &\ge \int_{A\cap[y-\varepsilon,y+\varepsilon]} \frac{p(x,y)}{2} dy'\\ &= \varepsilon p(x,y) \int_{A\cap[y-\varepsilon,y+\varepsilon]} \frac{1}{2\varepsilon} dy'\\ &= \alpha \nu(A). \end{align*}\]

Thus \(E\) is a small set. Since we can do this for any \(x\in\mathbb{R}\), and we can choose \(\varepsilon>0\) arbitrarily small, we can create arbitrarily many such small sets.

  1. Consider a Vervaat perpetuity \(X\), where \[X_0=0; \qquad X_{n+1} = U_{n+1}(X_n+1) \,,\] and where \(U_1,U_2,\dots\) are independent Uniform\((0,1)\) (simulated below).

Find a small set for this chain.

Solution: There are many possible answers. Here is one: let \(E = [0,1]\), \(\alpha = 1/2\) and \(\nu\) be uniform on \([0,1]\). Let \(U\) be a uniform random variable on \([0,1]\). Then for any \(x\in E\) and \(A\subset[0,\infty)\), \[\begin{align*} \operatorname{\mathbb{P}}\left(X_{1}\in A | X_0 = x\right) = \operatorname{\mathbb{P}}\left(U(x+1)\in A\right) &= \int_{A\cap[0,x+1]} \frac{1}{x+1} dy \\ &\ge \frac{1}{2} \int_{A\cap[0,1]} dy = \frac{1}{2}\nu(A). \end{align*}\] So \(E\) is small.

  1. Recall the idea of regenerating when our chain hits a small set: suppose that \(C\) is a small set for a \(\phi\)-irreducible chain \(X\), i.e. for \(x \in C\), \[\operatorname{\mathbb{P}}\left(X_1\in A| X_0=x\right) \geq \alpha \nu(A).\] Suppose that \(X_n\in C\). Then with probability \(\alpha\) let \(X_{n+1} \sim \nu\), and otherwise let it have transition distribution \(\tfrac{p(x,\cdot)-\alpha\nu(\cdot)}{1-\alpha}\).
    1. Check that the latter expression really gives a probability distribution.
    2. Check that \(X_{n+1}\) constructed in this manner obeys the correct transition distribution from \(X_n\).
  2. Define a reflected random walk as follows: \(X_{n+1}=\max\{X_n+Z_{n+1},0\},\) for \(Z_1, Z_2, \ldots\) i.i.d. with continuous density \(f(z)\), \[ \operatorname{\mathbb{E}}\left[Z_{1}\right]<0 \quad\text{and}\quad \operatorname{\mathbb{P}}\left(Z_{1}>0\right)>0 \,. \] Show that the Foster-Lyapunov criterion for positive recurrence holds, using \(\Lambda(x)=x\).

Hint: Choose \(c\in(0,\infty)\) such that \(\operatorname{\mathbb{P}}\left(Z_1\le -c\right) > 0\) and \(\operatorname{\mathbb{E}}\left[Z_1\operatorname{\mathbf{1}}_{Z_1>-c}\right]<0\). (To see that there exists such a \(c\), let \[\tilde c = \sup\{x\in\mathbb{R} : \operatorname{\mathbb{P}}\left(Z_1\le -x\right)>0\} \in (0,\infty].\] Then since \(Z_1\) has a density, \(\operatorname{\mathbb{E}}\left[Z_1\operatorname{\mathbf{1}}_{Z_1>-\tilde c}\right]=\operatorname{\mathbb{E}}\left[Z_1\right]<0\), so \(\lim_{x\uparrow\tilde c}\operatorname{\mathbb{E}}\left[Z_1\operatorname{\mathbf{1}}_{Z_1>-x}\right]=\operatorname{\mathbb{E}}\left[Z_1\right]<0\) and \(\operatorname{\mathbb{P}}\left(Z_1\le -c\right)>0\) for all \(c < \tilde c\).) Then show that \(\{x: \Lambda(x)\le c\}\) is small.

Solution: Take \(c\) as in the hint. First we show that \(\{x: \Lambda(x)\le c\} = [0,c]\) is a small set. Let \(\nu = \delta_0\), the delta mass at \(0\), and \(\alpha = \operatorname{\mathbb{P}}\left(Z_1\le -c\right)\). Then for \(x\in[0,c]\), \[\operatorname{\mathbb{P}}\left(X_1\in A | X_0 = x\right) \ge \operatorname{\mathbf{1}}_{0\in A} \operatorname{\mathbb{P}}\left(X_1 = 0 | X_0 = x\right) \ge \operatorname{\mathbf{1}}_{0\in A}\operatorname{\mathbb{P}}\left(Z_1\le -c\right) = \alpha \nu(A),\] so indeed \([0,c]\) is small.

Then we have \[\operatorname{\mathbb{E}}\left[\Lambda(X_{n+1}) | \mathcal{F}_n\right] = \operatorname{\mathbb{E}}\left[X_{n+1} | \mathcal{F}_n\right] = \int_{-X_n}^\infty (X_n + z) f(z) dz \le X_n + \int_{-X_n}^\infty z f(z) dz.\] If \(X_n\not\in C\), i.e. \(X_n>c\), then this is smaller than \(X_n - \int_{-c}^\infty z f(z) dz\) and we have chosen \(c\) such that \(\int_{-c}^\infty z f(z) dz = \operatorname{\mathbb{E}}\left[Z_1\operatorname{\mathbf{1}}_{Z_1>-c}\right]<0\). Thus we can set \(a=-\operatorname{\mathbb{E}}\left[Z_1\operatorname{\mathbf{1}}_{Z_1>-c}\right]\).

On the other hand, if \(X_n\in C\), then \[\operatorname{\mathbb{E}}\left[\Lambda(X_{n+1}) | \mathcal{F}_n\right] \le X_n + \int_{-X_n}^\infty z f(z) dz \le X_n + \int_0^\infty z f(z) dz\] so we can choose \(b=a+\int_0^\infty z f(z) dz\). Thus we have shown that \(X\) satisfies the Foster-Lyapunov criterion for positive recurrence.