𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A note on the last new vertex visited by a random walk

✍ Scribed by Lászlo Lovász; Peter Winkler

Publisher
John Wiley and Sons
Year
1993
Tongue
English
Weight
200 KB
Volume
17
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

A “cover tour” of a connected graph G from a vertex x is a random walk that begins at x, moves at each step with equal probability to any neighbor of its current vertex, and ends when it has hit every vertex of G. The cycle C~n~ is well known to have the curious property that a cover tour from any vertex is equally likely to end at any other vertex; the complete graph K~n~ shares this property, trivially, by symmetry. Ronald L. Graham has asked whether there are any other graphs with this property; we show that there are not. © 1993 John Wiley & Sons, Inc.

📜 SIMILAR VOLUMES

On the fragmentation of a torus by rando
On the fragmentation of a torus by random walk
✍ Augusto Teixeira; David Windisch 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 413 KB

## Abstract We consider a simple random walk on a discrete torus \input amssym $({\Bbb Z}/N{\Bbb Z})^d$ with dimension __d__ ≥ 3 and large side length __N__. For a fixed constant __u__ ≥ 0, we study the percolative properties of the vacant set, consisting of the set of vertices not visited by the r

On the Distribution of the Area Enclosed
On the Distribution of the Area Enclosed by a Random Walk onZ2
✍ James A Mingo; Alexandru Nica 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 475 KB

Let 1 2n be the set of paths with 2n steps of unit length in Z 2 , which begin and end at (0, 0). For # # 1 2n , let area(#) # Z denote the oriented area enclosed by #. We show that for every positive even integer k, there exists a rational function R k with integer coefficients, such that: We calc

A Note on an Addendum to the Confidentia
A Note on an Addendum to the Confidentiality Guaranteed under Randomized Response Sampling by Mahmood, Singh, and Horn
✍ Horng-Jinh Chang; Kuo-Chung Huang 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 48 KB 👁 1 views

Singh (1999) suggested a safe randomized response technique to deal with quantitative sensitive characters through Moors' (1971) strategy, but the variance and percent relative efficiency of the estimator of population mean seem to be incorrect. This note corrects them, and finds Singh's strategy is