The Library
Optimal co-adapted coupling for the symmetric random walk on the hypercube
Tools
Tools
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
![[img]](http://wrap.warwick.ac.uk/style/images/fileicons/application_pdf.png) |
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 |
| 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 |
Data sourced from Thomson Reuters' Web of Knowledge
Actions (login required)
 |
View Item |
