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 , 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 you stay where you are with probability 1/2 and, with probability 1/2, you move to a neighbor of chosen uniformly at random.

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

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

### Others measure of proximity

We can also ask: How many steps * M(n)* does it take until is close to the uniform distribution

*for every*? Namely, for every ,

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 is -close to the 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 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 -cube with probability greater than a giant component emerges! Now, choose every edge with probability and start a simple random walk from a vertex of the giant component. Itai Benjamini conjectured that it will take roughly steps to approximately reach the stationary distribution. This seems very difficult.