4
$\begingroup$

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 !

Improve this question
$\endgroup$
3
  • $\begingroup$ This looks like the sort of thing that R. Graham et al would have studied at Bell Labs. Does a paper such as www-stat.stanford.edu/~cgates/PERSI/papers/… provide any guidance? $\endgroup$
    – Benjamin Dickman
    Commented Mar 15, 2013 at 21:27
  • $\begingroup$ "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. $\endgroup$
    – Hugh Thomas
    Commented Mar 16, 2013 at 0:42
  • $\begingroup$ 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. $\endgroup$
    – Douglas Zare
    Commented May 18, 2013 at 22:56

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .