  We study information aggregation in networks when agents interact to learn a
binary state of the world. Initially each agent privately observes an
independent signal which is "correct" with probability $\frac{1}{2}+\delta$ for
some $\delta > 0$. At each round, a node is selected uniformly at random to
update their public opinion to match the majority of their neighbours (breaking
ties in favour of their initial private signal). Our main result shows that for
sparse and connected binomial random graphs $\mathcal G(n,p)$ the process
stabilizes in a "correct" consensus in $\mathcal O(n\log^2 n/\log\log n)$ steps
with high probability. In fact, when $\log n/n \ll p = o(1)$ the process
terminates at time $\hat T = (1+o(1))n\log n$, where $\hat T$ is the first time
when all nodes have been selected at least once. However, in dense binomial
random graphs with $p=\Omega(1)$, there is an information cascade where the
process terminates in the "incorrect" consensus with probability bounded away
from zero.

Computer Science and Game Theory;Discrete Mathematics;Combinatorics