Transition time in finite voter model

Question

I believe the following problem is related to something called the "voter model" in statistics. This is not my area of expertise so please forgive me if the answers turn out to be well known.

Consider a vector $V$ of length $n$ where the elements are integers chosen from $[m]$. At each (discrete) time step we apply the following update rule to $V$.

1. With probability $p$, choose an index $i$ uniformly at random from $[n]$ and set $V_i = x$ where $x$ is uniformly chosen from $[m]$.
2. With probability $1-p$ choose two indices $i$ and $j$ uniformly at random and set $V_i = V_j$. That is copy the value $V_j$ to replace the value $V_i$.

When $p$ is reasonably small (but not too small) the vector spends most of its time as a (more or less) constant vector with all elements the same except for a small number of single indices which change and than change back. It also periodically transitions rapidly to be a different (more or less) constant vector with the same properties.

I am interested in understanding this process in more detail. For example, how long does it spend in each (more or less) constant state (i.e how long until it flips to another one), how long does it spend not in a (more or less) constant state?

Answer 1

From any position, the expected number of steps of type $2$ before the vector is completely constant is at most $(n-1)^2$, with equality if all positions have different values. See "A balls-and-colours problem."

I don't agree with the description that when the vector is close to constant, there are just a small number of single indices which change and then change back. There is no force pushing small minorities to be smaller. It is true that they change location, so if you only watch a small portion of the vector you might only see single indices change and then change back.

After a type 1 move breaks the monotony of a vector, the expected number of type 2 moves before it becomes constant again is $(n-1)H_{n-1}$ where $H_{n-1} = 1 + 1/2 + ... + 1/(n-1) = \log (n-1) + \gamma + o(1)$. With probability $1/n$, the vector has switched to the new value. However, conditioned on switching the transition takes longer. The expected number of type 2 moves it takes to go from all different values to constant is $(n-1)^2$, so by symmetry, the conditional number of type 2 moves it takes for the value in position $1$ to take over against $n-1$ different values is $(n-1)^2$. This is the same as taking over against $n-1$ equal values, so conditioned on a switch, it takes an average of $(n-1)^2$ type 2 moves.

If $p \ll 1/n$ then what you will tend to see is a mutation which usually dies out every $1/p$ steps. If $1/(n \log n) \lt p$ then there will often be multiple mutations alive at the same time. About every $n/p$ steps there is a mutation which will take over. For larger values of $p$, the next successful mutation will often occur before a takeover is complete, and this description breaks down.