EmptySoulist's blog

By EmptySoulist, history, 5 months ago,

One day I thought of an interesting problem :

“ Given $n$ elements that are initially $0$, operate $k$ times, each time will randomly select an element, increase it by $1$, and find the expected value of the maximum value among the $n$ elements”

I used to think it was a very simple problem (at the beginning), but actually I couldn't find any good solution (at the beginning, I only knew an $O(k^2\ln k)$ solution)

After asking some powerful people, I learned one way to solve this problem in $O(\textrm{poly}~k^{\frac{5}{3}})/O(n\cdot k^{1.5})$. (thanks them.)

It is unimaginable to me that the solution of a seemingly simple problem is so difficult, Could any one find a better solution? Thank you !