TYI 41: How many steps does it take for a simple random walk on the discrete cube to reach the uniform distribution?

Aeiel Yadin’s homepage contains great lecture notes on harmonic functions on groups and on various other topics.

I have a lot of things to discuss and to report; exciting developments in the analysis of Boolean functions; much to report on algebraic, geometric and probabilistic combinatorics following our Oberwolfach summer meeting; much to tell about our Kazhdan seminar on quantum computation and symplectic geometry; a lot of exciting math and TCS activities in Israel; exciting things that Avi Wigderson’s told me on non commutative optimization and moment maps; and, of course, last but not least, the exciting Google supremacy demonstration that I most recently wrote about in my post Gil’s Collegial Quantum Supremacy Skepticism FAQ.  In particular, the unbelievable local-to-global fidelity Formula (77), and (NEW) a poem by Peter Shor for quantum computer skeptics. More poems are most welcome!

With all these excitements, plans, and blog duties it looks that this is the right time to take a pause for a Test Your Intuition post. (Based on chats with Asaf Nachmias, Jonathan Hermon and Itai Benjamini.)

Approaching the uniform distribution on the discrete cube with a lazy simple random walk.

Consider the discrete cube as a graph: the vertices are all the 0-1 vertices of length n , two vertices are adjacent if they differ in one coordinate.

A (lazy) simple random walk is described as follows: You start at the all 0 vertex. At each step when you are at vertex v you stay where you are with probability 1/2 and, with probability 1/2,  you move to a neighbor  of v chosen uniformly at random.

Your position after t steps is a random variable describing a probability distribution D_t on the vertices of the discrete cube. Now, lets fix once and for all the value of \epsilon to be 0.1.

Test your intuition: How many steps T(n) does it take until D_t is \epsilon-close to the uniform distribution U in total variation distance.  (The total variation distance is 1/2 the L^1 distance).

Others measure of proximity

We can also ask: How many steps M(n) does it take until D_t(x) is close to the uniform distribution for every x? Namely, for every x,

(1-\epsilon)/2^n \le D_t(x) \le (1+\epsilon)/2^n

For this question there is a simple analysis based on the coupon collector problem.

We can also consider intermediate measures of proximity, like the entropy:

How many steps H(n) it takes until the entropy of D_t(x) is \epsilon-close to the n the entropy of the uniform distribution?

Let me try now to test your more detailed intuition: For the public opinion poll below we say that X behaves like Y if their ratio tends to one as n tends to infinity, and that X is really smaller than Y if their ratio X/Y tends to a limit smaller than 1.

NEW: Share your knowledge

Let’s try something new: “Share your knowledge (SYK):” What other distances between probability distributions do you recommend? Tell us about them!

A theorem by Ajtai-Komlos-Szemeredi and a problem by Itai Benjamini

Ajtai, Komlos and Szemeredi proved that when you choose every edge of the discrete n-cube with probability greater than 1/n a giant component emerges! Now, choose every edge with probability 2/n  and start a simple random walk from a vertex of the giant component. Itai Benjamini conjectured that it will take roughly n^2 steps to approximately reach the stationary distribution. This seems very difficult.


This entry was posted in Combinatorics, Probability, Test your intuition and tagged , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s