Rollo de una N colindado mueren K veces. Sea S el lado que apareció con más frecuencia. ¿Cuál es el número esperado de veces que S aparecieron?

Question

Por ejemplo, considere una de las 6 caras morir laminado de 10 veces. Basado en la siguiente simulación monte-carlo, me sale que el lado que aparece con más aparecerá el 3,44 veces en promedio.

n = 6
k = 10
samples = 10000
results = []

for _ in range(samples):
    counts = {s:0 for s in range(n)}
    for _ in range(k):
        s = randint(0, n-1)
        counts[s] += 1

    results.append(max(counts.values()))

print sum(results)/float(len(results))

Pero no puedo averiguar cómo conseguir esto en una forma cerrada para cualquier N y K.

Answer 1

No una respuesta, pero vale la pena intentarlo algún ejemplo con pequeño $N$.

Deje $M$ ser su número.

Para $n=2$, y cualquier $k/2 < m \leq k$$P(M=m)=\frac{\binom{k}{m}}{2^{k-1}}$. Si $k$, incluso, a continuación,$P(M=k/2)=\frac{\binom{k}{k/2}}{2^k}$.

Así, por $k=2j+1$ impar, se tiene:

$$\begin{align}E(M)&=\frac{1}{2^{2j}}\sum_{m=j+1}^{2j+1} m\binom{2j+1}{m}\\ &=\frac{2j+1}{2^{2j}}\sum_{m=j+1}^{2j+1}\binom{2j}{m-1}\\ &=\frac{2j+1}{2^{2j}}\sum_{m=j}^{2j}\binom{2j}{m}\\ &=\frac{2j+1}{2^{2j}}\left(\frac{1}{2}2^{2j}+\frac{1}{2}\binom{2j}{j}\right)\\ &=\frac{k}{2}\left(1+\frac{\binom{k-1}{(k-1)/2}}{2^{k-1}}\right) \end{align}$$

Para$N=2$$k=2j$, se obtiene: $$ \begin{align}E(M)&=j\frac{\binom{2j}{j}}{2^{2j}}+\frac{1}{2^{2j-1}}\sum_{m=j+1}^{2j}m\binom{2j}{m}\\ &=j\frac{\binom{2j}{j}}{2^{2j}}+\frac{2j}{2^{2j-1}}\sum_{m=j+1}^{2j}\binom{2j-1}{m-1}\\ &=j\frac{\binom{2j}{j}}{2^{2j}}+\frac{j}{2^{2j-2}}\cdot\frac{2^{2j-1}}{2}\\ &=\frac{k}{2}\left(1+\frac{\binom{k}{k/2}}{2^k}\right) \end{align}$$

Se va a poner complicada cuando se trata de ti para $N=3$.

Answer 2

Aquí es una forma cerrada, se necesitan métodos más sofisticados para la asymptotics.

Siguiendo la notación introducida en este MSE enlace suponemos que la muerte ha $m$ caras y se enrolla $n$ veces. Lanzar el dado con la mayoría de ocurrido el valor que se $q$ e instancias de este tamaño marcado de los rendimientos de las especies

$$\mathfrak{S}_{=m} (\mathfrak{P}_{y=0}(\mathcal{Z}) + \mathfrak{P}_{=1}(\mathcal{Z}) + \cdots + \mathcal{V}\mathfrak{P}_{=q}(\mathcal{Z})).$$

Esto ha generando función

$$G(z,v) = \left(\sum_{i=0}^{p-1} \frac{z^r}{r!} + v\frac{z^p}{q!}\right)^m.$$

Restando los valores donde los conjuntos de tamaño $q$ no se producen obtenemos la generación de la función

$$H_{p}(z) = \left(\sum_{i=0}^{q} \frac{z^r}{r!}\right)^m - \left(\sum_{i=0}^{p-1} \frac{z^r}{r!}\right)^m.$$

Esto también se sigue más o menos por la inspección.

Se obtiene por la cantidad deseada de la forma cerrada

$$\bbox[5px,border:2px solid #00A000]{ \frac{n!}{m^n} [z^n] \sum_{q=1}^n q H_q(z).}$$

La introducción de

$$L_{p}(z) = \left(\sum_{i=0}^{q} \frac{z^r}{r!}\right)^m$$

por lo tanto, tienen

$$\frac{n!}{m^n} [z^n] \sum_{q=1}^n q (L_{q}(z) - L_{q-1}(z)).$$

Este es

$$\frac{n!}{m^n} [z^n] \left(n L_n(z) - \sum_{q=0}^{n-1} L_q(z)\right).$$

También tenemos para

$$[z^n] L_q(z) = \sum_{k=0}^{\min(p, n)} \frac{1}{k!} [z^{n-k}] \left(\sum_{i=0}^{q} \frac{z^r}{r!}\right)^{m-1}$$

Además obtenemos para $m=1$

$$[z^n] L_q(z) = [[n \le p]] \times \frac{1}{n!}.$$

Con estos se puede implementar una recursividad, que de hecho en que se está codificada resultó inferior a la de Maple rápida multiplicación de polinomio rutinas. Es se incluye aquí porque memoizes coeficientes de $L_q(z)$, lo que proporcionar una dramática la velocidad de las parcelas en el costo de la asignación de más de memoria.

Todo esto da como resultado el siguiente gráfico donde hemos reducido la trama por un factor de $n/m.$ Esto es para una de las seis caras de morir:

 3+ H 
 + 
 | H 
 + H 
 | 
 + H 
 + HH 
 | HH 
 2+ HH 
 | HHH 
 + HHHH 
 + HHHHHHH 
 | HHHHHHHHHHH 
 + HHHHHHHHHHHHHHHHHHHHHHHHH 
 | HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH 
 -+--+---+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+-- 
 0 20 40 60 80 100 120 

Y aquí está la parcela por un período de doce caras de morir. (Considero que vale la pena la observación de que tenemos el exacto valor de la expectativa en el caso de $120$ rollos de este morir, un número de casos que ha $130$ dígitos, similar a lo que apareció en el compañero del post.)

 8+ 
 | 
 + 
 + 
 | 
 + 
 + H 
 | 
 6+ 
 | 
 + 
 + 
 | H 
 + 
 + H 
 | 
 4+ HH 
 + H 
 | H 
 + HH 
 + HH 
 | HHHH 
 + HHHHHH 
 2+ HHHHHHHHHHH 
 | HHHHHHHHHHHHHHHHHHHHHHHHH 
 + HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH 
 -+--+---+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+-- 
 0 20 40 60 80 100 120 

Este fue el Arce de código.

con(parcelas);
con(planta);

ENUM :=
proc(n, m)
opción de recordar;
local rollos, res, ind, cuenta, por lo menos, la mayoría de los;
 res := 0;

 para la ind de la m^n 2*m^n-1 hacer
 rollos := convert(ind, base, m);

 cuenta := map(mel->op(2, mel),
 convertir(rollos[1..n], `conjunto múltiple`));

 res := res + max(cuenta);
od;

res/m^n;
end;

L := (m, rmáx) -> add(z^r/r!, r=0..rmax)^m;

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

 H := q -> expand(L(m,p)-L(m,q-1));

n!/m^n*
 coef(añadir(q*H(q), q=1..n), z, n);
end;

LCF :=
proc(n,m,p)
 opción de recordar;

 si n < 0 then return 0 fi;

 si m = 1 entonces
 si n <= q entonces devolver 1/n! fi;
 return 0;
fi;

agregar(1/k!*LCF(n-k,m-1,p),k=0..min(p,n));
end;

LVERIF :=
(m, q) -> add(LCF(n, m, p)*z^n, n=0..p*m);

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

 res :=
 n*LCF(n,m,n) - agregar(LCF(n,m,p), q=0..n-1);

res*n!/m^n;
end;


DICEPLOT :=
proc(nmx), m)
local pt;

 pts := [seq([n, XX(n,m)/(n/m)], n=1..nmx)];
pointplot(pts);
end;