Week 9 - lecture 1
Week 8 - lecture 2
1.* Let be an irreducible transition matrix on , and suppose that is nonzero and satisfies . (a) Show that for all odd . (b) Deduce that there is a partition of into two sets such that if , then either and , or and . 2.* Let be an irreducible transition matrix on , […]
Week 8 - lecture 1
Week 7 - lecture 2
Week 7 - lecture 1
Week 6 - lecture 2
1.* (Review problem). Suppose that we move a knight randomly on a standard chess board according to the following rules. Initially, the knight stands on one of the corners of the chess board. Then, at each step, the knight chooses one of the possible moves at random with equal probabilities, independently of what happened before. […]
Week 5 - lecture 1
Week 6 - lecture 1
Week 5 - lecture 2
1.* Let be the transition matrix corresponding to simple random walk on a finite connected graph . Show that for each , we have . Moreover, if the graph is bipartite, then . 2.* Let . Consider a graph which consists of a complete graph on nodes, and a path of length that emanates from […]
Week 4 - lecture 2
1.* Let 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 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 ? If […]