Número esperado de asientos incorrectos en el avión

Question

Muchas personas se familiaricen con la puesta en marcha de este problema: usted tiene un avión con 100 asientos, y 100 pasajeros que han sido asignados asientos única. El primer pasajero se olvida de su billete, y así toma un asiento al azar. El resto de los pasajeros entran en el avión. Si su asiento está vacío, la llevan. Si está ocupado, tomar una muestra aleatoria de asiento en el avión.

En este punto, la pregunta que se suele pedir es "¿cuál es la probabilidad de que el número 100 de la persona obtiene su plaza". Este fue preguntado aquí.

Mi pregunta es un poco diferente. Por el momento todos los pasajeros hayan abordado lo que se espera que el número de pasajeros en el mal asiento? He visto muchas personas se preguntan esto como una pregunta de seguimiento a la primera en algunos otros foros en línea, pero no parece ser una respuesta razonable en cualquier lugar.

Intento:

Buscan a menor tamaño de los planos, podemos llegar a una conjetura que para un avión de tamaño $n$, $$\text{expectation}=\begin{cases}1+\frac12+\cdots+\frac1{n-1}&n\text{ is even}\\\frac12+\frac13+\cdots+\frac1n&n\text{ is odd}\end{cases}$$

Cuando se intenta calcular la expectativa, incluso, $n$ como una suma, se obtiene una muy complicado de expresión, de la forma $$\frac1n\left(2\sum_{i=1}^{n-1}\frac1i+3\sum_{i\ne j,i,j=1}^{n-1}\frac1{ij}+4\sum_{i\ne j\ne k,i,j,k=1}^{n-1}\frac1{ijk}\cdots\right)$$

Cómo podemos obtener el resultado que me han conjeturado?

---

$\small\text{Edit:}$

$\small\text{The conjecture was wrong in the odd case - the expectation is always equal to }\small\sum_{i=1}^{n-1}\frac1i\small\text{whether }n\small\text{ is even or odd. (As shown by the answers and @Akababa's comment)}$

Answer 1

Deje $X_k$ ser el número incorrecto de escaños ocupados por pasajeros $k$. Obviamente $X_k$ es $0$ o $1$; por esta respuesta que hemos $$P(X_k=1)=\frac1{n+2-k}\quad\hbox{for $k=2,3,\ldots,n$}\ ;$$ por lo tanto $$E(X_k)=0\cdot P(X_k{=}0)+1\cdot P(X_k{=}1)=\frac1{n+2-k}\ .$$ Del mismo modo, $$E(X_1)=\frac{n-1}n=1-\frac1n\ .$$ El número total de pasajeros en el mal asiento es $T_n=X_1+\cdots+X_n$, y por la linealidad de su valor esperado es $$E(X_1)+E(X_2)+E(X_3)+\cdots+E(X_n) =\Bigl(1-\frac1n\Bigr)+\frac1n+\frac1{n-1}+\cdots+\frac12\ ,$$ es decir, $$E(T_n)=1+\frac12+\cdots+\frac1{n-1}\ ,$$ siempre $n>1$.

Answer 2

Cada configuración está asociado a un ciclo como $1\mapsto 5\mapsto 8\mapsto 72\mapsto 1$, lo que significa que la primera persona que ocupa el quinto lugar, la quinta persona que se toma el octavo lugar, $\ldots$, $72$th persone ocupa el primer lugar. Si esto ocurre cualquier otra persona además de la $1,5,8,72$ toma su lugar. La probabilidad de que $1\mapsto 5\mapsto 8\mapsto 72\mapsto 1$ ocurre es $\frac{1}{101-1}\cdot\frac{1}{101-5}\cdot\frac{1}{101-8}\cdot\frac{1}{101-72}$ y por este camino hay cuatro personas en el lugar equivocado.

La probabilidad de que $0$ de las personas están en el lugar equivocado es $\frac{1}{100}$.
La probabilidad de que sólo $1$ persona está en el lugar equivocado es cero.
La probabilidad de que $2$ de las personas están en el lugar equivocado (configuraciones $1\mapsto m\mapsto 1$) está dado por $\frac{1}{100}$ veces la suma de $\frac{1}{101-k}$ $k$ que va de $2$$100$, es decir, por el coeficiente de $x^2$ en

$$g(x)=\frac{x}{101-1}\left(1+\frac{x}{101-2}\right)\cdot\left(1+\frac{x}{101-3}\right)\cdot\ldots\cdot\left(1+\frac{x}{101-100}\right).$$ Del mismo modo, la probabilidad de que $k\geq 2$ de las personas están en el lugar equivocado está dada por el coeficiente de $x^k$$g(x)$. En particular, el valor promedio del número de personas en el lugar equivocado está dada por $$\sum_{k\geq 2} k\cdot [x^k]g(x) = \left.\frac{d}{dx}\left(g(x)-\frac{x}{100}\right)\right|_{x=1}=g'(1)-\frac{1}{100}=\frac{g'(1)}{g(1)}-\frac{1}{100}.$$ Por otro lado $\log(g(x))=\log(x)-\log(100)+\log\left(1+\frac{x}{99}\right)+\ldots+\log\left(1+\frac{x}{1}\right)$, por lo tanto

$$\frac{g'(x)}{g(x)}=\frac{1}{x}+\frac{1}{99+x}+\frac{1}{98+x}+\ldots+\frac{1}{1+x}$$ y $\frac{g'(1)}{g(1)}$ es igual a la $100$ésimo número armónico $H_{100}$.
De ello se desprende que la quería valor promedio es $H_{99}\approx 5.17738$.

El mismo argumento funciona para cualquier otro número de escaños $s\geq 3$ y no depende de la paridad del número de escaños. Considerando $g''(x)$ también puede calcular la varianza de la variable aleatoria $W$ dando el número de personas en el lugar equivocado:

$$\operatorname{Var}[W]=\mathbb{E}[W^2]-\mathbb{E}[W]^2 = -H_{s-1}^2+\sum_{n\geq 2}n^2\cdot [x^n]g(x)$$ es igual $$-H_{s-1}^2+H_{s-1}+g''(1) = H_{s-1}-H_{s-1}^2+H_s^2+\left.\frac{d}{dx}\left(\frac{g'(x)}{g(x)}\right)\right|_{x=1}$$ tal que $$\operatorname{Var}[W]=H_{s-1}\left(1+\frac{2}{s}\right)-H_{s-1}^{(2)}.$$ Para grandes valores de $s$ la distribución de los $W$ está muy bien aproximada por una distribución de Poisson.