Mouse and cat walk randomly (and independently) on the same consistent 8-regular graph with 20 vertices. At the beginning, they are in non-neighboring vertices. When they are in the same vertex, the cat eats the mouse. Explain that the expected number of steps at which the mouse will be eaten is less than
625 · 2^15
I know that average cover time for a random walk over any consistent G graph, for any state initial, is smaller than
e(G) is number of edges in graph and
v(G) is number verticles.
I also have a small hint that this number of steps should be smaller than
8*(e(G)^2)(v(G)^2), but don’t know how to use it and moreover prove it.