A Markov consensus

Question

Consider the following process. You start with $n$ nodes in different colors $c=c1,c2,...$ (representing an opinion). Say, $n=5, c=1,2,3,4,5$. Now each node checks which colors have weak majority (here, all :-) and takes a random one. Say, $c=1,3,3,5,1$. Only $1,3$ have majority. Rinse and repeat: Say, $c=3,3,1,1,3$. Next step, $c=3,3,3,3,3$, we have agreement, stop. Of course now it is interesting how many steps $E$ the process needs in the average (it's VERY fast).

Here are the values of $E$ for $1\leq n \leq 9$ via a simple (ehem) Markov chain calculation: $0,2 ,15/7 ,334/145 ,5575/2404 ,2562531/996556 ,374308417/151539984 ,20507023600358/7758785772837 ,37796077434852247/15034331949432832.$

Clearly the numbers are evil, even the denominators. I would already be content with a much simpler question: What happens if $n\rightarrow\infty$?

a) $E\rightarrow\infty$ (very slowly), since it can hang up in ties arbitrarily often,

b) $E\rightarrow 2$ (very slowly), since it's extremely probable one color has majority due to random fluctuation,

c) $E\rightarrow C$ (very slowly), where $C$ is Reddmann's constant (hey, I want to have something named after me in math, I'm getting old :-) which is about $2.5-2.6$, judging by numeric simulations. (I went until $n=100000$ which is small compared to $\infty$ but my computer is a snail.)

Answer 1

(This is an extended comment, not an answer).

---

Let $X_j$ be the number of votes for the $j$-th candidate in the first turn.

For large $n$, $X_j$ are roughly independent Poisson random variables with mean $1$. More precisely, one can obtain $X_j$ by choosing a random sample $Y_j$ of independent Poisson random variables and then add extra $n - \sum_{j = 1}^n Y_j$ random votes if this quantity is positive, or, otherwise, take away randomly chosen $\sum_{j = 1}^n Y_j - n$ votes. This is minor, as $|n - \sum_{j = 1}^n Y_j|$ is typically of order $O(\sqrt{n})$. (Correct me if I am wrong here).

On average, $n/(e k!)$ of the random variables $Y_j$ are equal to $k$.

If $k$ is extremely large and $e k! \ll n \ll e (k+1)!$, with high probability there will be no $Y_j$ greater than $k$ and there will be roughly $n / (e k!) \gg 1$ of $Y_j$ equal to $k$. This suggests that for such $n$ typically one turn will not be enough: $E \approx 3$.

On the other hand, if $k$ is very large and $n \approx e k!$, then with high probability there will be no $Y_j$ greater than $k$ and there will be roughly one $Y_j$ equal to $k$. Therefore I would expect that for such $n$ the winner will be chosen in one turn: $E \approx 2$. (Edit: exactly one of $Y_j$ is equal to $k$ with probability roughly $1/e$, so one should rather expect $E \approx 3 - 1/e$).

Therefore, my conjecture is: the limit does not really exist!

---

Observe that $e \times 7! < 100000 < e \times 8!$ with $100000/(e \times 7!) \approx 7.3$ and $100000/(e \times 8!) \approx 0.91$. This shows that for $n = 100000$ is somehow in an intermediate regime. (However, $k = 7$ is not very large).

Can you repeat your simulations for $n = 109601 \approx e \times 8!$ and $n = 38750 \approx e \times 7! \times \sqrt{8}$? The former one should lead to $E \approx 2$ (edit: rather $E \approx 3 - 1/e$), while for the latter I expect $E \approx 3$.

---

Edit #2: I did some numerical experiments to support the above claim about non-convergence of $E$. Here is what I got:

This is the plot of the probability of a draw in the first round (which is roughly equal to $E - 2$) against $n$ in the logarithmic scale. Each data point was found by averaging $10^4$ repetitions. Bars correspond to $95\%$ confidence intervals (obtained by approximation by normal distribution). Red vertical lines mark $n = e k!$ for $k = 1, 2, \ldots$

Looks like there is little hope that the Reddmann's constant exists. Good news, however, is that you can have even two of them: the upper and the lower Reddmann's constant (for the $\limsup$ and $\liminf$).