Assign independent standard normally distributed random variables to the vertices of an n-dimensional cube. Say one vertex is greater than another if the assigned number is greater. Define a random walk on the vertices according to the following rules:
a) the starting point is chosen from all the vertices with equal probability,
b) during our journey, if we reach a vertex such that there are adjacent vertices which have higher values, we choose the next vertex with equal probability,
c) if there is none, we stop.
Prove that ∀ε>0∃K∀n>1
P(λ>Klogn)<ε
where λ is the number of steps of the random walk. probability and statsMiklos Schweitzer