La probabilidad de una carrera de a $n$ tarjetas del mismo color?

Question

Un mago amigo me golpeó con esto: dada una baraja, ¿cuál es la probabilidad de que contenga al menos una carrera de al menos $n$ tarjetas del mismo color - por ejemplo, cuatro de los rojos o cuatro negros en una fila?

Answer 1

No es fácil dar un resultado exacto, pero si quieres un simple límite superior, se puede calcular el número esperado de las carreras de la longitud de la $n$ fácilmente. Cualquier bloque de $n$ tarjetas es una carrera con una probabilidad de $$ \frac{{{52-n}\elegir{26}}}{{52}\seleccione{26}}=\frac{(52-n)!26!}{(26-n)!52!}, $$ por lo que el número esperado de las carreras de la longitud de la $n$ es sólo $$ E_n = (53-n)\frac{(52-n)!26!}{(26-n)!52!}=\frac{53\cdot {{26}\, seleccione{n}}}{{53}\, seleccione{n}}. $$ (Aquí estamos permitiendo que no maximal se ejecuta en la cuenta... así que una carrera de duración $8$, dicen, contiene tres carreras de la longitud de la $6$.) El número esperado de las carreras de la longitud de la $n$ es mayor que o igual a la probabilidad de que haya al menos una carrera de la longitud de la $n$. El primer resultado es trivial para $n=6$: la probabilidad de que al menos una carrera de la longitud de la $6$ satisface $$ P_6 \le E_6 = \frac{53\cdot{{26}\elegir{6}}}{{53}\seleccione{6}}=\frac{26\cdot 25\cdot 24\cdot 23 \cdot 22\cdot 21}{52 \cdot 51\cdot 50 \cdot 49\cdot 48}=0.5315... $$ Dado que el resultado exacto es $P_6=0.46424\ldots$, esto no es demasiado flojo; y producirá más cerca de aproximaciones para tiradas largas.

Answer 2

Supongamos que tenemos $m$ rojo y $m$ tarjetas negras y nos preguntamos acerca de los $(2m)!$ barajan cubiertas que contiene una carrera de al menos $n$ tarjetas de la mismo color. Vamos a calcular la probabilidad de la complementaria evento, es decir, no había una carrera de $n$ colores o todas las carreras haber de longitud en la mayoría de las $n-1.$

El uso de $z$ para las tarjetas rojas y $w$ para el negro tarjetas que tenemos por la inspección que el recuento $$[z^m w^m] G(z, w)$$

donde $G$ es la generación de la función

$$G(z, w) = [z^m w^m] (1+\cdots+z^{n-1})(1+\cdots+w^{n-1}) \\ \times \sum_{q=0}^m w^q z^q (1+\cdots+z^{n-2})^q(1+\cdots+w^{n-2})^q.$$

Los polinomios que aparecen en la generación de esta función $O(n^2 m^2)$ términos (contribución de la suma), en una liga diferente de la $4^m/\sqrt{\pi m}$ del coeficiente binomial. Donde tenemos que pagar es en el tamaño de los coeficientes que se $m$ dígitos peor de los casos.

Como una nota aparte que tenemos que multiplicar el coefficents de $G(z,w)$ $(m!)^2$ debido a que es el número de cubiertas correspondiente a un patrón binario de colores donde hemos asumido que las tarjetas de la mismo color y valor, pero de diferente palo se consideran distintas.

En particular, la respuesta de una baraja de naipes donde tenemos $26$ rojos y $26$ negros no tener una carrera de duración de cuatro es (este valor es exacta)

$${52\elija 26}^{-1} 12911299418962 \sim 0.02603512182$$

por lo que la probabilidad de que no contienen una carrera de duración de cuatro es $$97.4\%.$$

Obviamente no hemos comprobado todos los $495918532948104$ posible binario las secuencias que contengan $26$ ceros y unos para obtener esta respuesta.

Curiosamente, cuando proponemos $n=2$ y sólo hay dos posibles los candidatos a la alternancia entre el cero y el uno genera la fórmula

$$[z^m w^m] (1+z)(1+w) \sum_{q=0}^m w^q z^q.$$

Como los términos de la suma son coincidentes en sus exponentes debemos seleccionar igualmente pareja del producto en la parte delantera y estas son las $1$ y $wz$ y obtenemos dos como la respuesta cuando los comparamos a $z^m w^m$ and $z^{m-1}w^{m-1}$ a partir de la suma.

Finalmente, observe que la fórmula anterior nos permite generar secuencias fijas $n$ y consultar la OEIS para más información. Estos OEIS entradas contienen algunos muy sofisticados cerrado expresiones que muestran que podemos encontrar fórmulas en binomio los coeficientes de $n$ fijo.

Por ejemplo, no permitir que se ejecuta de longitud $3$ rendimientos $$2, 6, 14, 34, 84, 208, 518, 1296, 3254, 8196, 20700, \\ 52404, 132942, 337878, \ldots$$

que es OEIS A177790.

Del mismo modo no permitir carreras de la longitud de la $4$ rendimientos $$2, 6, 20, 62, 194, 616, 1972, 6344, 20498, 66486, 216352, \\ 705982, 2309246, 7569420, \ldots$$

que es OEIS A177792.

El lector que desee iniciar estudios adicionales de estos los números lo desea, puede consultar la siguiente Arce código donde un total de la enumeración de rutina que se presenta y la generación de funciones proporcionado. Para mostrar estas quiero señalar que con $50$ cartas a cada uno y no se ejecuta de más de siete nos permite obtener el valor

$${100\elegir 50}^{-1} 52686377360486324043397253174$$

que da $$47.78\%$$ para el complementario del suceso (hay una carrera de al menos siete cartas).

RL :=
proc(m, n)
 opción de recordar;
 local iter, res;

 res := 0;

 iter :=
 proc(zc, oc, d)
 local pos, cur, runlen;

 si zc = 0 y oc = 0, entonces
 cur := -1; pos := 1; runlen := 0;

 mientras pos <= 2*m do
 si d[pos] <> cur entonces
 cur := d[pos];
 runlen := 1;
otra cosa
 runlen := runlen + 1;

 si runlen >= n, entonces
break;
fi;
fi;

 pos := pos + 1;
od;

 si pos = 2*m+1 y runlen<n, entonces
 res := res + 1;
fi;

de retorno;
fi;

 si zc >= 1 entonces
 el iter(zc-1, oc, [op(d), 0]);
fi;
 si oc >= 1 entonces
 el iter(zc, oc-1, [op(d), 1]);
fi;

end;

 el iter(m, m, []);

res;
end;

P1 :=
proc(m, n)
 opción de recordar;
 local H;

 H := (1-z^n)*(1-w^n)*
1/((1-z)*(1-w)-w*z+w*z^n+z*w^n-w^n*z^n);

 coeftayl(coeftayl(H, z=0, m), w=0, m);
end;

Q3 :=
proc(m, n)
 opción de recordar;
 local K;

 K := añadir(z^q, q=0..n-1)*agregar(w^q, q=0..n-1)*
 agregar(w^q*z^q*añadir(z^q, q=0..n-2)^q*añadir(w^q, q=0..n-2)^q,
q=0..m);


 coef(coef(expand(K), z, m), w, m);
end;

El siguiente gráfico muestra las probabilidades cuando tenemos dieciséis tarjetas de cada color. Tenemos todas las configuraciones cuando permitimos que se ejecuta de longitud en la mayoría de los dieciséis años, obviamente.

1 + HHHHHHHHHHHHHHHHHHHHHHHHHH
 + HHHHH
 + HHH
 + HH
 + HH
0.8 H
 + H
 + H
 + H
 + HH
0.6 H
 + H
 + H
 | H
 + H
 + H
0.4 H
 + H
 + H
 + H
 + H
0.2 H
 + H
 + H
 + HH
 + H
+********+-++-++-++-++-+-++-++-++-++-++-++-++-+-++-++-++-++-
0 2 4 6 8 10 12 14 16