The Library

Optimal co-adapted coupling for the symmetric random walk on the hypercube

Tools

Connor, Stephen B. and Jacka, Saul D.. (2008) Optimal co-adapted coupling for the symmetric random walk on the hypercube. Journal of Applied Probability, Vol.45 (No.3). pp. 703-713. ISSN 0021-9002

PDF
WRAP_Jacka_8473264-st-211209-optimal-jap.pdf - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
Download (251Kb)

Official URL: http://dx.doi.org/10.1239/jap/1222441824

Abstract

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.

Item Type:	Journal Article
Subjects:	Q Science > QA Mathematics
Divisions:	Faculty of Science > Statistics
Library of Congress Subject Headings (LCSH):	Stochastic control theory, Markov processes, Random walks (Mathematics), Hypercube
Journal or Publication Title:	Journal of Applied Probability
Publisher:	Applied Probability Trust
ISSN:	0021-9002
Official Date:	September 2008
Volume:	Vol.45
Number:	No.3
Page Range:	pp. 703-713
Identification Number:	10.1239/jap/1222441824
Status:	Peer Reviewed
Access rights to Published version:	Open Access
References:	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. Mathematical Reviews (MathSciNet): MR770418 Zentralblatt MATH: 0514.60067 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. Mathematical Reviews (MathSciNet): MR1068491 Feller, W. (1971). An Introduction to Probability Theory and Its Applications, vol. II, 2nd edn. John Wiley, New York. Mathematical Reviews (MathSciNet): MR270403 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. Mathematical Reviews (MathSciNet): MR885462 Digital Object Identifier: doi:10.1007/BF00354033 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. Mathematical Reviews (MathSciNet): MR890287 Digital Object Identifier: doi:10.1007/BF00318710 Griffeath, D. (1975). A maximal coupling for Markov chains. Z. Wahrscheinlichkeitsth. 31, 95--106. Mathematical Reviews (MathSciNet): MR370771 Digital Object Identifier: doi:10.1007/BF00539434 Harison, V. and Smirnov, S. N. (1990). Jonction maximale en distribution dans le cas Markovien. Prob. Theory Relat. Fields 84, 491--503. Mathematical Reviews (MathSciNet): MR1042062 Digital Object Identifier: doi:10.1007/BF01198316 Krylov, N. V. (1980). Controlled Diffusion Processes (Appl. Math. 14). Springer, New York. Mathematical Reviews (MathSciNet): MR601776 Lindvall, T. (2002). Lectures on the Coupling Method. Dover, New York. Mathematical Reviews (MathSciNet): MR1924231 Zentralblatt MATH: 1013.60001 Matthews, P. (1987). Mixing rates for a random walk on the cube. SIAM J. Algebraic Discrete Methods 8, 746--752. Mathematical Reviews (MathSciNet): MR918073 Digital Object Identifier: doi:10.1137/0608060 Pitman, J. W. (1976). On coupling of Markov chains. Z. Wahrscheinlichkeitsth. 35, 315--322. Mathematical Reviews (MathSciNet): MR415775 Digital Object Identifier: doi:10.1007/BF00532957 Sverchkov, M. Y. and Smirnov, S. N. (1990). Maximal coupling of D-valued processes. Soviet Math. Dokl. 41, 352--354. Mathematical Reviews (MathSciNet): MR1072656
URI:	http://wrap.warwick.ac.uk/id/eprint/2491