¿Probabilidad de algún ser de cara de morir perdido N o más veces en una fila en M rollos? [Aclarado]

Question

2015/01/28 Aclaración: la Pregunta reescrito para eliminar la ambigüedad que la provocó (muy interesante) de las respuestas a un problema diferente (uso editar si desea ver).

De Markus' comentarios en la pregunta anterior:

Consideremos una matriz con $F$ caras. Este dado es lanzado $M$ veces. ¿Cuál es la probabilidad de que cada una de las ventanas de tamaño $N \leq M$ dentro de esta serie de $M$ rollos contiene siempre todos los $F$ caras?

O como alternativa, considere la posibilidad de una urna con $F$ diferente bolas de colores, donde $M$ pelotas son dibujadas (con reemplazo después de cada sorteo) y los colores señaló. ¿Cuál es la probabilidad dado $F$, $M$, y algunos $N \leq M$ que cada consecutivas $N$ sorteos de la $M$ total dibuja mostraron al menos un ejemplo de cada uno de todos los $F$ colores?

Obviamente, si $M<N$ o $N<F$ la probabilidad es 0. Estoy atascado por la $F\leq N \leq M$ de los casos.

Me puede hacer esto utilizando recursiva de cálculo o de una cadena de Markov, pero sólo para los más triviales (pequeño) de los casos, ya que el espacio de estado, obviamente, explota con bastante rapidez.

Pensé en tratarla como a una se ejecuta racha problema, que es, pensé que si algún rostro o el color que se ve, seguido por $N$ todos de diferentes rostro/color resultante en un "fracaso", yo podría simplemente utilizar los medios existentes de cálculo de una racha de $N$ eventos con probabilidad de $(faces - 1)/(faces)$ para el caso de diferencias de la cara/de color. Yo era incapaz de llegar a una solución de esta manera.

Pensé entonces de tratarlo como un cupón de coleccionista problema. Fácilmente se puede calcular la probabilidad de que todas las caras o los colores que se observa en la primera $N$, por lo que pensé que el uso de que, en el próximo "ventana" de 2 a N+1 es un "fracaso" si los $N$ son todos diferentes, desde el 1 elemento (la probabilidad de $((faces - 1)/(faces))^N$), continuando este para cada paso de la "ventana" por 1 a conseguir una red de probabilidad. Me quedo atascado aquí con la dependencia entre los sucesivos "windows", y ni siquiera estoy seguro de si es válida la tachuela.

Traté de buscar una generación de función mirando ejemplo real de los condes de diferentes casos, y la búsqueda OEIS para las secuencias junto con la comprobación de la generación/secuencia de funciones en Mathematica. No encontré los partidos, y yo soy un neófito con funciones de generación, así que llegué a un callejón sin salida no.

Línea de fondo, dado $F, M, N$, ¿cómo podría calcular esto?

Un par de ejemplos para aclarar el problema anterior descripción.

Dado un alfabeto de dos elementos ${0,1}$, ($F=2$) las posibles palabras de longitud 4 ($M=4$) son

Con una "ventana" de 3 ($N=3$), la única longitud de 4 palabras que no tienen falta alfabeto elementos en todas las posibles longitud de 3 "windows" son

Por lo tanto, mi probabilidad de que faltan algunos alfabeto elemento en un 3-ventana 4-longitud de la cadena en un 2-elemento del alfabeto es 6/16.

Para más involucrado ejemplo, la longitud de 6 cuerdas en $0,1,2,3$. Hay 4096 de ellos (no voy a enumerarlos por razones obvias). Para una "ventana" de 5, sólo 528 de ellos tienen el alfabeto en todo lo posible la longitud de 5 posiciones consecutivas. Un par de ejemplos:

Tenga en cuenta que en todas estas, las posiciones de la 1 a la 5 y de 2 a 6 para cada uno tiene al menos un ejemplo de cada elemento en el alfabeto.

Ese número (528 en este ejemplo, o, equivalentemente, 3568 para el complemento) es lo que yo busco.

Espero que aclara la cuestión, disculpas a los lectores por la confusión que había causado.

2015/01/30 - he concedido la recompensa a Markus, aunque la respuesta fue un problema diferente (por mi culpa, mi ambiguamente escrito OP), en lugar de tener que desaparecer en el éter. Su respuesta me llevó a mirar el problema de otras maneras y fue de lo más interesante en sí mismo. Voy a añadir otra recompensa si/cuando se permite, y/o premio a uno manualmente debe una solución de presentar a sí mismo.

Answer 1

A la atención de: [2015-01-28] de Acuerdo a una reformulación de la OPs pregunta aclarar aspectos ambiguos, esta respuesta es no válido. En lugar de direcciones el problema señalado un par de párrafos más abajo. Sin embargo, desde la elaboración podría ser útil para el lector interesado, no voy a quitar.

---

Nota: El siguiente es un enfoque de dos pasos. Voy a empezar con un problema más sencillo con el fin de estar bien preparados para el más difícil problema señalado por OP. También tomamos una mirada en el pequeño ejemplos como simple plausability de verificación. Vamos a ver que el resultado de la generación de la función es el declarado por @RusMay.

---

El siguiente está basado en la sección I. 4.1 y ejemplo III.24 de la Analítica de la Combinatoria por P. Flajolet y R. Sedgewick.

Vamos a denotar la $F$ caras con $a_1,\ldots,a_F$. Cada resultado de $M$ de los rollos puede ser visto como la palabra de longitud $M$ consta de caracteres del alfabeto $\mathcal{A}=\{a_1,\ldots,a_F\}$.Podemos reformular OPs pregunta y obtiene la siguiente

Problema: Vamos a usar un alfabeto $\mathcal{A}=\{a_1,\ldots,a_F\}$ $F$ personajes. ¿Cuál es el número de $C_F(M,N)$ de las diferentes palabras de longitud $M$ con carreras más largas de un carácter que tienen una longitud de menos de $N(\geq 2)$.

La correspondiente probabilidad OP es lo que pide es el número de $C_F(M,N)$ dividido por el número de $F^M$ de todas las palabras de longitud $M$ sobre el alfabeto $\mathcal{A}$.

Primer Paso: Análisis de los casos $F=2,N\geq 2$

Consideramos binario de las cadenas sobre el alfabeto

\begin{align*} \mathcal{A}=\{0,1\} \end{align*}

y se busca el número de cadenas de longitud $M$ tenía menos de $N$ consecutivo $0$s y $1$s.

Construimos las cadenas binarias comenzando con el más sencillo de los patrones. Vamos $$\text{SEQ}(1)=\{\varepsilon,1,11,111,\ldots\}$$ denote all strings containing only $1$s with length $\geq0$. The empty string is denoted with $\varepsilon$. The corresponding generating function is $$z^0+z^1+z^2+\ldots=\frac{1}{1-z},$$ with the exponent of $z^n$ marking the length $n$ of a string of $1$s and the coefficient of $z^n$ marking the number of strings of length $n$. Similarly, we define $\text{SEQ}(0)=\{\varepsilon,0,00,000,\ldots\}$.

Deje $\text{SEQ}^{\leq k}(1)$ ser el conjunto de todas las cadenas de $1$s con una longitud de $\leq k$. La generación de la función de $\text{SEQ}^{\leq k}(1)$ $$1+z+z^2+\ldots+z^{k}=\frac{1-z^{k+1}}{1-z}$$

Aún más simplificado: consideramos $$F=2, N=2$$ es decir, las cadenas con las carreras de la $0$s y $1$s con longitud máxima $1$.

¿Cómo podríamos describir todas estas cadenas? Podemos tener un líder de $1$. Así, partimos de cero o $1$s. Formalmente: \begin{align*} \text{SEQ}^{\leq 1}(1)=\{\varepsilon,1\} \end{align*} con la generación de la función \begin{align*} 1+z\tag{1} \end{align*}

Entonces puede haber cero o más grupos, cada grupo contiene un $0$, seguido por una $1$. Formalmente:

$$\text{SEQ}(01)=\{\varepsilon,01,0101,010101,\ldots\}$$

con la generación de la función

\begin{align*} 1+z^2+z^4\ldots=\frac{1}{1-z^2}\tag{2} \end{align*} Las cuerdas puede terminar con el cero o el uno $0$, formalmente $\text{SEQ}^{\leq 1}(0)$ con la generación de la función $1+z$.

Llegamos a la conclusión: Las cadenas binarias tener pistas de $0$s y $1$s de longitud máxima $1$ son modelados por la

\begin{align*} \text{SEQ}^{\leq 1}(1)\text{SEQ}(01)\text{SEQ}^{\leq 1}(0)\tag{3} \end{align*}

con la generación de la función \begin{align*} \left(1+z\right)\left(\frac{1}{1-z^2}\right)\left(1+z\right)=\frac{1+z}{1-z} \end{align*}

de acuerdo a (1) y (2)

---

Generalización: $F=2,N\geq 2$

Consideramos ahora el mayor problema general $N\geq 2$. Ya que debemos tener en cuenta que las carreras de menos de $N$ $0$s y $1s$ tenemos que sustituir el exterior de las apariciones $0$ $1$ hasta $N-1$ $0$s resp. $1$s y el interior de la $0$s y $1$s ampliar hasta $N-2$ $0$s resp. $1$s. Obtenemos

\begin{align*} \text{SEQ}^{\leq N-1}(1)\text{SEQ}\left(0\text{SEQ}^{\leq N-2}(0)1\text{SEQ}^{\leq N-2}(1)\right)\text{SEQ}^{\leq N-1}(0) \end{align*}

con la correspondiente generación de función $A(z)$

\begin{align*} A(z)&=\left(\frac{1-z^N}{1-z}\right)\left(\frac{1}{1-z\frac{1-z^{N-1}}{1-z}z\frac{1-z^{N-1}}{1-z}}\right)\left(\frac{1-z^N}{1-z}\right)\\ &=\frac{(1-z^N)^2}{(1-z)^2-z^2(1-z^{N-1})^2}\\ &=\frac{1-z^N}{1-2z+z^N}\tag{4} \end{align*}

Nota: Observar, que (4) corresponde a la generación de función dada por @RusMay con $F=2$

---

Ejemplo: $F=2, N=3$

La generación de la función de contar el número de cadenas binarias con el consecutivo de carreras de duración menor de 3 es

\begin{align*} \frac{1-z^3}{1-2z+z^3}=1+2z+4z^2+6z^3+10z^4+\ldots \end{align*}

las cadenas correspondientes son

\begin{align*} \{&\varepsilon,\\ &0,1,\\ &00,01,10,11,\\ &001,010,011,100,101,110,\\ &0010,0011,0100,0101,0110,1001,1010,1011,1100,1101,\\ &\ldots\} \end{align*}

Este fue el warm-up de ejercicio y ahora estamos bien preparados para la solución general.

---

Segundo Paso: solución General $F\geq 2,N\geq 2$

Palabras con el consecutivo carreras que tienen una longitud de exactamente uno se llama Smirnov palabras. Observar, en (3) se describe Smirnov palabras sobre un alfabeto binario con la generación de la función $\frac{1+z}{1-z}$.

Deje $\mathcal{W}=SEQ(\mathcal{A})$ el conjunto de palabras sobre el alfabeto $\mathcal{A}=\{a_1,\ldots,a_F\}$, e $\mathcal{S}$ el conjunto de Smirnov palabras. Tenemos dos observaciones:

• Aspecto 1: La generación de la función de $W(v_1,\ldots,v_F)$ contando el número de palabras de $\mathcal{W}$ $v_j$ que indica el número de apariciones de la letra $a_j$, $1 \leq j \leq F$ es

\begin{align*} W(v_1,\ldots,v_F)=\frac{1}{1-(v_1+\ldots+v_F)}\tag{5} \end{align*}

Nota: Aquí sigo Flajolet del consejo y omitir la variable redundante $z$ $W$ que de lo contrario se utiliza para marcar la longitud de las palabras. Este trabajo está hecho por $v_1,\ldots,v_F$, por lo que no necesito usar $W(z;v_1,\ldots,v_F)=\frac{1}{1-(v_1+\ldots+v_F)z}$ lugar.

• Aspecto 2: podemos tomar una arbitraria de la palabra de$\mathcal{W}$, y el sustituto de cada ejecución de los personajes por una única aparición de este personaje con el fin de obtener un Smirnov palabra. Por otro lado, podemos encontrar a cada palabra $w\in \mathcal{W}$ un Smirnov palabra $s_w\in\mathcal{S}$ y ampliar cada uno de los caracteres de $s_w$ por un correcto funcionamiento de la longitud de este personaje con el fin de obtener la correspondiente palabra $w\in \mathcal{W}$.

Así, arbitraria palabras en $\mathcal{W}$ son derivados de Smirnov palabras por un simultánea de sustitución:

\begin{align*} \mathcal{W}=\mathcal{S}[a_1\mapsto SEQ^{\geq 1}(a_1),\ldots,a_F\mapsto SEQ^{\geq 1}(a_F)]\tag{6} \end{align*}

Deje $S(v_1,\ldots,v_F)$ denotar la generación de la función de contar el número de Smirnow palabras en $\mathcal{S}$.

La sustitución en (6) implica la relación:

\begin{align*} W(v_1,\ldots,v_F)=S\left(\frac{v_1}{1-v_1},\ldots,\frac{v_F}{1-v_F}\right)\tag{7} \end{align*} ya que de manera similar a (2) la generación de la función de \begin{align*} SEQ^{\geq 1}(a_j)=\{a_j,a_ja_j,a_ja_ja_j,\ldots\} \end{align*} es $$\frac{v_j}{1-v_j}$$

Observamos $S(v_1,\ldots,v_F)$ se especifica en (7) implícitamente por $W(v_1,\ldots,v_F)$. Dado que la función inversa de a $\frac{v}{1-v}$ $\frac{v}{1+v}$ obtenemos con la ayuda de (5):

\begin{align*} S(v_1,\ldots,v_F)&=W\left(\frac{v_1}{1+v_1},\ldots,\frac{v_F}{1+v_F}\right)\\ &=\left(1-\sum_{j=1}^{F}\frac{v_j}{1+v_j}\right)^{-1} \end{align*}

Podemos avanzar aún más simple, ya que no es necesario distinguir entre los caracteres del alfabeto $\mathcal{A}$. Así, si partimos $v_j=z$ y así olvidar la composición de las palabras en letras, se obtiene la generación de función para Smirnov palabras

\begin{align*} \frac{1}{1-F\frac{z}{1+z}}&=\frac{1+z}{1-(F-1)z}\tag{8}\\ &=1+\sum_{n=1}^{\infty}F(F-1)^{n-1}z^n \end{align*}

A partir de aquí es sólo un pequeño paso en la búsqueda de la generación de la función de las palabras, que no contienen pistas de $N$ consecutivo la igualdad de las letras. Seguimos aspecto 2 y sustituir cada carácter de una longitud de menos de $N$. En términos de generación de funciones tenemos que sustituir en (8)

$$z\mapsto z\frac{1-z^{N-1}}{1-z}.$$

Se obtiene finalmente la

Solución: La generación de la función $\tilde{S}(z)$ contando todas las palabras sobre el alfabeto $\mathcal{A}=\{a_1,\ldots,a_F\}$ con las carreras de la longitud de menos de $N$ caracteres consecutivos es

\begin{align*} \tilde{S}(z)=\frac{1}{1-F\frac{z\frac{1-z^{N-1}}{1-z}}{1+z\frac{1-z^{N-1}}{1-z}}}=\frac{1-z^{N}}{1-Fz+(F-1)z^{N}} \end{align*}

Si $C_F(M,N)$ denota el coeficiente de $[z^M]\tilde{S}(z)$ la quería probabilidad es $$\frac{C_F(M,N)}{F^M}$$

Nota: Observar que $\tilde{S}(z)$ es la generación de función dada por @RusMay.

---

Vamos a terminar con dos pequeños ejemplos:

Ejemplo: $F=3,N=3,\mathcal{A}=\{0,1,2\}$

La generación de la función de contar el número de ternario cadenas con el consecutivo de carreras de duración menor de 3 es

\begin{align*} \frac{1-z^3}{1-3z+2z^3}=1+3z+9z^2+24z^3+66z^4+\ldots \end{align*}

las cadenas correspondientes son

\begin{align*} \{&\varepsilon,\\ &0,1,2\\ &00,01,02,10,11,12,20,21,22\\ &001,002,010,011,012,020,021,022,\\ &100,101,102,110,112,120,121,122,\\ &200,201,202,210,211,212,220,221,\\ &0010,0011,0012,0020,0021,0022,0100,0101,0102,0110,0112,\\ &0120,0121,0122,0200,0201,0202,0210,0211,0212,0220,0221,\\ &1001,1002,1010,1011,1012,1020,1021,1022,1100,1101,1102,\\ &1120,1121,1122,1200,1201,1202,1210,1211,1212,1220,1221,\\ &2001,2002,2010,2011,2012,2020,2021,2022,2100,2101,2102,\\ &2110,2112,2120,2121,2122,2200,2201,2202,2210,2211,2212,\\ &\ldots\} \end{align*}

Ejemplo: $F=3,N=4,\mathcal{A}=\{0,1,2\}$

La generación de la función de contar el número de ternario cadenas con el consecutivo de carreras de duración menor de 4 es

\begin{align*} \frac{1-z^4}{1-3z+2z^4}=1+3z+9z^2+27z^3+78z^4+\ldots \end{align*}

las cadenas correspondientes son

\begin{align*} \{&\varepsilon,\\ &0,1,2\\ &00,01,02,10,11,12,20,21,22\\ &000,001,002,010,011,012,020,021,022,\\ &100,101,102,110,111,112,120,121,122,\\ &200,201,202,210,211,212,220,221,222,\\ &0001,0002,0010,0011,0012,0020,0021,0022,0100,\\ &0101,0102,0110,0111,0112,0120,0121,0122,0200,\\ &0201,0202,0210,0211,0212,0220,0221,0222,1000,\\ &1001,1002,1010,1011,1012,1020,1021,1022,1100,\\ &1101,1102,1110,1112,1120,1121,1122,1200,\\ &1201,1202,1210,1211,1212,1220,1221,1222,2000,\\ &2001,2002,2010,2011,2012,2020,2021,2022,2100,\\ &2101,2102,2110,2111,2112,2120,2121,2122,2200,\\ &2201,2202,2210,2211,2212,2220,2221,\\ &\ldots\} \end{align*}

---

Nota: Según P. Flajolet (p.205) en este ejemplo se aplica igual de bien a no uniforme de la carta de las probabilidades y a una colección de longitud de ejecución superior límite inferior y límite depende de cada letra en particular. Este tema en particular, es perseguido por los diferentes métodos en varias obras de S. Karlin y los coautores.

Answer 2

El camino "fácil" para enumerar las cadenas de una longitud determinada que evitar cualquier colección de palabras es el llamado Goulden-Jackson clúster método. Este método está elegantemente descrito en un maravilloso papel por Zeilberger y el de Noonan. (Este documento está pensado como una introducción a la Goulden-Jackson clúster método y casi no tiene requisitos previos.) En lo que concretamente se describe cómo obtener fácilmente por la generación de la función de palabras de diferentes longitudes que evitar una colección de "malas palabras". En su caso, decir $a_M$ es el número de rollos de la longitud de la $M$ que evitar todas las malas palabras de la forma$i^N$$1\le i\le F$. Su método muestra que la correspondiente generación de función $\sum_{M\ge0}a_M z^M$ es $$\frac{1-z^N}{1-Fz+(F-1)z^{N}}.$$ Por supuesto, todavía queda el problema de la extracción del coeficiente de $z^M$ a partir de esta función racional, pero tal vez esto es suficiente para empezar.

Answer 3

Si los números implicados son pequeños, sólo tienes que calcularlos. Si $F$ es grande, la probabilidad de dos en una fila en un par determinado es $1/F^2$ y la posibilidad de que un par (ya que el primero puede ser cualquier cosa) es $1/F$ que puede hacer una distribución de Poisson. No han especificado el cálculo lo suficientemente bien como para hacerlo.