Análisis de bolas y contenedores en el régimen m >> n.

17

Es bien sabido que si arrojas n bolas en n contenedores, es muy probable que el contenedor más cargado tenga O(Iniciar sesiónnorte) bolas en él. En general, uno puede preguntar acerca de bolas en contenedores. Un artículo de RANDOM 1998 de Raab y Steger explora esto con cierto detalle, mostrando que a medida que aumenta m , la probabilidad de ir incluso un poco por encima del valor esperado de m / n disminuyó rápidamente. Aproximadamente, estableciendo r = m / n , muestran que la probabilidad de ver más de r + m>nnmm/nr=m/nr+rlogn es.o(1)

Este artículo apareció en 1998, y no he encontrado nada más reciente. ¿Hay resultados nuevos e incluso más concentrados en este sentido, o hay razones heurísticas / formales para sospechar que esto es lo mejor que se puede obtener? Debo agregar que un documento relacionado sobre la variante de opción múltiple en coautoría de Angelika Steger en 2006 tampoco cita ningún trabajo más reciente.

Actualización : en respuesta al comentario de Peter, déjenme aclarar las cosas que me gustaría saber. Tengo dos objetivos aquí.

  1. En primer lugar, necesito saber qué referencia citar, y parece que este es el trabajo más reciente sobre esto.
  2. En segundo lugar, es cierto que el resultado es bastante ajustado en el rango r = 1. Estoy interesado en el rango m >> n, y específicamente en el reino donde r podría ser poly log n, o incluso n ^ c. Estoy tratando de ubicar este resultado en un lema que estoy probando, y el límite específico en r controla otras partes del algoritmo general. Creo (pero no estoy seguro) que el rango de r provisto por este documento podría ser suficiente, pero solo quería asegurarme de que no hubiera un límite más estricto (que daría un mejor resultado).
Suresh Venkat
fuente
3
Aprendí el nombre "problema de ocupación" de la etiqueta, así que gracias por publicar una pregunta educativa. :)
Tsuyoshi Ito
77
Mirando el papel de Raab y Steger, es difícil para mí averiguar qué resultados adicionales desearía en este sentido. ¿Hay una pregunta específica para la que necesita saber la respuesta? Si es así, debe preguntarlo, ya sea aquí o en MathOverflow. En particular, si , Raab y Steger dan un estrecho límite de r + r=m/n donde2es la constante correcta. r+2rlogn2
Peter Shor el
@ Peter Editaré la pregunta: es un punto válido.
Suresh Venkat

Respuestas:

8

No es realmente una respuesta completa (ni una referencia útil), sino un comentario más bien extendido. Para cualquier bin dado, la probabilidad de tener exactamente bolas en el bin estará dada por p B = ( mB. Podemos usar una desigualdad debido a Sondow,((b+1)apB=(mB)(1n)B(n1n)mB, para producirpB<((r+1)r+1((b+1)aa)<((b+1)b+1bb)a, donder=mpB<((r+1)r+1rr)B(1n)B(n1n)mB. Tenga en cuenta que este límite es bastante ajustado, ya que a ( (b+1)ar=mB1.((b+1)aa)>14ab((b+1)b+1bb)a

Así tenemos . Ahora, dado que está interesado en la probabilidad de encontrar B o más bolas en un contenedor, podemos considerar p B = m b = B p b <pB<eB(r+1)ln(r+1)Brlnrmlnn+(mB)ln(n1)BpB=b=Bmpb<b=Bmeb(r+1)ln(r+1)brlnrmlnn+(mb)ln(n1)

pB<emlnnn1×eB(r+1)ln(r+1)BrlnrBln(n1)b=0mBeb(r+1)ln(r+1)brlnrbln(n1).

Note the summation above is merely a geometric series, so we can simplify this to give

pB<emlnnn1×eB(r+1)ln(r+1)BrlnrBln(n1)×1((r+1)r+1rr(n1))mB+11((r+1)r+1rr(n1)).
If we rewrite (r+1)r+1rr(n1) terms using exponentials, we get
pB<emlnnn1×eB(r+1)ln(r+1)BrlnrBln(n1)×1(e(r+1)ln(r+1)rlnrln(n1))mB+11e(r+1)ln(r+1)rlnrln(n1),
which then becomes
pB<emlnnn1×(eB((r+1)ln(r+1)rlnrln(n1))e(m+1)((r+1)ln(r+1)rlnrln(n1)))1e(r+1)ln(r+1)rlnrln(n1).

Now, I take it you care about finding some B such that pB<Cn for some constant C, since this gives the total probability of any bin having B or more balls as bounded from above by C. This criteria is satisfied by taking

emlnnn1×(eB((r+1)ln(r+1)rlnrln(n1))e(m+1)((r+1)ln(r+1)rlnrln(n1)))1e(r+1)ln(r+1)rlnrln(n1)=Cn,
which can be rewritten as
B=ln(Cnemlnnn1(1e(r+1)ln(r+1)rlnrln(n1))+e(m+1)((r+1)ln(r+1)rlnrln(n1)))(r+1)ln(r+1)rlnrln(n1).

I'm not entirely sure how useful this comment will be to you (it's entirely possible I've made a mistake somewhere), but hopefully it can be of some use.

Joe Fitzsimons
fuente
1
this is pretty awesome. thanks for the outline.
Suresh Venkat
@Suresh: Glad it's useful.
Joe Fitzsimons