# Transition time in finite voter model

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?

-

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."
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.
Thank you. This is a very elegant and helpful description. I have a few questions. How large can $p$ be before the description breaks down? Also, does your argument also give the mixing time? That is, is it the same as the time to get the first transition from all constant to a new all constant vector? – user32786 May 3 '13 at 13:50