Análise de bolas e caixas no regime m >> n.

É sabido que, se você jogar n bolas em n compartimentos, é altamente provável que a bandeja mais carregada tenha . Em geral, pode-se perguntar sobre bolas em caixas. Um artigo da RANDOM 1998 de Raab e Steger explora isso com alguns detalhes, mostrando que à medida que aumenta, a probabilidade de ir um pouco acima do valor esperado de diminui rapidamente. Aproximadamente, definindo , eles mostram que a probabilidade de ver mais de é .$O(\log n)$$m > n$m m / n r = m / n r + $n$$m$$m/n$$r = m/n$$r + \sqrt{r\log n}$$o(1)$

Este artigo foi publicado em 1998 e não encontrei nada mais recente. Existem resultados novos e ainda mais concentrados nesse sentido, ou existem razões heurísticas / formais para suspeitar que esse é o melhor possível? Devo acrescentar que um artigo relacionado sobre a variante de múltipla escolha, em co-autoria de Angelika Steger em 2006, também não cita nenhum trabalho mais recente.

Atualização : em resposta ao comentário de Peter, deixe-me esclarecer as coisas que gostaria de saber. Eu tenho dois objetivos aqui.

1. Primeiro, preciso saber qual referência citar, e parece que esse é o trabalho mais recente sobre isso.
2. Em segundo lugar, é verdade que o resultado é bastante apertado na faixa r = 1. Estou interessado no intervalo m >> n e, especificamente, no domínio em que r pode ser poly log n, ou até n ^ c. Estou tentando inserir esse resultado em um lema que estou provando, e o limite específico em r controla outras partes do algoritmo geral. Eu acho (mas não tenho certeza) que o intervalo em r fornecido por este artigo pode ser suficiente, mas eu só queria ter certeza de que não havia um limite mais restrito (que produziria um resultado melhor).

Não é realmente uma resposta completa (nem uma referência útil), mas apenas um comentário bastante extenso. Para qualquer posição, a probabilidade de ter exatamente bolas na posição será dada por . Podemos usar uma desigualdade devido a Sondow, , para produzir , em que . Observe que esse limite é bastante restrito, pois a .$B$((b+1)$p_B = \binom{m}{B} \left(\frac{1}{n}\right)^B \left(\frac{n-1}{n}\right)^{m-B}$pB<((r+1)r+$\binom{(b+1)a}{a}<\left(\frac{(b+1)^{b+1}}{b^b}\right)^a$r=$p_B < \left(\frac{(r+1)^{r+1}}{r^r}\right)^B \left(\frac{1}{n}\right)^B \left(\frac{n-1}{n}\right)^{m-B}$ ( (b+1)$r=\frac{m}{B}-1$$\binom{(b+1)a}{a}>\frac{1}{4ab}\left(\frac{(b+1)^{b+1}}{b^b}\right)^a$

Portanto, temos . Agora, como você está interessado na probabilidade de encontrar ou mais bolas em uma lixeira, podemos considerar . Reorganizando os termos, obtemos B p ≥ B = ∑ m b = B p b < Σ m b = b e b ( r + $p_B < e^{B(r+1)\ln(r+1) - Br\ln r - m\ln n + (m-B)\ln (n-1)}$$B$ p ≥ B < e - m ln $p_{\geq B} = \sum_{b=B}^{m} p_b < \sum_{b=B}^{m} e^{b(r+1)\ln(r+1) - br\ln r - m\ln n + (m-b)\ln (n-1)}$

$$p_{\geq B} < e^{-m\ln \frac{n}{n-1}} \times e^{B(r+1)\ln(r+1) - Br\ln r - B\ln (n-1)} \sum_{b=0}^{m-B} e^{b(r+1)\ln(r+1) - br\ln r - b\ln (n-1)}.$$

Observe que o somatório acima é apenas uma série geométrica; portanto, podemos simplificá-lo para fornecerSe reescrevermos termos usando exponenciais, obteremos que então se torna(r+1)r+

$$p_{\geq B} < e^{-m\ln \frac{n}{n-1}} \times e^{B(r+1)\ln(r+1) - Br\ln r - B\ln (n-1)} \times \frac{1-\left(\frac{(r+1)^{r+1}}{r^r (n-1)}\right)^{m-B+1}}{1-\left(\frac{(r+1)^{r+1}}{r^r (n-1)}\right)}.$$ p≥B<e-mln$\frac{(r+1)^{r+1}}{r^r (n-1)}$ $$p_{\geq B} < e^{-m\ln \frac{n}{n-1}} \times e^{B(r+1)\ln(r+1) - Br\ln r - B\ln (n-1)} \times \frac{1-\left(e^{(r+1)\ln (r+1) - r \ln r - \ln(n-1)}\right)^{m-B+1}}{1-e^{(r+1)\ln (r+1) - r \ln r - \ln(n-1)}},$$ $$p_{\geq B} < \frac{e^{-m\ln \frac{n}{n-1}} \times \left(e^{B((r+1)\ln(r+1) - r\ln r - \ln (n-1))} -e^{(m+1)((r+1)\ln (r+1) - r \ln r - \ln(n-1))}\right)}{1-e^{(r+1)\ln (r+1) - r \ln r - \ln(n-1)}}.$$

Agora, suponho que você se preocupe em encontrar alguns tais que para algum constante , pois isso fornece a probabilidade total de qualquer caixa com ou mais bolas limitadas por acima por . Este critério é atendido considerando que pode ser reescrito como$B$$p_{\geq B} < \frac{C}{n}$$C$$B$$C$

$$\frac{e^{-m\ln \frac{n}{n-1}} \times \left(e^{B((r+1)\ln(r+1) - r\ln r - \ln (n-1))} -e^{(m+1)((r+1)\ln (r+1) - r \ln r - \ln(n-1))}\right)}{1-e^{(r+1)\ln (r+1) - r \ln r - \ln(n-1)}} = \frac{C}{n},$$ $$B = \frac{\ln\left(\frac{C}{n} e^{m\ln \frac{n}{n-1}} \left(1-e^{(r+1)\ln (r+1) - r \ln r - \ln(n-1)}\right) + e^{(m+1)((r+1)\ln (r+1) - r \ln r - \ln(n-1))}\right)}{(r+1)\ln(r+1) - r\ln r - \ln (n-1)}.$$

Não tenho certeza de quão útil esse comentário será útil para você (é perfeitamente possível que cometi um erro em algum lugar), mas espero que possa ser útil.