Consider $n$ agents labeled $\{1, \dots, n\}$, each holding an arbitrary initial binary opinion $x_i \in \{0,1\}$. We study the \emph{minority dynamics}, in which, at each round, each agent $i$ samples $k$ opinions uniformly at random from $\{x_1, \dots, x_n\}$, and then replaces $x_i$ with the \emph{least common} value among the sampled opinions. The minority dynamics is of interest in computer science and distributed algorithms due to its connection with the \emph{bit-dissemination problem}, which models information spread in biological systems.

This process was previously analyzed in \cite{sodapaper}, where it was shown that if $k = \Omega(\sqrt{n \log n})$ and $k \le n/2$, the system converges to a unanimous state (all 0's or all 1's) within $O(\log^2 n)$ rounds with high probability.

In this work, we analyze the minority dynamics for \emph{polylogarithmic sample sizes}, i.e., $k = \Omega(\mathrm{polylog}(n))$, and show that consensus is still reached rapidly, in $O(\mathrm{polylog}(n))$ rounds with high probability. The chaotic and non-monotone nature of the minority dynamics makes its analysis depart significantly from that of previously studied consensus dynamics in similar settings, as it precludes the identification of a natural potential function to measure progress toward consensus.