Asymptotic Analysis of a Random Walk on a Hypercube With Many Dimensions

P. Diaconis and R.L. Graham have recently considered a random walk on an n-dimensional cube, starting at the origin. At each step, the probability of a change in the i sup (th) coordinate only is 1/(n+1), i=1,...,n, and the probability of no change is also 1(n+1). They obtained an explicit expression for P sub n (w), the probability of being at a point x of weight w after N steps. In this paper P sub N (w) is expressed as a contour integral and an asymptotic approximation to it is derived by the saddle point method, when n >> 1, w = pn, 0 p. From this, the limiting crossover point, corresponding to W = max(w | P sub N (w) >= 2 sup (-n)), as n -> approaches infinity, is obtained. Also, for 4lambda = log(bn), where 0 Erf[8b) sup (-1/2)], as n -> approaches infinity.