Week 4 - lecture 1
Week 3 - lecture 2
1.* Let be simple random walk on the integers, with . Show that for all . Hint: Prove the inequality for all real , and use it to bound . 2.* Let be a b-ary tree of height , that has vertices. What are the best upper and lower bounds you can prove for the […]
Week 3 - lecture 1
Week 2 - lecture 2
1.* Let be simple random walk on the hypercube , and let denote the Hamming weight (i.e., the number of ones) of . Then is also a Markov chain, with transition probabilities and for . Read about projected (or lumped) chains on pages 23-25 of the textbook, and calculate for . Hint: it suffices […]
Week 2 - lecture 1
Week 1 - lecture 2
1. A connected graph is a tree if it contains no cycles. Show that every finite tree with at least two vertices must have at least two leaves. (a leaf is a vertex of degree 1). 2. A vertex coloring of a graph is called proper if every pair of adjacent vertices are assigned different […]