(a) Let . For , let be the first time at which a simple symmetric random walk on with initial position at time 0 hits 0 or . Show . [If you use a recursion relation, you do not need to prove that its solution is unique.]
(b) Let be a simple symmetric random walk on starting at 0 at time . For , let be the first time at which has visited distinct vertices. In particular, . Show for . [You may use without proof that, conditional on , the random variables have the distribution of a simple symmetric random walk starting at .]
(c) For , let be the circle graph consisting of vertices and edges between and where is identified with 0 . Let be a simple random walk on starting at time 0 from 0 . Thus and conditional on the random variable is with equal probability (identifying with ).
The cover time of the simple random walk on is the first time at which the random walk has visited all vertices. Show that .