Pregunta sobre el problema de la "Revisión del sombrero

Question

El famoso "Problema del Sombrero" dice así: "Los hombres entran en el restaurante y se ponen el sombrero en la recepción". Cada hombre recibe un sombrero al azar cuando regresa después de cenar. El objetivo es encontrar el número esperado de hombres que recuperan su sombrero derecho. Para calcular el valor esperado de su definición, tenemos que calcular la probabilidad con la que 'k' hombres recuperarían su sombrero correcto.

¿Cómo calcular esta probabilidad? Sé que este problema puede ser resuelto usando la "Linealidad de la Expectativa" de una forma mucho más simple, pero me gustaría saber la forma de calcular esta probabilidad.

Answer 1

Este es un ejemplo arquetípico en el que la expectativa es mucho más fácil que la distribución...

Hay $n$ y cada persona elige un sombrero uniformemente al azar, por lo que cada uno recupera su sombrero derecho con probabilidad $ \frac1n $ . La expectativa es lineal incluso cuando las variables aleatorias son dependientes, por lo que la media del número total de personas que recuperan su sombrero derecho es $n \times\frac1n =1$ .

Answer 2

Obsérvese que las especies combinatorias $ \mathcal {Q}$ de permutaciones con puntos fijos marcados es $$ \mathcal {Q} = \mathfrak {P} \left ( \mathcal {U} \mathcal {Z} + \mathfrak {C}_2( \mathcal {Z}) + \mathfrak {C}_3( \mathcal {Z}) + \mathfrak {C}_4( \mathcal {Z})+ \ldots\right ).$$ Por lo tanto, la función generadora de estas marcadas permutaciones es $$G(z, u) = \exp\left (uz+ \frac {z^2}{2}+ \frac {z^3}{3}+ \frac {z^4}{4}+ \ldots\right )$$ que es $$ \exp\left (uz-z+ \frac {z}{1}+ \frac {z^2}{2}+ \frac {z^3}{3}+ \frac {z^4}{4}+ \ldots\right ) \\ = \exp (uz-z) \exp\log\frac {1}{1-z} = \frac {1}{1-z} \exp (uz-z).$$

Podemos recuperar el número total de permutaciones en $n$ con $k$ puntos fijos de esta función generadora, está dada por $$n! [z^n][u^k] \frac {1}{1-z} \exp (uz-z) = n! [z^n] \frac {1}{1-z} \exp (-z) \frac {z^k}{k!} \\ = \frac {n!}{k!} [z^{n-k}] \frac {1}{1-z} \exp (-z) = \frac {n!}{k!} \sum_ {m=0}^{n-k} \frac {(-1)^m}{m!}.$$

De ello se deduce que el OGF del número esperado de puntos fijos es $$ \left.\frac {d}{du} G(z,u) \right |_{u=1} = \left.\frac {1}{1-z} \exp (uz-z) \times z \right |_{u=1} = \frac {z}{1-z}. $$ Ahora bien, desde $$[z^n] \frac {z}{1-z} =1,$$ esperamos que haya en promedio una persona que recupere su sombrero.

La diferenciación funciona aquí porque convierte el término $q \times u^k \times z^n/n!$ en $q \times k \times z^n/n!$ y vemos que el factor $n!$ que es necesario para el promedio ya está presente en el GF.

Answer 3

Para cada uno $S \in [n]$ de tal manera que $|S|=k$ que $f(S)$ sea el número de elementos $ \pi \in \mathfrak {S}_{n}$ cuyo conjunto de puntos fijos es exactamente $S$ : $$ f(S) = |\{ \pi \in \mathfrak {S}_{n}: \pi (i)=i ~ \text {iff}~~ i \in S\}| $$ Deje que $g(S)$ ser el número de $ \pi \in \mathfrak {S}_{n}$ cuyo conjunto de puntos fijos incluye $S$ : $$ g(S) = |\{ \pi \in \mathfrak {S}_{n}: \pi (i)=i ~~ \forall i \in S\}| $$ Claramente, $g(S)= \sum_ {S \subseteq T \subseteq [n]} f(T)$ . La inversión de Mobius da \begin {alineado*} f(S) &= \sum_ {S \subseteq T}(-1)^{||T \backslash S|}g(T) \\ &= \sum_ {S \subseteq ¡T} (-1)^{|||T|-k} (n-|T|)! \\ &= \sum_ {i=k}^{n} \sum_ {\a6}(-1)^{\i}(n-i)! \\ &= \sum_ {i=k}^{n} \binom (-1)^{i-k}(n-i)! \\ &=(n-k)! \sum_ {i=k}^{n} \frac {(-1)^{i-k}}{(i-k)!} \end {alineado*} Ya que hay $ \binom {n}{k}$ formas de elegir $S$ el número total de permutaciones en $ \mathfrak {S}_{n}$ con $k$ los puntos fijos son iguales a $$ \binom {n}{k} \cdot (n-k)! \sum_ {i=k}^{n} \frac {(-1)^{i-k}}{(i-k)!} = \frac {n!}{k!} \sum_ {i=k}^{n} \frac {(-1)^{i-k}}{(i-k)!} $$

Answer 4

Pista: Usar el principio de desquiciamiento (!n).

Este es un problema clásico y el siguiente pdf da la solución exacta que está buscando

La sección 5 del documento le da la respuesta. http://homepages.math.uic.edu/~kauffman/OldHats.pdf

Gracias

Satish