Puzzle sobre la votación

Question

Me encontré acerca de este rompecabezas que no estoy seguro de cómo ir sobre.

Supongamos que hay $L$ líderes y $F$ seguidores, con $1 < L<<F$. Un líder hace una decisión binaria, $0$ o $1$ con la misma probabilidad. Cada seguidor de copias de la decisión de uno de los líderes, por simplicidad, la elección de uno de ellos con una distribución uniforme.

El experimento se repite muchas veces, tantas como quieras. Cada seguidor copias el voto de un líder de un número aleatorio de veces $k\in {1, 2, ..., K}$, $K$ igual a algún número entero positivo. Después de eso, el seguidor elige otro líder o el mismo, de nuevo, uniformemente al azar.

Hay algo en la literatura que se puede utilizar para resolver este problema, es decir, identificar o supongo que los líderes son?

Answer 1

Usted puede con una probabilidad de acercarse a $1$ con suficiente eventos, al menos si sabemos que el número de líderes. Para citar números, supongamos $L=3$, pero funciona para cualquier $L$. $\frac 14$ de el tiempo de los líderes estarán todos de acuerdo, entonces el conjunto de la sociedad estará de acuerdo, y no hay ninguna información, por lo que ignorar estos eventos. De lo contrario, habrá dos de una opinión y una de las otras. Lo importante es que los líderes no están de acuerdo por unanimidad. Cualquier otro grupo de tres estarán de acuerdo, a veces, cuando la sociedad no está de acuerdo. Si están todos los seguidores, se pondrán de acuerdo $(\frac 23)^3+(\frac 13)^3=\frac 13$ del tiempo. Dos líderes y un seguidor estará de acuerdo $\frac 13\cdot \frac 23=\frac 29$ del tiempo. Un líder y dos seguidores estarán de acuerdo $\frac 13$, al igual que tres seguidores. A fin de ver los eventos hasta que sólo hay un conjunto de tres que nunca ha aceptado por unanimidad.

Puede determinar $L$. Si $L=3$ (salvo que la votación es unánime) la población se divide acerca de $2-1$. Si $L=4$, $\frac 47$ de las veces no se $3-1$ $\frac 37$ de las veces será incluso. Viendo algunos votos (muchos menos de los que necesita para encontrar los líderes) determinará $L$ con una probabilidad alta.

Answer 2

Un extremadamente rápido y sucio manera de hacerlo, de forma ilimitada observaciones: no seguidor puede ser la única persona de voto 0 en una ronda (o 1), pero que un líder puede ser, y por lo tanto, tarde o temprano, cada líder se mostrará como un lobo solitario en algunos ronda.

Por supuesto, esto ocurre con muy baja probabilidad en cada ronda, por lo que requerirá de muchas rondas para obtener una respuesta completa de esta manera. Precisamente: para un determinado líder, la oportunidad de ser un lobo solitario en una ronda dada es $\frac{1}{2^{L-1}} \left(\frac{L-1}{L}\right)^F$; estos eventos son mutuamente exclusivos para los diferentes líderes, por lo que en una ronda determinada, la probabilidad de que algunos líder es aislado es $\frac{(L-1)^F}{2^{L-1} L^{F-1}}$.