MathDB

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

\forall\varepsilon>0 \,\exists K\, \forall n>1

P(\lambda> K \log n) <\varepsilon

where

\lambda

is the number of steps of the random walk.

Problem Statement