Timeline for Random walk on the hypercube
Current License: CC BY-SA 3.0
4 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 18, 2013 at 22:56 | comment | added | Douglas Zare | 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. | |
| Mar 16, 2013 at 0:42 | comment | added | Hugh Thomas | "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. | |
| Mar 15, 2013 at 21:27 | comment | added | Benjamin Dickman | 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? | |
| Mar 15, 2013 at 18:32 | history | asked | user16215 | CC BY-SA 3.0 |