Hostname: page-component-78c5997874-fbnjt Total loading time: 0 Render date: 2024-11-09T09:25:50.846Z Has data issue: false hasContentIssue false
  • English
  • Français

Optimal Co-Adapted Coupling for the Symmetric Random Walk on the Hypercube

Part of: Markov processes Stochastic systems and control

Published online by Cambridge University Press:  14 July 2016

Stephen Connor  and
Saul Jacka
Stephen Connor*
Affiliation:
University of Warwick
Saul Jacka*
Affiliation:
University of Warwick
*
∗Postal address: Department of Statistics, University of Warwick, Coventry CV4 7AL, UK.
∗Postal address: Department of Statistics, University of Warwick, Coventry CV4 7AL, UK.
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Let X and Y be two simple symmetric continuous-time random walks on the vertices of the n-dimensional hypercube, Z2n. We consider the class of co-adapted couplings of these processes, and describe an intuitive coupling which is shown to be the fastest in this class.

Keywords

Optimal couplingco-adaptedstochastic minimumhypercube

MSC classification

Secondary: 93E20: Optimal stochastic control 60J27: Continuous-time Markov processes on discrete state spaces
Type
Research Article
Information
Journal of Applied Probability , Volume 45 , Issue 3 , September 2008 , pp. 703 - 713
Copyright
Copyright © Applied Probability Trust 2008 

References

[1] Aldous, D. (1983). Random walks on finite groups and rapidly mixing Markov chains. In Seminar on Probability XVII (Lecture Notes Math. 986), Springer, Berlin, pp. 243–297.Google Scholar
[2] Diaconis, P., Graham, R. L. and Morrison, J. A. (1990). Asymptotic analysis of a random walk on a hypercube with many dimensions. Random Structures Algorithms 1, 51–72.CrossRefGoogle Scholar
[3] Feller, W. (1971). An Introduction to Probability Theory and Its Applications, Vol. II, 2nd edn. John Wiley, New York.Google Scholar
[4] Greven, A. (1987). Couplings of Markov chains by randomized stopping times. I. Couplings, harmonic functions and the Poisson equation. Prob. Theory Relat. Fields 75, 195–212.CrossRefGoogle Scholar
[5] Greven, A. (1987). Couplings of Markov chains by randomized stopping times. II. Short couplings for O-recurrent chains and harmonic functions. Prob. Theory Relat. Fields 75, 431–458.CrossRefGoogle Scholar
[6] Griffeath, D. (1975). A maximal coupling for Markov chains. Z. Wahrscheinlichkeitsth. 31, 95–106.CrossRefGoogle Scholar
[7] Harison, V. and Smirnov, S. N. (1990). Jonction maximale en distribution dans le cas Markovien. Prob. Theory Relat. Fields 84, 491–503.CrossRefGoogle Scholar
[8] Krylov, N. V. (1980). Controlled Diffusion Processes (Appl. Math. 14). Springer, New York.CrossRefGoogle Scholar
[9] Lindvall, T. (2002). Lectures on the Coupling Method. Dover, New York.Google Scholar
[10] Matthews, P. (1987). Mixing rates for a random walk on the cube. SIAM J. Algebraic Discrete Methods 8, 746–752.CrossRefGoogle Scholar
[11] Pitman, J. W. (1976). On coupling of Markov chains. Z. Wahrscheinlichkeitsth. 35, 315–322.CrossRefGoogle Scholar
[12] Sverchkov, M. Y. and Smirnov, S. N. (1990). Maximal coupling of D-valued processes. Soviet Math. Dokl. 41, 352–354.Google Scholar