MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $H_N=\{0,1\}^N$ the N-dimensional hypercube. We define the following random walk $X_n$ on $H_N$:

  • start from a point $x \in H_N$
  • pick at random an integer $k$ in $[1,N-1]$ and exchange $x(k)$ and $x(k+1)$
  • go on like that...

For instance, with n=4, the random walk looks like: $X_0=0011$, $X_1=0101$, $x_2=0110$, ...

Do you know any article/textbook where this random walk is studied in details ? I have been looking in many classical textbook without success...

Beyond this general request, I am interested in the following question: take a given point $x^* \in H_N$ and define $d_n$ the Hamming distance between $X_n$ and $x^*$. Is is possible to estimate the mean of the first time when $d_n$ hits $0$ (as a function of $x*$ and the starting point of the chain $X_0$) ? Of course we suppose that $X_0$ and $x^*$ have the same number of ones... I hope you will enjoy this problem.

Thank you !

share|cite|improve this question
This looks like the sort of thing that R. Graham et al would have studied at Bell Labs. Does a paper such as… provide any guidance? – Benjamin Dickman Mar 15 '13 at 21:27
"Go on like that" is not entirely clear to me. Do we pick a new random $k$ at each step? Or do we proceed $k$, $k+1$, ..., which is consistent with the example you gave? Also, I suggest that it will probably help to visualize the problem to think of these 0,1 strings as lattice paths from $(0,0)$ to $(t,n-t)$, where we read 1's as horizontal steps and 0's as vertical steps. The basic swap move which you describe looks at two adjacent steps. If they are both horizontal or both vertical, nothing happens; otherwise, a single box is added or subtracted from the region under the path. – Hugh Thomas Mar 16 '13 at 0:42
One upper bound would be the time to reach a particular permutation by adjacent transpositions in the symmetric group. However, this value should be much lower, since you only need to hit one of $k! (n-k)!$ permutations. – Douglas Zare May 18 '13 at 22:56

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.