Número esperado de personas sentadas en el derecho de los asientos.

Question

Hubo un popular pregunta de la entrevista de hace un tiempo: hay $n$ gente sentado en un avión, y la primera persona que llega y se sienta en un asiento al azar. Todos los demás que viene en cualquiera de los dos se sienta en su asiento, o si su asiento ha sido tomada, se sienta en un azar desocupado el asiento. ¿Cuál es la probabilidad de que la última persona se sienta en su asiento?

La respuesta a esta pregunta es $1/2$ porque todo el mundo busca a sentarse en un asiento al azar tiene la misma probabilidad de estar en la primera persona del asiento como el último de la persona.

Mi pregunta es: ¿cuál es el número esperado de personas que se sientan en su asiento?

Mi opinión: este sería $\sum_{i=1}^n p_i$ donde $p_i$ es la probabilidad de que la persona $i$ se sienta en el asiento derecho..

$X_1 = 1/n$

$X_2 = 1 - 1/n$

$X_3 = 1 - (1/n + 1/n(n-1))$

$X_4 = 1 - (1/n + 2/n(n-1) + 1/n(n-1)(n-2))$

Es esto correcto? Y no generalizar a $X_i$ tener un $\max(0, i-1)$ plazo de $1/n(n-1)$ $\max(0, i-2)$ plazo de $1/n(n-1)(n-2)$ etc?

Gracias.

Answer 1

Lo siento por la segunda respuesta (voy a borrar la primera):

Me tendrá como objetivo mostrar que el número esperado de personas sentadas en sus asientos está dada por:

$$ n-1-\frac12-\frac13-\dots-\frac1{n-1}=n-H_{n-1} $$

Para ello, en primer lugar, encuentre el número esperado de personas en el mal asientos, que vamos a llamar a $s_n$.

Supongamos que el pasajero número $1$ sentado en el asiento $i\ne1$. En este punto, los pasajeros $2,\dots,i-1$ todos se sientan en sus asientos. Ahora tenemos una situación donde no se $n-i+1$ asientos vacíos a la izquierda, y el pasajero $i$ va a sentarse en un asiento al azar.

Esto es muy similar a la situación que tenía al inicio, sólo que con menos asientos. La única diferencia es que el pasajero $i$'s del asiento, y hay un asiento (asiento de $1$) que pertenece a ninguna de las personas de pie.

Esto es un poco de un problema, así que vamos a cambiar las cosas un poco. Vamos a suponer que el número de asiento, $1$ no, de hecho, pertenecen a cualquiera de los pasajeros. Por lo tanto, donde el pasajero $1$ se encuentra, que está en el mal asiento. Vamos a utilizar la carta de $t_n$ para denotar el número esperado de personas sentadas en el mal asiento si el asiento $1$ no pertenecen a nadie.

Lo que ahora recibimos, es que la situación después de que el pasajero $1$ se ha sentado en el asiento de $i\ne1$, y los pasajeros $2,\dots,n-1$ se han sentado en sus asientos es exactamente el mismo ya que la situación en el principio, pero con $n-i+1$ asientos en lugar de $n$: hay un pasajero acerca de elegir un asiento al azar que no pertenecen a él (he decidido que el sexo de los pasajeros $i$ por lanzar una moneda): hay un asiento ($1$) que no pertenecen a nadie, y el resto de los escaños pertenecen al resto de pasajeros. Así que en este punto, se espera que el número de pasajeros sentados en el mal de los asientos es de $1+t_{n-i+1}$: $1$ para el pasajero $1$, que se sentó en el mal asiento, y $t_{n-i+1}$ porque después estamos en la misma situación que antes, pero con $n-i+1$ asientos.

Lo que si el pasajero $1$ sentado en el asiento $1$? Luego el resto de los pasajeros se sientan en el derecho de los asientos, por lo que el número esperado de personas sentadas en el mal de los asientos, al final, es sólo $1$ (recuerde, el pasajero $1$ no posee asiento $1$).

Pasajero $1$ elige entre las $n$ asientos al azar, así que esto nos da la recurrencia:

\begin{align} t_1 &= 1\\ t_n &= 1+\frac1n\sum_{i=2}^nt_{n-i+1} = 1+\frac1n\sum_{i=1}^{n-1}t_i \end{align}

Ahora estamos listos para probar el siguiente:

Reclamo: $t_n=H_n$

Prueba de reclamación: inducción sobre $n$. $\mathbf{n=1}$ : $t_1=1=H_1$.

$\mathbf{n>1}$ : $t_n=1+\frac1n\sum_{i=1}^{n-1}t_i=1+\frac1n\sum_{i=1}^{n-1}H_i$ (por la hipótesis inductiva). Un conocido de identidad que involucra armónica de los números nos dice que:

$$ \sum_{i=1}^{n-1}H_i = nH_{n-1}-(n-1) $$

Así $t_n=1+H_{n-1}-1+\frac1n=H_n$. $\Box$

¿Cómo podemos llegar desde aquí a $s_n$? La diferencia es que ahora pasajero $1$ lo hace propio asiento $1$, lo que significa que la respuesta va a ser menor por $1$ si y sólo si el pasajero $1$ sentado en el asiento $1$. Desde pasajero $1$ sentado en el asiento $1$ con una probabilidad de $\frac1n$, tenemos que restar $\frac1n$ $t_n$ conseguir $s_n$:

$$ s_n=t_n-\frac1n=H_n-\frac1n=H_{n-1} $$

Finalmente, para obtener el número esperado de personas en el derecho de los asientos, restamos $s_n$ $n$ para obtener:

$$ n-H_{n-1} $$

Nota 1: Desde $H_n$ crece logarítmicamente, la proporción de personas que se sientan en sus asientos converge a$1$$n\to\infty$.

Nota 2: me sigue pareciendo que esta prueba bastante insatisfactorio, ya que utiliza la identidad de $\sum_{i=1}^{n-1}H_i = nH_{n-1}-(n-1)$, que yo todavía no entiendo muy bien. Estoy seguro de que es bastante fácil de demostrar por inducción, pero si alguien puede venir para arriba con una buena explicación de por qué funciona, se podría producir aún más impermeable a prueba de este hecho.

Answer 2

Su enfoque general se ve técnicamente correcta, usando la linealidad de la expectativa de contar y, a continuación, escribir una fórmula para cada una de las $p_i$ (aunque parece que cambia la notación y comenzó a usar el $X_i$ en las fórmulas en lugar de $p_i$). Sin embargo creo que la ecuación de $X_4$ es decir $p_4$ es en realidad

$$X_4 = 1 - (1/n + 1/n(n-1) + 1/n(n-2) + 1/n(n-1)(n-2))$$

y la generalización de $X_i$ arbitrarias $i$ es obtenida por el razonamiento básico, sólo escribir la probabilidad de que cada forma de la $i$ª persona del asiento ya podrían ser adoptadas, teniendo en cuenta cada caso, por ejemplo, para $X_4$ el plazo $1/n(n-2)$ corresponde al caso de que la primera persona que toma la tercera persona del asiento, y la tercera persona toma la cuarta persona del asiento. No estoy seguro de si/lo que es una fórmula fácil sería que cuando se suman todas las $X_i$ términos para obtener la respuesta total. Sin embargo es fácil ver que la regla general para obtener la ecuación de $X_i$ al $i > 1$ han $X_i = 1 - q_i$ donde $q_i$ es la suma de todos los términos que usted puede hacer de la forma $1/n(n-k_1)(n-k_2)\ldots$ donde ha $0$ o más distintos valores de $k_j$, e $k_1 < k_2 \ldots < i-1$.

Answer 3

He encontrado esta pregunta y la respuesta podría ser relevante.

Asientos de $n$ de las personas con entradas en $n+k$ sillas con la 1ª persona que toma un asiento al azar

La respuesta de los estados que la probabilidad de que una persona no está sentado en su asiento es $\frac{1}{k+2}$ donde $k$ es el número de asientos a la izquierda después de que él toma asiento. Esto tiene sentido porque para la persona $i$, si alguien se sienta en sillas de $1, i+1, ... n$ entonces él debe sentarse en su propia silla, por lo que la probabilidad de que esto ocurra es $\frac{n-i+1}{n-i+2}$. Por lo $k = 0$ durante la última persona y $k = n-1$ para la segunda persona. La respuesta, a continuación, sólo debe ser

$1/n + \sum_{i = 2}^{n} \frac{n-i+1}{n-i+2}$

Answer 4

Respuesta correcta a la pregunta incorrecto: por favor, consulte la segunda respuesta

La respuesta es $\frac{1}{2}$ como se dijo.

El patrón general es que para $n$ de la gente, hay un $\frac{1}{n}$ de probabilidad de éxito, $\frac{1}{n}$ probabilidad de fracaso, y un $\frac{n-2}{n}$ de probabilidad de que el problema se repite en el $n-1$ de la escala.

Caso $n=2$: La probabilidad de que la primera recoge el correcto asiento de la es $\frac{1}{2}$, y, a continuación, la última persona que se sienta en la sede apropiada con probabilidad 1. La probabilidad de que la primera recoge el mal asiento es $\frac{1}{2}$, y, a continuación, la última persona que se encuentra en buen asiento con una probabilidad de 0. Por lo que la probabilidad total es de: $$ \frac{1}{2}\cdot1+\frac{1}{2}\cdot0=\frac{1}{2} $$

Caso $n=3$: La probabilidad de que la primera recoge el correcto asiento de la es $\frac{1}{3}$, y, a continuación, la última persona que se sienta en la sede apropiada con probabilidad 1. La probabilidad de que la primera recoge la última persona en el asiento del es $\frac{1}{3}$, y, a continuación, la última persona que se encuentra en buen asiento con una probabilidad de 0. La probabilidad de que la primera recoge la media persona en el asiento del es $\frac{1}{3}$, y ahora hay un $\frac{1}{2}$ que la segunda persona elige el último asiento o en el primer asiento (Caso 2), ya que dos no-pasado la gente de conmutación asientos significa que todos los demás tiene su propio asiento. Así: $$ \frac{1}{3}\cdot1+\frac{1}{3}\cdot0+\frac{1}{3}\cdot\frac{1}{2} = \frac{2}{6} + \frac{1}{6} = \frac{3}{6} = \frac{1}{2} $$

Prueba por inducción.

Supongamos que es cierto para $n$ que la probabilidad de que la última persona que se sienta en la sede apropiada es $\frac{1}{2}$. Ahora bien, si hay $n+1$ de la gente, tenemos una $\frac{1}{n+1}$ de probabilidad de que el último asiento de la probabilidad es 1 (correcta del asiento), $\frac{1}{n+1}$ de probabilidad de que el último asiento de la probabilidad es 0 (último asiento), y un $\frac{n-1}{n+1}$ de probabilidad de que la probabilidad es $\frac{1}{2}$, ya que sabemos que el $n$ de los casos. $$ \frac{1}{n+1} + \frac{0}{n+1} + \frac{n-1}{2(n+1)}\\ =\frac{2}{2(n+1)}+\frac{n-1}{2(n+1)}\\ =\frac{n+1}{2(n+1)}\\ =\frac{1}{2} $$ QED

Answer 5

Ahora que he limpiado mis gafas, voy a tratar de nuevo. Gracias, Señor Farin.

Algunas observaciones.

La respuesta debe ser mayor que 1. La probabilidad de que la primera persona, independientemente del número de personas, se encuentra en la sede apropiada es $\frac{1}{n}$, y $n$ de la gente, por lo que la expectación es 1. Incluso si la primera persona que se sienta en el mal asiento, no hay probabilidad no nula de otras personas sentadas en el asiento que sea correcto, por lo que la respuesta debe ser mayor que o igual a 1, y estoy bastante seguro de que la igualdad sólo existe en el caso de $n=2$.

Hay alguna forma de recurrencia pasando aquí. La enumeración de las posibilidades, me sale (si no he errado): $$ E_2 = \frac{1}{2}\cdot 2 + \frac{1}{2}\cdot 0 = 1\\ E_3 = \frac{1}{3}\cdot 3 + \frac{2}{3}\left[\frac{1}{2}\cdot 1 + \frac{1}{2}\cdot 0\right] = 1+\frac{1}{3}=\frac{4}{3}\\ E_4 = \frac{1}{4}\cdot 4 + \frac{3}{4}\left[\frac{1}{3}\cdot2 + \frac{2}{3}\left[\frac{1}{2}\cdot 1 + \frac{1}{2}\cdot 0\right]\right] = 1+\frac{3}{4}\cdot\left(\frac{2}{3}+\frac{1}{3}\right)=\frac{7}{4}\\ E_5 = \frac{1}{5}\cdot 5 + \frac{4}{5}\left[\frac{1}{4}\cdot3 + \frac{3}{4}\left[\frac{1}{3}\cdot2 + \frac{2}{3}\left[\frac{1}{2}\cdot 1 + \frac{1}{2}\cdot 0\right]\right]\right] = 1+\frac{4}{5}\left(\frac{3}{4} + \frac{3}{4}\cdot\left(\frac{2}{3}+\frac{1}{3}\right)\right)=\frac{11}{5}\\ $$ Deje $E_k$ ser el número esperado de personas en la correcta asientos cuando la población de partida es k. La relación parece ser: $$ E_k = 1 + \left(E_{k-1} - 1 + \frac{k-2}{k-1}\right)\frac{k-1}{k} $$ El primer 1 es el valor esperado de la persona 1 tomando el correcto asiento. El siguiente término se divide en dos partes. Si la primera persona que lo hizo no tomar el asiento que sea correcto, entonces la segunda persona puede "corregir" el error por el intercambio y tomar la persona anterior del asiento, dejando el resto de la $n-2$ de las personas de sus propios asientos. Si la segunda persona también se toma el mal asiento, el problema de los reinicios en el $n-1$ de la escala. En tanto los dos últimos casos, no es "uno menos" correcto asiento de la inicial, ya que el término anterior se utiliza un asiento con una opción incorrecta. Si la suposición es correcta, el valor esperado sería simplemente la suma de la recurrencia de la relación aplicada a $n$ o $\sum_{k=1}^n E_k$.

La generación de los primeros términos de uso de esta relación, se obtiene: $$ 1, 1, \frac{4}{3}, \frac{7}{4}, \frac{11}{5}, \frac{16}{6}, \frac{22}{7}, \frac{29}{8}, \frac{37}{9}, \frac{46}{10}, \ldots $$

El numerador es una ecuación cuadrática y el denominador es sólo $n$ por lo que el valor esperado debe ser: $$ E_n = \frac{n^2-n+2}{2n} $$

Edit: La de largo plazo de la proporción de personas que se sientan en el buen asientos de forma intuitiva sería de $$ \lim_{n \to \infty} \frac{E_n}{n}\\ =\lim_{n \to \infty} \frac{n^2-n+2}{2n^2}\\ =\frac{1}{2} $$ Que encaja muy bien con el largo plazo la probabilidad de que la última persona que se sienta en su sede apropiada.