๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Stratified random walks on the n-cube

โœ Scribed by F. R. K. Chung; R. L. Graham

Publisher
John Wiley and Sons
Year
1997
Tongue
English
Weight
226 KB
Volume
11
Category
Article
ISSN
1042-9832

No coin nor oath required. For personal study only.

โœฆ Synopsis

In this paper we present a method for analyzing a general class of random

ลฝ

. walks on the n-cube and certain subgraphs of it . These walks all have the property that the transition probabilities depend only on the level of the point at which the walk is. For these walks, we derive sharp bounds on their mixing rates, i.e., the number of steps required to ลฝ . guarantee that the resulting distribution is close to the uniform stationary distribution.

๐Ÿ“œ SIMILAR VOLUMES

Random minimal spanning tree and percola
Random minimal spanning tree and percolation on the N-cube
โœ Mathew D. Penrose ๐Ÿ“‚ Article ๐Ÿ“… 1998 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 251 KB ๐Ÿ‘ 1 views

The N-cube is a graph with 2 N vertices and N 2 Ny1 edges. Suppose indepen- dent uniform random edge weights are assigned and let T be the spanning tree of minimal ลฝ . y 1 N ฯฑ y3 total weight. Then the weight of T is asymptotic to N 2 ร i as N ยช ฯฑ. Asymp-is1 totics are also given for the local stru

Derangements on the n-cube
Derangements on the n-cube
โœ William Y.C. Chen; Richard P. Stanley ๐Ÿ“‚ Article ๐Ÿ“… 1993 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 599 KB

Chen, W.Y.C. and R.P. Stanley, Derangements on the n-cube, Discrete Mathematics 115 (1993) 65-15. Let Q. be the n-dimensional cube represented by a graph whose vertices are sequences of O's and l's of length n, where two vertices are adjacent if and only if they differ only at one position. A k-dime

Subcube Coverings of Random Spanning Sub
Subcube Coverings of Random Spanning Subgraphs of the n-Cube
โœ Karl Weber ๐Ÿ“‚ Article ๐Ÿ“… 1985 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 896 KB

Let G(n, p ) denote the probability space consisting of all spanning subgraphs g of the n-cube En, and the probability is defined as ERDOS and SPENCER investigated the connectedness of such random graphs for fixed probability p , O<p<l (cf. [l]). I n this paper we study coverings of the vertex set

Asymptotic normality of subcubes in rand
Asymptotic normality of subcubes in random subgraphs of the n-cube
โœ Urzula Konieczna ๐Ÿ“‚ Article ๐Ÿ“… 1993 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 275 KB

We consider two types of random subgraphs of the n-cube. For these models we study the asymptotic behaviour of the number of d-cubes when d = 1,2,