¿Es la probabilidad $\frac12$?

Question

He a $n$ jugadores en total. Tenga en cuenta que $n$ es incluso. Queremos recoger $\frac n2$ jugadores uniformemente al azar. Tenemos acceso a un solo imparcial de la moneda. Queremos hacer de este interseccion en el mínimo número esperado de lanzar una moneda. ¿Qué debo hacer?

Mi enfoque: voy a seguir tirando-si es que H voy a añadir que el jugador del equipo Una persona para el equipo B. Si ya hay $\frac n2$ jugadores de cualquier equipo, yo deje de dar vueltas y poner el resto en otro equipo. Dejando de lado el problema de la prueba de por qué esto le dará un número mínimo de lanzamientos, no estoy seguro de por qué los jugadores tienen la misma probabilidad de llegar a el equipo a o B. es claro para la primera $\frac n2$ jugadores pero después de que se pone un poco desordenado.

Por favor, no digas que es simétrica, así que la probabilidad es la mitad de la trivialidad.

Answer 1

Paso 1: Establezca $k={n\choose n/2}$.

Paso 2: Elegir un número entero entre $1$$k$, uniformemente al azar con su moneda. Este es un problema bien conocido, por ejemplo, aquí. Si $k$ pasa a ser un poder de $2$ se puede hacer en un número finito de volteretas; de lo contrario, el número de lanzamientos es ilimitado (pero muy poco probable que sea grande) o su distribución no es precisamente uniforme (pero muy cerca).

Paso 3: Elegir el subconjunto de tamaño $n/2$, sobre la base del resultado del paso 2, y un orden lexicográfico de los subconjuntos. Por ejemplo, si $n=4$ y los jugadores se $A,B,C,D$, entonces el primer subconjunto se $AB$, el segundo es $AC$, etc.

Answer 2

No puede hacerse con un número finito de lanzamientos en todos. Si $n=4$, entonces hay $\binom42=6$ posible bi-secciones, por lo que la probabilidad de cada bisección $\frac16$, que no es una suma de potencias de $\frac12$.

Se podría considerar un protocolo con una cantidad ilimitada de lanza y luego pedir un protocolo que reduce al mínimo el número esperado de lanzamientos. O un protocolo que maximiza la probabilidad de ser hecho tan pronto como sea posible, o algo como eso.

Answer 3

Vamos a trabajar de ello para $n=4.$ Tenemos al menos dos volteretas y no más de tres, porque en el momento en $n-1$ de los jugadores han sido colocadas en los equipos de un equipo va a estar lleno y el último jugador del equipo ya estará determinada. Vamos $X_1,$ $X_2,$ y $X_3$ (si es necesario) ser los resultados de los tirones en ese orden. Vamos a considerar en primer lugar los dos primeros lanzamientos, y para cada uno de los casos tienen en cuenta el resto de los flip, si es necesario.

Caso $X_1 = H, X_2 = H.$, a Continuación, los jugadores de $1$ $2$ ir en equipo $A$, y el de los otros jugadores van en equipo $B$; el resultado es $AABB,$ con una probabilidad de $\frac14.$

Caso $X_1 = T, X_2 = T.$, a Continuación, los jugadores de $1$ $2$ ir en equipo $B$, y el de los otros jugadores van en equipo $A$; el resultado es $BBAA,$ con una probabilidad de $\frac14.$

Caso $X_1 = H, X_2 = T.$, a Continuación, los jugadores de $1$ $2$ ir en equipos de $A$ $B,$ respectivamente, y tenemos que voltear de nuevo. Esto produce dos sub-casos:

• $X_1 = H, X_2 = T, X_3=H.$ El resultado es: $ABAB,$ con una probabilidad de $\frac18.$
• $X_1 = H, X_2 = T, X_3=T.$ El resultado es: $ABBA,$ con una probabilidad de $\frac18.$

Caso $X_1 = T, X_2 = H.$, a Continuación, los jugadores de $1$ $2$ ir en equipos de $B$ $A,$ respectivamente, y tenemos que voltear de nuevo. Esto produce dos sub-casos:

• $X_1 = T, X_2 = H, X_3=H.$ El resultado es: $BAAB,$ con una probabilidad de $\frac18.$
• $X_1 = T, X_2 = H, X_3=T.$ El resultado es: $BABA,$ con una probabilidad de $\frac18.$

Observar que para el jugador número $k,$ cualquier $k$ tal que $1 \leq k \leq n,$ para cada secuencia de volteretas que los lugares reproductor $k$ equipo $A$ hay otra secuencia de lanzamientos de la misma longitud (y la misma probabilidad) de que los lugares reproductor $k$ equipo $B.$ Por lo tanto, reproductor de $k$ tiene la misma probabilidad (específicamente, $\frac12$) en cualquiera de los equipos. Esto es cierto en general para cualquier $n,$ no sólo para $n=4.$

Pero observe que hay dos resultados ( $AABB$ $BBAA$ ) que en lugar de los jugadores de $1$ $2$ en el mismo equipo, y el evento que consta de estos dos resultados se ha probabilidad de $\frac12$; mientras que los resultados que poner jugadores a $2$ $3$ en el mismo equipo ( $BAAB$ $ABBA$ ) constituyen un evento cuya probabilidad es $\frac14.$

El criterio acerca de cada jugador que ha $\frac12$ de probabilidad de estar en cualquiera de los dos equipos es sólo una pequeña parte de lo que consideramos como la uniformidad de la selección aleatoria de los jugadores para los equipos. Después de todo, podemos lograr la $\frac12$ probabilidad al lanzar una moneda y asignar el resultado a $AABB$ a los jefes y $BBAA$ a las colas. Por eso yo preferiría una distribución uniforme sobre todos los $\binom{n}{n/2}$ posibles listas de tareas, como se discutió en las otras respuestas.

Answer 4

Para hacer los números enteros, vamos a 2k = n. Si ha asignado una a los jugadores del equipo a y b, los jugadores del equipo B, entonces usted tiene k-a la izquierda para el equipo a y k-b a la izquierda para el equipo B. El siguiente jugador debe, por tanto, tienen probabilidad (k-a)/(2k-a-b) probabilidad de ser asignado para el equipo A. El método más simple es encontrar el más pequeño de p tales que 2^p >= 2k-a-b, de la vuelta a la moneda p veces, convertir el resultado en binario, asignar a Un equipo si el resultado es <= k-a, asignar a un equipo de la B si el resultado es entre k-a+1 y 2k-a-b, y repetir de otra manera. A partir de allí, el de la fruta que cuelga baja de dividir a cabo por el mcd de k-y k-b.

Más mejoras, sin embargo, son más complicados. Supongamos que k=5. El primer jugador puede ser asignado por un tirón de la moneda. El siguiente debe tener un 4/9 oportunidad para que un equipo y 5/9 para el otro. Así que usted puede voltear la moneda cuatro veces, convertir a binario, y los envían a un equipo por 1-4 y la otra para los de 5-9. 10-16 resultará en una repetición, por lo que hay siete resultados que se "desperdicia". Pero si tienes la mala suerte de tener que repetir, entonces hay 49 formas que puede suceder (7*7), y se puede se puede dividir esos 49 posibilidades en cinco grupos de 9 personas con 4 a la izquierda. Tan sólo esas 4 son un desperdicio. Si se lanza la moneda cuatro veces más y conseguir uno de los 7 "pérdida" de posibilidades, se puede multiplicar por el 4 desperdiciado y conseguir 28, que se puede dividir en tres grupos de 9 con 1 a la izquierda. Y así sucesivamente.