La probabilidad de consecutivos pisos en un ascensor con más gente

Question

Otro usuario publicado esta pregunta acerca de los ocupantes del elevador, lo que me hizo curioso acerca de una pregunta más difícil.

En un $t$pisos (edificio sin sótano), $n$ de las personas de obtener en un ascensor en el primer piso. Cada persona uniformemente al azar de forma independiente desea ir a uno de los pisos más altos y se pulse el botón correspondiente para el piso, suponiendo que no ha sido presionado.

¿Cuál es la probabilidad de que tres pisos de ser visitado en algún momento durante el ascensor del viaje de llevar a estas personas?

Nota, no estoy pidiendo la probabilidad de que sólo hay tres pisos visitado y todos ellos pasan a ser consecutivos, sino más bien, que entre las plantas visitadas, hay un subconjunto de ellos de tamaño tres que son adyacentes.

Mis reflexiones iniciales sobre el problema, es que podemos aproximarnos a través de "malas palabras" y las cadenas, dejando "+" representa que el piso fue visitado y "0" representa que el suelo no estaba, nos preguntamos por la probabilidad de que la secuencia del visitado o no no contiene la subcadena "+++", pero este no tiene en cuenta el hecho de que varias personas podrían elegir para ir a la misma planta, etc...

Un enfoque sencillo sería simplemente para ejecutar las simulaciones, pero que es poco interesante, así que les pido si alguien tiene una idea en un pen+blanco.

Si alguien quiere números específicos para trabajar con, trate con $n=t=10$, ya que de esa manera me equivoco y leer la de otros usuarios de la cuestión a primera vista.

Answer 1

DESCARGO de responsabilidad: en la Actualidad este post es un trabajo en progreso. No tengo el tiempo para pensar en los índices y la notación thorougly por ahora, así que voy a volver más tarde y limpiar mi post.

Deje $A(k,n),B(k,n)$ e $C(k,n)$ denotar el número de "malas palabras" como se les llame de longitud $n$ que contiene exactamente $k$ visitó pisos "+" que termina en $0,1$ e $2$ visitó plantas respectivamente. Luego podemos configurar el sistema: $$ \begin{align} A(k,n)&=A(k,n-1)+B(k,n-1)+C(k,n-1)\\ B(k,n)&=A(k-1,n-1)\\ C(k,n)&=B(k-1,n-1)=A(k-2,n-2) \end{align} $$ la combinación de estos, vemos que $$ A(k,n)=A(k,n-1)+A(k-1,n-2)+A(k-2,n-3) $$ lo que nos permite calcular $A(k,n)$ de forma recursiva. A continuación, el número de $T(k,n)$ de las "malas palabras" de longitud $n$ con exactamente $k$ apariciones de "+" se puede obtener tomando el número de "malas palabras" de longitud $n+1$ con $k$ apariciones de "+" que termina con un "$0$", es decir,$A(k,n+1)$, y sólo la eliminación de la última "$0$" de cada palabra. De inmediato nos han $$ T(k,n)=T(k,n-1)+T(k-1,n-2)+T(k-2,n-3) $$ donde $T(0,n)=1$, $T(1,n)=n$ y $T(2,n)=\binom{n}{2}=\frac{n(n-1)}2$ para todos los $n\in \mathbb N$. Aquí hay una tabla para $T(k,n)$ (calculada usando este programa): $$ \begin{array}{c|cc} (k,n)&0&1&2&3&4&5&6&7&8&9&10&11&12&13\\ \hline 0&1&1&1&1&1&1&1&1&1&1&1&1&1&1\\ 1&0&1&2&3&4&5&6&7&8&9&10&11&12&13\\ 2&0&0&1&3&6&10&15&21&28&36&45&55&66&78\\ 3&0&0&0&0&2&7&16&30&50&77&112&156&210&275\\ 4&0&0&0&0&0&1&6&19&45&90&161&266&414&615\\ 5&0&0&0&0&0&0&0&3&16&51&126&266&504&882\\ 6&0&0&0&0&0&0&0&0&1&10&45&141&357&784\\ 7&0&0&0&0&0&0&0&0&0&0&4&30&126&393\\ 8&0&0&0&0&0&0&0&0&0&0&0&1&15&90\\ 9&0&0&0&0&0&0&0&0&0&0&0&0&0&5 \end{array} $$ Podemos ver cómo cada entrada de esta tabla es la suma de la vecina a la izquierda y, a continuación, dos números más movimiento en diagonal a la izquierda-arriba - como la recurrencia dice.

---

Dado que la figura, también necesitamos calcular el número de maneras en $n$ de la gente se puede poner en exactamente $k$ papeleras de ie. no hay bin es permitido estar vacío, pero varias personas se les permite ir en la misma bandeja. Este es el mismo que preguntar por el número de surjections $S(n,k)$ de $[n]$ a $[k]$, como Brian M. Scott tan brillantemente observa en un comentario más abajo.

---

Con estas cifras en la mano, el número de unsuccesful combinaciones de $U(t,n)$ para $n$ personas y $t$ historias se pueden encontrar como $$ U(t,n)=\sum_{k=1}^{t-1} T(k,t-1)\cdot S(n,k) $$ La suma no tenía necesidad de ir todo el camino hasta el$k=t-1$, ya que para la mayoría de los valores de $t$ tenemos $T(k,t-1)=0$ incluso antes de $k=t-1$, pero he elegido el de arriba por la simplicidad.