[EDITADO principalmente para informar sobre la respuesta por Kevin Costello (y para mejorar el gp de código al final)]
Doy gracias a Nicolas Dupont para la siguiente pregunta (y por el permiso para difundirlo a más):
Tengo una lista de reproducción con, digamos, $N$ piezas de la música. Mientras que el uso de la opción de reproducción aleatoria (cada pieza es jugar al azar en cada paso), me di cuenta de que, en general, tengo que escuchar un buen montón de veces la misma pieza antes de que la última aparece. Me hace pensar en la siguiente pregunta:
En el momento en que el último no ha oído hablar de la pieza que se escucha es, ¿cuál es la max, en promedio, de número de veces la misma pieza ya ha sido jugado?
No he previamente detectadas esta variante de la cupón colector del problema. Si es nuevo, entonces (el pensamiento de la original el contexto del mundo real origen del problema) me propongo llamar el "cupón coleccionista de gusano".
Es esta, de hecho, una nueva pregunta? Si no, lo que se conoce acerca de lo que ya?
Llamamos a este valor esperado $M_N$. Nicolas observa que el $M_1=1$ y $M_2=2$ (ver abajo), y le pregunta:
Me duda de que existe una fórmula fácil para general $N$ - usted sería capaz de encontrar algo de información sobre ella, por ejemplo, su comportamiento asintótico?
[Bien respondido por Kevin Costello: $M_N$ es asintótica a $e \log N$ as $N \rightarrow \infty$. Por otra parte, la máxima multiplicidad dentro de $o(\log N)$ de %de $e \log N$ con una probabilidad de $\rightarrow 1$. No recuerdo ningún otro caso de una forma natural-derivadas asintótica de la tasa de crecimiento de $e \log N$...]
Recordemos que el estándar de cupón de coleccionista problema pide el valor esperado del número total de baraja hasta que cada pieza ha aparecido al menos una vez. Es bien sabido que la respuesta es $N H_N$ donde $H_N = \sum_{i=1}^N 1/i$ es el $N$-ésimo número armónico. Por lo tanto el valor esperado de la media número de obras de teatro por pista es $H_N$, que crece como $\log N + O(1)$. El valor máximo esperado $M_N$ debe ser al menos tan grande $-$ en hecho más de una vez $N>1$, debido a que una pista se escucha sólo una vez, por lo que el promedio sobre las otras es $(N H_N-1) / (N-1)$. Uno podría pensar que $M_N$ no es mucho más grande, ya que por lo general es sólo el último par de pistas que lleva a la mayoría de la baraja a aparecer. Pero no parece fácil conseguir que la diferencia entre la máxima y la media esperada, incluso asintóticamente. A diferencia de la norma cupón colector del problema, aquí una respuesta exacta parece sin esperanza una vez $N$ está en todos los grandes (ver más abajo), así que me pregunto:
Cómo hace la diferencia $M_N - H_N$ se comportan asintóticamente como $N \rightarrow \infty$?
[Parece que esto era una maniobra de distracción: "Uno podría suponer" plausiblemente que $M_N - H_N$ es eclipsada por $H_N$ grandes $N$, pero por Kevin Costello's respuesta $M_N - H_N$ asintóticamente supera $H_N$ por un factor de $e - 1$, y ese factor es el más complicado de lo que $\lim_{N\rightarrow\infty} M_N/H_N = e$, para el análisis de la diferencia de $M_N-H_N$ no es probable que un enfoque fructífero.]
Aquí están el resto de las pocas cosas que sé acerca de esto:
@ Para cada una de las $N>1$, el valor esperado del número máximo está dada por el convergente $(N-1)$veces la suma $$ M_N = \sum_{a_1,\ldots,a_{N-1} \geq 1} N^{-\!\sum_i \! a_i} \Bigl(\sum_i a_i\Bigr)! \frac{\max_i a_i}{\prod_i a_i!}. $$ En efecto, podemos suponer sin pérdida de generalidad que el $N$-ésimo de la pista se oye el pasado; condicional en este supuesto, la probabilidad de que el $i$-ésimo de la pista que va a ser escuchado $a_i$ tiempos para cada una de las $i<N$ es $N^{-\!\sum_i \! a_i}$ multiplicado por el coeficiente multinomial $(\sum_i a_i)! \big/ \prod_i a_i!$. Numéricamente, estos valores son $$ 2.00000, \quad 2.84610+, \quad 3.49914-, \quad 4.02595\!- $$ para $N=2,3,4,5$.
@ Una forma cerrada para $M_N$ está disponible para $N \leq 3$ y probablemente no más allá. Trivialmente $M_1 = 1$; y N. Dupont ya obtenidos el valor de $M_2 = 2$ evaluando $M_2 = \sum_{a \geq 1} a/2^a$. Pero para $N=1$ e $N=2$ el problema se reduce a la clásica cupón colector del problema. Ya para $N=3$ tenemos una sorpresa: $M_3 = 3/2 + (3/\sqrt{5})$, que tiene una escuela primaria, pero un poco difícil prueba. Para $N=4$, me sale $$ M_4 = \frac73 - \sqrt{3} + \frac4\pi \int_{x_0}^\infty \frac{(2x+1) \, dx}{(x-1) \sqrt{4x^3-(4x-1)^2}} $$ donde $x_0 = 3.43968\!+$ es la más grande de las raíces (reales) de la cúbico $4x^3-(4x-1)^2$. No espero que este para simplificar aún más: la integral es el período de más de una curva elíptica de un diferencial con dos simple polos que no difieren en un punto de torsión. En general se puede reducir el $(N-1)$veces suma a una $(N-2)$veces uno (que es una ruta para el valor de $M_3$ e $M_4$), o a un $(N-3)$veces la integral, pero probablemente no más allá.
@ No es demasiado duro para simular este proceso, incluso para la considerablemente mayor $N$. En GP se puede obtener una sola muestra de la distribución desde el código
try(N) = v=vector(N); while(!vecmin(v),v[random(N)+1]++); vecmax(v)
[resulta que uno no necesita llamar a vecmin cada turno:
try(N, m,i)= v=vector(N); m=N; while(m, i=random(N)+1; v[i]++; if(v[i]==1,m--)); vecmax(v)
hace la misma cosa en $\rho+O(1)$ operaciones por shuffle en lugar de $\rho+O(N)$ donde $\rho$ es el costo de una forma aleatoria(N) de la llamada.]
Así, por ejemplo,
sum(n=1,10^4,try(100)) / 10000.
los promedios de 1000 muestras por $M_{100}$; esto toma un par de segundos, y parece dar acerca de $11.7$.
