Random walk of $k$ particles on a $n$-dimensional hypercube

104 Views Asked by At

I would appreciate your help with the following, if possible.

Consider an $n$-dimensional hypercube where nodes are connected by an edge if they differ in a single bit. There are $k=poly(n)$ particles, all starting in different positions on the hypercube. Their moves are dictated by the following procedure, which is applied to all particles in parallel:

  1. Two different indices $i$ and $j$ are first selected uniformly at random between 1 and $n$.
  2. A random bit $b$ is then selected uniformly at random as well.
  3. For each particle $p$, if the $j$-th coordinate of the particle is equal to $b$, the $i$-th coordinate is flipped and $p$ moves to the new location.

Clearly, if there is only one particle, the particle moves to a new location with probability 1/2, so this corresponds to a lazy walk in the hypercube which converges to the stationary distribution in about $nlogn$ steps.

My main questions are:

a) Can we claim that particles will end up in random locations? Intuitively, we might think that walks are independent but this not true entirely. For example, notice that by the way moves are made, particles cannot end up in the same node (their locations will still be different after each move). But can we still claim randomness under this constraint? Is there anything concrete we can say about the distribution of the particles at the end of the random walk?

b) How many steps are needed to end up in the stationary distribution? Can we still claim that $O(nlogn)$ steps are enough for all particles to end up in random (yet different) positions?

Thank you for your time on this. I remain available for any questions you might have.

TD