Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
add comment

1 Answer

up vote 2 down vote accepted

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.

share|improve this answer
    
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
    
Or.. is the mixing time much more work to establish do you think? –  user32786 May 5 '13 at 8:15
    
@marshall: I'm not sure. I have to think about it more. –  Douglas Zare May 5 '13 at 16:47
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.