| Register
\(\newcommand{\Cat}{{\rm Cat}} \) \(\newcommand{\A}{\mathcal A} \) \(\newcommand{\freestar}{ \framebox[7pt]{$\star$} }\)

6. Various

    1. Kac’s random walk

          Consider the Kac’s random walk on the $n$-sphere defined as follows: for a vector $v\in \mathcal S^n$, pick two coordinates uniformly at random, and an angle uniformly at random on $[0,2\pi)$. Then rotate in the circle generated by the two coordinates by that angle.

      Add remark

      Problem 6.1.

      [Natesh Pillai] Does Kac’s random walk on $\mathcal S^n$ exhibit cutoff?

      Does the analogously defined random walk on $SO(n)$ exhibit cutoff?
          For Kac’s random walk, it is known that $\frac 12 n\log n \leq t_{\mbox{mix}} \leq 4n\log n$.

      For the two coordinate random walk on $SO(n)$, $t_{\mbox{mix}}\leq O(n^4)$ but $\tilde O(n^2)$ is conjectured.

        • Metropolis on $[0,1]^2$

              Consider the stationary distribution on $[0,1]^2$ given by \[\pi_A(p_1,p_2)=\mathcal Z^{-1} \exp(-A|p_1-p_2|^2) \] parametrized by $A\in [10,1000]$.

          Add remark

          Problem 6.2.

          [Persi Diaconis] Obtain a good bound on the mixing time of the Metropolis algorithm for this stationary distribution in terms of $A$. Generalize this to $[0,1]^d$.
              The current best known upper bound is $\exp(A^2)$.

            • Random walk on monotone subsets of $\{0,1\}^n$

                  Let $A\subset \{0,1\}^n$ be a monotone subset of the hypercube: for all $x\in A$, if $y$ satisfies $y_i\geq x_i$ for all $1\leq i\leq n$, then $y\in A$. The random walk picks a coordinate at random, flip it, and accepts the move only if it remains in $A$.

              Add remark

              Problem 6.3.

              [Ben Morris] Can we establish an upper bound in $O(n\log n)$ for the mixing time ?
                  Ding and Mossel (2014) showed that $$ t_{\text{mix}}\leq 2\left(\frac{16n}{\mathbb{P}(A)}\right)^2 \log\left(4\cdot2^n\mathbb{P}(A)\right)\, , $$ where $\mathbb{P}(\cdot)$ is the uniform probability on $\{0,1\}^n$.

                • Function-specific mixing time and concentration

                      Let $(X_n)$ be a stationary Markov chain on a finite state space $\Omega$ and $f\colon\Omega\to [-1,1]$. Consider $$ S_n=\frac{1}{n} \sum_{i=1}^n f(X_i) . $$

                  Add remark

                  Problem 6.4.

                  [Maxim Rabinovich] Does there exist an absolute constant $c>0$ such that, for all $\varepsilon>0$ and $n\geq 1$, $$ \mathbb{P}\left(\Big| S_n-\mathbb{E} S_n\Big| \geq\varepsilon\right)\leq 2\exp\left(-\frac{cn\varepsilon^2}{t_f(\delta)}\right)\, , $$ where $t_f(\delta)=\sup_{x\in\Omega}\left\{n\geq 0,\, \Big|\mathbb{E}_x f(X_n) -\mathbb{E}_\pi f\Big|\leq\delta\right\}$ ? Does it hold for $\delta=1/4$?
                      - This is known for $\delta=\varepsilon^2$, Maxim Rabinovich, Aaditya Ramdas, Michael I. Jordan, and Martin J. Wainwright (2016).

                  - In the reversible case, this holds with $t_f$ replaced by $t_{\text{REL}}$ (Gilman, 1998).

                  - Allan Sly’s counterexample for $\delta=1/4$: let $\Omega$ be a segment of length $N$. For all $1\leq i\leq N$, $f(i)=\pm 1$. In each local neighborhood, the number of $1$’s is approximately equal to the number of $-1$’s, but there is a fraction $1/100$ more $1$’s on the right side and a fraction $1/100$ more $-1$’s on the left side.

                  - Roberto Oliveira’s progress: it holds with $\delta=\varepsilon/2$. Let $t=t_f(\varepsilon/2)$ and assume $n=kt$. Then \begin{eqnarray*} S_n &=&\frac{1}{t}\sum_{\ell=1}^t\frac{1}{k} \sum_{i=0}^{k-1} f(X_{it+\ell})\, . \end{eqnarray*} Let $\theta\geq 0$. By convexity of $x\mapsto \exp(\theta x)$, \begin{eqnarray*} \mathbb{E}\left[\mathrm{e}^{\theta (S_n-\mathbb{E}_\pi f)}\right]&\leq & \frac{1}{t}\sum_{\ell=1}^t \mathbb{E}\left[\mathrm{e}^{\theta \frac{1}{k} \sum_{i=0}^{k-1} (f(X_{it+\ell})-\mathbb{E}_\pi f)}\right]\, . \end{eqnarray*} Now, by definition of $t$, $\mathbb{E}_\pi f\geq \mathbb{E}\left[f(X_{it+\ell})\big|X_\ell,X_{t+\ell},\dots,X_{(i-1)t+\ell}\right]-\varepsilon/2$. And by Hoeffding’s inequality, \begin{eqnarray*} \mathbb{E}\left[\mathrm{e}^{\theta (S_n-\mathbb{E}_\pi f)}\right]&\leq & \frac{1}{t}\sum_{\ell=1}^t \mathrm{e}^{\frac{\theta\varepsilon}{2}}\mathbb{E}\left[\mathrm{e}^{\theta \frac{1}{k} \sum_{i=0}^{k-1} \left(f(X_{it+\ell})-\mathbb{E}\left[f(X_{it+\ell})\big|X_\ell,\dots,X_{(i-1)t+\ell}\right]\right)}\right]\\ &\leq & \mathrm{e}^{\frac{\theta^2}{2k}+\frac{\theta\varepsilon}{2}}\, . \end{eqnarray*} Applying the same arguments to $\theta<0$, one obtains \begin{eqnarray*} \mathbb{P}\left(\Big| S_n-\mathbb{E} S_n\Big| \geq\varepsilon\right)&\leq& 2\exp\left(-\frac{k\varepsilon^2}{8}\right)\, , \end{eqnarray*}

                      Cite this as: AimPL: Markov chain mixing times, available at http://aimpl.org/markovmixing.