Loading Web-Font TeX/Math/Italic
| 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.