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

Dates:

Date	Event
September 2008	Published

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