rompecabezas de probabilidades - selección de una persona

Question

Hay n personas en una mesa redonda. una de ellas es la cabeza y planea convertir a otra persona del resto en la nueva cabeza. tiene una moneda. lanza la moneda. si obtiene cara da la moneda a la persona de su izquierda y si obtiene cruz da la moneda a la persona de su derecha. cualquiera que reciba la moneda ya no puede convertirse en cabeza. la persona que recibe la moneda repite el procedimiento similar. cuando sólo queda una persona que no ha recibido la moneda, se convierte en cabeza. quien recibe la moneda ya no puede convertirse en cabeza. la persona que recibe la moneda repite el procedimiento similar. cuando sólo queda una persona que no ha recibido la moneda, se convierte en cabeza. cuál es la probabilidad de que cada una de las n-1 personas se convierta en cabeza.

para n = 3, 4 obtenemos una distribución de probabilidad uniforme. ¿cómo resolverlo para n mayores?

He luchado con esto durante algún tiempo pero no he podido resolverlo todavía.

¡parece que te esta costando resolverlo! no pude encontrar la solución en google.

Actualización:

enfoque que estaba utilizando:

  let ai be the probability of that the ith person is not selected.
  summation i:1 to n (1-ai) = 1;
  a1 = 0;
  we need another equation to use the fact that the probability of getting a head on a             
  coin flip is 1/2.
  tried Bayes etc. could not get it.

  try induction

  anything else you might like

Answer 1

La distribución de probabilidad es uniforme. Cada persona P tiene dos vecinos, R y L. Uno es eliminado antes que el otro, digamos R. Entonces la probabilidad de que P sea seleccionado es la probabilidad condicional de que L sea eliminado antes que P, con la moneda empezando en R. Por simetría, esto es lo mismo para cada persona.

Answer 2

El siguiente argumento procede de Nota sobre el último vértice visitado por un paseo aleatorio L. Lovasz, P. Winkler, Journal of Graph Theory, Vol. 17, No. 5, 1993.

Cada persona P tiene dos vecinos R y L. Sea $p$ sea la probabilidad de que partiendo del nodo R visite P en último lugar. Por simetría, $p$ es también la probabilidad de que partiendo del nodo L se visite P en último lugar. También por simetría, $p$ no depende de la persona de partida $P$ - sólo depende de $n$ .

Reclamación: Si tu persona de partida no es P, entonces $p$ es la probabilidad de que P sea visitado en último lugar.

Prueba: Llegará a R o L antes que a P con probabilidad 1. La probabilidad de que $P$ se visita en último lugar es $p$ .

Esto demuestra que la probabilidad de que P sea el último no depende de la persona P, por lo que debe ser $1/(n-1)$ .

Answer 3

Es uniforme para todos los n. Consideremos primero la persona situada inmediatamente a la derecha de la cabeza. La probabilidad de que llegue el último se puede calcular utilizando la teoría del paseo aleatorio como 1/(n-1). El mismo argumento sirve para la persona situada inmediatamente a la izquierda de la cabeza.

Ahora considere a alguien en una posición arbitraria (no al lado de la cabeza) No puede recibir la moneda antes que la persona de su derecha y antes que la persona de su izquierda. llámele k , a la persona de su izquierda k-1 y a la persona de su derecha k+1. Entonces P[k es el último]= P[K+1 antes que k-1 antes que k]+P[k-1 antes que k+1 antes que k] =P[k+1 antes que k-1]/(n-1)+P[k-1 antes que k+1]/(n-1) esto se debe a que una vez k-1 o K+1 lo consigue estaban en la posición en la persona inmediatamente a la derecha en la cabeza.

\=1/(n-1)

Answer 4

Se trata de responder a una pregunta planteada por unknown: en el caso asimétrico en el que la moneda se mueve en el sentido de las agujas del reloj con probabilidad $p$ y en sentido contrario a las agujas del reloj con probabilidad $1-p$ se encuentra la nueva cabeza $k$ escaños alejados del antiguo jefe, contando los escaños en el sentido de las agujas del reloj, con probabilidad $r^k(r-1)/(r^n-r)$ para cada $1\le k\le n-1$ donde $r=(1-p)/p$ . (Cuando $p\to1/2$ , $r\to1$ y el límite es efectivamente uniforme, es decir, igual a $1/(n-1)$ para cada $k$ .)

Answer 5

He escrito un artículo sobre este juego, y lo resolvió numéricamente para el caso de 10 personas. Calculé que la probabilidad es la misma para cada una de las 9 personas.

En resumen, he definido lo siguiente:

Sea P(n,i,j,k) la probabilidad de que en la n-ésima ronda, la persona k tenga la moneda, mientras que las personas desde i contando en el sentido de las agujas del reloj hasta k hayan recibido todas la moneda antes.

Y se formulan 3 ecuaciones de recurrencia:

$P (n+1,i,j,k)= \frac{1}{2} P (n,i,j,k-1)+ \frac{1}{2} P (n,i,j,k+1)$ ........(1)

$P (n+1,i,j,j)=\frac{1}{2} P (n,i,j-1,j-1)+ \frac{1}{2} P(n,i,j,j-1)$ ........(2)

....(3)

Para más detalles, consulte:

Resolver un juego de probabilidades mediante ecuaciones de recurrencia y python

En este artículo, a(n,i), que denota la probabilidad de que la i-ésima persona sea la cabeza en la n-ésima ronda, también se encuentra y se representa gráficamente.