Sorprendente límite (probabilidad de no hay dos coincidiendo pares)

Question

Me topé con esta pregunta por azar. La motivación es larga, la pregunta es bastante corto; si sólo estás aquí para los límites, siéntase libre para saltar a la rotura.

Estoy tomando cinco cursos de este semestre, todos los que se reúnen en dos días, y se me ocurrió cuenta de que todos mis días parecía un poco diferente. Así que me tomé un vistazo más de cerca a mi horario, y por supuesto, ninguno de mis clases de compartir el mismo dos días.

Esto me pareció muy raro, así que me decidí a trabajar la probabilidad de que esto ocurra. Por supuesto, en realidad, hay todo tipo de factores que hacen que ciertas distribuciones más favorables que otros, pero decidí ignorar eso y simplemente asumir que los horarios eran independientes idénticamente distribuidas variables.

Era una especie de cómoda que también hay cinco días en una semana, por lo que la motivación de la pregunta era esta: En un $n$ día de la semana, ¿cuál es la probabilidad de que $n$ clases de reuniones, dos veces cada uno, no tiene pareja que se reúne en el mismo dos días?

Así que miré en la combinatoria, y estoy bastante seguro de que la respuesta es la desagradable vertical fórmula $$\frac{ \displaystyle { {n \choose 2} \choose n} n!}{ {n \choose 2}^n}$$ La idea aquí es que hay ${n \choose 2}$ posibles horarios, por lo que la lista de todos los posibles resultados incluye $n$ opciones con la repetición de este grupo, teniendo en cuenta las clases de distinguir. La lista de los resultados deseados elige $n$ opciones sin repetición de este grupo y, a continuación, asigna los horarios de las clases.

[ Tal vez esto no es correcto; si no, yo estaría interesado en que, también, pero mi pregunta para todos es realmente acerca de esta expresión, no es mi clase de situación :) ]

Ahora sabía por trabajo a mano que $n=3$ da alrededor de un 22% y $n=4$ da alrededor de un 28%, y he calculado mi situación real en un 30%. Monótona creciente es lo que yo esperaba. Después de todo, usted tiene mucho más capacidad de separar las clases durante largas semanas.

Yo también se espera que este efecto rápidamente a dominar la complicación que más clases que se añaden. Pero la imagen que surge de (más) pequeño $n$ lo hizo bastante claro que me equivoqué.

---

Cuando yo estaba jugando en WolframAlpha, me encontré con el límite de

$$\lim_{n\to\infty}\frac{ \displaystyle { {n \choose 2} \choose n} n!}{ {n \choose 2}^n} = \frac{1}{e}$$

Que me cogió con la guardia baja. Inmediatamente pensé en Stirling aproximación, pero no puedo hacer el ajuste, ya que en Stirling $e$ es elevado a la $n^\text{th}$. Es cierto que no sé mucho de especial límites, pero se escriben en términos de factoriales parece llegar a ninguna parte cerca de la definición de $e$.

Hay una escuela primaria explicación para este límite?

Pregunta extra: "elija $2$" parece ser una muy especial circunstancia: si los dos son reemplazadas por otras, el límite se vuelve $0$, y si los dos son reemplazados por grupos de tres o cuatro, el límite se vuelve $1$. Mi conjetura es que con la correcta explicación del caso interesante, la razón de estos será bastante obvio.

Answer 1

La situación es generalizada Brithday problema. Ha $m$ opciones posibles (horarios en su configuración), y elige $n$ elementos con posibles repeticiones. ¿Cuál es la probabilidad de que usted nunca tomará el mismo elemento dos veces?

La probabilidad es, por decisiones independientes,

$$\frac{\binom{m}{n}n!}{m^n} = \frac{m!}{m^n(m-n)!} = \prod_{k=0}^{n-1}\frac{m-k}{m} = \prod_{k=1}^{n-1}\left(1 - \frac{k}{m}\right).$$

Al $k \ll m$, podemos aproximar que bien con el primer orden de aproximación de $\log (1-x)$,

$$\begin{align} \prod_{k=1}^{n-1} \left(1 - \frac{k}{m}\right) &= \exp \left(\sum_{k=1}^{n-1}\log \left(1-\frac{k}{m}\right) \right)\\ &\approx \exp \left(-\sum_{k=1}^{n-1}\frac{k}{m} \right)\\ &= \exp \left(-\frac{n(n-1)}{2m} \right). \end{align}$$

En su caso, usted ha $m = \binom{n}{2}$ horarios, por lo que el argumento de la función exponencial, viene a ser exactamente $-1$.

Podemos - para $n \ll m$ - uso más términos de la expansión de los logaritmos para obtener una aproximación más precisa,

$$\log \left(1 - \frac{k}{m}\right) = - \sum_{j=1}^\infty \frac{1}{j}\left(\frac{k}{m}\right)^j = - \left(\frac{k}{m} + \frac{k^2}{2m^2}\right) + O\left(\frac{k^3}{m^3}\right).$$

Que los rendimientos de

$$\prod_{k=1}^{n-1}\left(1-\frac{k}{m}\right) = \exp\left(- \frac{n(n-1)}{2m} - \frac{(n-1)n(2n-1)}{12m^2} + O\left(\frac{n^4}{m^3}\right)\right)$$

y la inserción de $m = \binom{n}{2} = \frac{n(n-1)}{2}$

$$\begin{align} \prod_{k=1}^{n-1}\left(1-\frac{k}{m}\right) &= \exp\left(-1 -\frac{2n-1}{2n(n-1)} + O(n^{-2})\right)\\ &= \frac1e\exp\left(-\frac{1}{n} + O(n^{-2})\right)\\ &= \frac1e\frac{n-1}{n} + O(n^{-2}). \end{align}$$