Week 3 - lecture 2

Home » Week 3 - lecture 2

LECTURE presentation

Homework

1.* Let $\{S_n\}$ be simple random walk on the integers, with $S_0=0$ . Show that $P(S_n \ge \ell) \le e^{-\ell^2/(2n)}$ for all $n,\ell \ge 1$ . Hint: Prove the inequality $\cosh(x) \le e^{x^2/2}$ for all real $x$ , and use it to bound $E(e^{\lambda S_n})$ .

2.* Let $T$ be a b-ary tree of height $k$ , that has $1+b+\dots+b^k$ vertices. What are the best upper and lower bounds you can prove for the mixing time of lazy SRW on $T$ ?

3. Let $GL_n(2)$ be the set of invertible $n \times n$ matrices mod 2. Find the cardinality of $GL_n(2)$ . Hint: consider choosing the rows of the matrix one by one.

4.* Let $M$ be a subset of the group of permutations $\bf S_n$ . consider the Markov chain on $\bf S_n$ obtained by picking a permutation $g_n$ in $M$ uniformly at random (independently of previous $g_j$ ), and defining $X_{n}=X_{n-1}g_n$ .

(a) Write a lower bound for the mixing time of this chain in terms of $n$ and $|M|$ .

(b) Suppose that $M$ consists of transpositions. What is the smallest possible size of $M$ for which this chain is irreducible?

(d) Suppose that $M$ consists of all transpositions, and we consider the lazy version of the chain above. Can you improve the lower bound from part (a) in this case?

Reference

[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.

Week 3 - lecture 2

TOP TOPIC

LECTURE presentation

Video lecture

Homework

Reference

Contact Me