Week 4 - lecture 2


Date: 01/09/22

4.5. Thomson's principle
4.6. Nash-Williams inequality
4.6. Commute Time 

LECTURE presentation

Video lecture


1.* Let \tau be the strong stationary time constructed in class for the reverse riffle shuffle, i.e., the first time that all cards have distinct label vectors. Is \tau optimal? (i.e., does it have minimal expectation among all strong stationary times?)

If not, can you find another strong stationary time with a smaller expectation than \tau? If the answer is positive, can you find a halting state?

2*. Let a and z be opposite corners of an n \times n \times n cube in the 3D lattice. Does the effective resistance between a and z tend to infinity as n \to \infty?

3*. In the 3-1 tree, the root has two children, and for each k \ge 1, half the vertices at level k have three children and the other half have one child. Show that the effective resistance between the root and level n of this tree tends to infinity as n \to \infty.

4. An Oregon professor has n umbrellas, of which initially k \in (0,n) are at her office and n-k are at her home. Every day, the professor walks to the office in the morning and returns home in the evening. In each trip, she takes an umbrella with her only if it is raining. Assume that in every trip between home and office or back, the chance of rain is p \in (0,1), independently of other trips.
(a) Asymptotically, in what fraction of her trips does the professor get wet?
(b) Determine the expected number of trips until all n umbrellas are at the same location.
(c) Determine the expected number of trips until the professor gets wet.


[1] Glasner, Shmuel.
Almost periodic sets and measures on the torus.
Israel J. Math. 32 (1979), no. 2-3, 161–-172.

[2] Berend, Daniel and Peres, Yuval.
Asymptotically dense dilations of sets on the circle.
J. London Math. Soc. (2) 47 (1993), no. 1, 1–-17.

[3] N. Alon and Y. Peres, "Uniform dilations'', Geometric and Functional Analysis, vol. 2, No. 1 (1992), 1–28.

[4] Nair, R. and Velani, S. L.
Glasner sets and polynomials in primes.
Proc. Amer. Math. Soc. 126 (1998), no. 10, 2835–-2840.