Puzzle about voting

Question

I came across about this puzzle which I'm not sure how to go about.

Suppose there are $L$ leaders and $F$ followers, with $1 < L<<F$. A leader makes a binary decision, $0$ or $1$ with same probability. Each follower copies the decision of one of the leaders, for simplicity, choosing one of them with uniform distribution.

The experiment is repeated many times, as many as you like. Every follower copies the vote of a leader for a random number of times $k\in {1, 2, ..., K}$, with $K$ equal to some positive integer. After that, the follower chooses another leader or the same, again, uniformly at random.

Is there anything in the literature that can be used to solve this problem, that is, to identify or guess who the leaders are?

Answer 1

You can with probability approaching $1$ with sufficient events, at least if we know the number of leaders. To quote numbers, let us assume $L=3$, but it works for any $L$. $\frac 14$ of the time the leaders will all agree, then the whole society will agree, and there is no information, so ignore these events. Otherwise, there will be two of one opinion and one of the other. The critical thing is that the leaders do not all agree unanimously. Any other group of three will agree sometimes when the society disagrees. If they are all followers, they will agree $(\frac 23)^3+(\frac 13)^3=\frac 13$ of the time. Two leaders and a follower will agree $\frac 13\cdot \frac 23=\frac 29$ of the time. A leader and two followers will agree $\frac 13$ like three followers. So watch the events until there is only one set of three that has never agreed unanimously.

You can determine $L$ as well. If $L=3$ then (unless the vote is unanimous) the population will split about $2-1$. If $L=4$, then $\frac 47$ of the time it will be $3-1$ and $\frac 37$ of the time it will be even. Watching some votes (many fewer than needed to find the leaders) will determine $L$ with high probability.

Answer 2

An extremely quick and dirty way to do it, given unlimited observations: no follower can ever be the only person voting 0 in a given round (or 1), but a leader can be, and so sooner or later, each leader will show up as a lone wolf in some round.

Of course, this will occur with very low probability in each round, so it will take many rounds to get a full answer this way. Precisely: for a given leader, the chance of being a lone wolf in a given round is $\frac{1}{2^{L-1}} \left(\frac{L-1}{L}\right)^F$; these events are mutually exclusive for different leaders, so in a given round, the probability that some leader is isolated is $\frac{(L-1)^F}{2^{L-1} L^{F-1}}$.