Speeding up Markov chains with deterministic jumps
- PDF / 374,852 Bytes
- 22 Pages / 439.37 x 666.142 pts Page_size
- 49 Downloads / 187 Views
Speeding up Markov chains with deterministic jumps Sourav Chatterjee1
· Persi Diaconis1
Received: 23 April 2020 / Revised: 25 August 2020 / Accepted: 18 September 2020 / Published online: 22 September 2020 © Springer-Verlag GmbH Germany, part of Springer Nature 2020
Abstract We show that the convergence of finite state space Markov chains to stationarity can often be considerably speeded up by alternating every step of the chain with a deterministic move. Under fairly general conditions, we show that not only do such schemes exist, they are numerous. Keywords Markov chain · Mixing time · Spectral gap · Cheeger constant Mathematics Subject Classification 60J10 · 60J22
1 Introduction This paper started from the following example. Consider the simple random walk on Zn (the integers mod n): X k+1 = X k + k+1
(mod n),
with X 0 = 0, and 1 , 2 , . . . i.i.d. with equal probabilities of being 0, 1 or −1. This walk takes order n 2 steps to reach its uniform stationary distribution in total variation distance. This slow, diffusive behavior is typical of low dimensional Markov chains (“Diameter2 steps are necessary and sufficient”—see Diaconis and Saloff-Coste [19]
In memory of Harry Kesten. Sourav Chatterjee’s research was partially supported by NSF Grant DMS-1855484. Persi Diaconis’s research was partially supported by NSF Grant DMS-1954042. Data availability statement: Data sharing not applicable to this article as no datasets were generated or analyzed during the current study.
B
Sourav Chatterjee [email protected] Persi Diaconis [email protected]
1
Departments of Mathematics and Statistics, Stanford University, Stanford, CA, USA
123
1194
S. Chatterjee, P. Diaconis
for careful statements and many examples). Now change the random walk by deterministic doubling: X k+1 = 2X k + k+1
(mod n).
This walk has the “same amount of randomness”. Results discussed below show that it takes order log n steps to mix (at least for almost all n). We would like to understand this speedup more abstractly—hopefully to be able to speed up real world Markov chains. Our main result shows a similar speedup occurs for fairly general Markov chains with deterministic doubling replaced by almost any bijection of the state space into itself. We proceed to a careful statement in the next section. In Sect. 3 a literature review offers pointers to related efforts to beat diffusive behavior. A sketch of the proof is in Sect. 4. Proofs are in Sects. 5 and 6. A different kind of deterministic speedup, X k+1 = X k + X k−1 + k+1
(mod n),
is analyzed in Sect. 7. The last section has applications and some interesting open questions.
2 Speedup by deterministic functions Let S be a finite set and P = ( pi j )i, j∈S be a Markov transition matrix on S. We assume the following conditions on P: (1) (2) (3) (4)
The Markov chain generated by P is irreducible and aperiodic. If pi j > 0 for some i, j ∈ S, then p ji > 0. For each i ∈ S, pii > 0. The uniform distribution on S is the stationary measure of P. We will call it μ.
In additi
Data Loading...
