Este problema era interesante, así que lo probé y, para mi sorpresa, lo conseguí. Bueno, si se tiene en cuenta la creación de una función recursiva (en forma de programa Python) que calcula rápidamente el resultado deseado - 2 segundos en mi máquina para n=50,k=20. Esto podría ser fácilmente optimizado aún más. Tal vez ayude a alguien a encontrar una solución más "pura".
De todos modos, este es mi razonamiento:
Tomemos un resultado del lanzamiento, y reetiquetemos los dados para que el valor más frecuente sea $1$ el siguiente más frecuente es $2$ y así sucesivamente hasta $k$ . Por ejemplo, el lanzamiento 1-3-2-3-3 se convertirá en 3-1-2-1-1 o 2-1-3-1-1.
Como puede ver, si hay "empates" hay múltiples formas de realizar este reetiquetado. Por ejemplo, si el resultado es 5-5-1-1-3-3-2-2-4-4, entonces 1, 2 y 3 aparecen 3 veces y 4 y 5 aparecen dos veces, por lo que hay $3!\times 2!$ formas de hacer el reetiquetado. Dado un reetiquetado $r$ denotaremos el número de reetiquetados equivalentes por $c(r)$ que viene dado por el producto de los factoriales del número de veces que se repite cada frecuencia de valores.
Además, dado un reetiquetado con $l\leq k$ etiquetas, hay $\frac{k!}{(k-l)!}$ resultados que pueden ser reetiquetados de esta manera. (Por ejemplo, si sólo se utilizan 2 de 4 etiquetas, hay 4 opciones para la primera etiqueta y 2 para la segunda).
Obviamente, el número de unos en un reetiquetado es igual al número de veces que el valor más común aparece en un resultado que puede ser reetiquetado de esta manera. Cualquier recuento que hagamos de los reetiquetados sobrecontará los resultados reales por un factor de $c(r)$ y los subestima por un factor de $\frac{k!}{(k-l)!}$ .
Así que $p_m$ la probabilidad de que se produzca el valor más frecuente $m$ veces, viene dada por
$$ p_m = \sum_{r \, \in \, R_m} p(r)\frac{1}{c(r)} \frac{k!}{(k-l(r))!}, $$
donde $R_m$ es el conjunto de reetiquetas que contienen exactamente $m$ los, y $p(r)$ es la probabilidad de obtener el resultado $r$ en un lanzamiento. $p(r)$ es de hecho $\frac{1}{k^n}$ .
Tenga en cuenta que la cantidad que busca es el valor esperado de la mayor frecuencia de valores de los dados, y por definición de valores esperados, esto es simplemente:
$$ \sum_{1 \leq m \leq n} p_m. $$
Así que una rápida simplificación:
$$ p_m = \frac{1}{k^n}\sum_{r \, \in \, R_m} \frac{1}{c(r)}\frac{k!}{(k-l(r))!}. $$
Ahora, vamos a ordenar los reetiquetados, por ejemplo, 3-2-3-1-1-1-2 se convierte en 1-1-1-1-2-2-3-3. Tenga en cuenta que esto no afecta a $c(r)$ o $l(r)$ .
Entonces, ¿cuántas reetiquetas corresponden a un clasificado ¿recalificación? En el ejemplo anterior es $\frac{8!}{4! \times 2! \times 2!}$ . En general, llamemos a esta cantidad $s(r)$ que viene dado por el producto de los factoriales del número de veces que se repite cada etiqueta.
Finalmente tenemos
$$ p_m = \frac{1}{k^n}\sum_{r \, \in \, S_m} \frac{s(r)}{c(r)}\frac{k!}{(k-l(r))!}, $$
donde $S_m$ es el conjunto de clasificado reetiquetas que contienen exactamente $m$ los.
Para los pequeños $n$ En el caso de los números, es posible calcularlos a mano, ya que se trata de decir "¿cuántos 1s? ¿cuántos 2s?", etc. Sin embargo, hagamos que el ordenador lo haga.
Aquí hay un script que he probado contra una simulación numérica y los resultados parecen correctos.
#given n dice and k labels, find the "average" count of
#the most commonly occuring value
def avg(n, k):
return sum(prob(n, k, i) * i for i in range(1, n+1))
#given n dice and k labels, find the probability that
#the most common value occurs c times
def prob(n, k, c):
return 1./(k**n) * fact(n) * 1./fact(c) * calc(n - c, k - 1, c, 1) * k
# 1./fact(c) contributes to s(r)
# k contributes to c(r)
#given n remaining dice and l remaining labels, all of which must occur
#with frequency <= prev_freq, and an existing runlength
#this function tries to give the next label to every allowable number of dice
#and sums the results
def calc(n, l, prev_freq, runlength):
#all dice accounted for
if n == 0:
return 1.0
#not enough labels to give remaining dice
if n > l * prev_freq:
return 0.0
term_sum = 0
if prev_freq <= n:
freq = prev_freq
#same freq as previous label
term_sum = (1./fact(freq) * calc(n - freq, l - 1, freq, runlength + 1)
/ (runlength + 1))
# 1./fact(freq) contributes to s(r)
# 1./(runlength + 1) contributes to c(r)
for freq in range(1, min(prev_freq, n + 1)):
#smaller freq than previous label
term_sum += 1./fact(freq) * calc(n - freq, l - 1, freq, 1)
return term_sum * l
# l contributes to k! / (k - l(r))!
#factorial
def fact(n):
prod = 1
for i in range(2, n+1):
prod *= i
0 votos
¿y si tiene dos (o más) valores "más comunes"?