Suppose that I have 1 million balls ( $10^6$ ) and 1000 buckets. For each ball, I choose a bucket for it with equal probability. The task is to estimate the probability that some bucket contains more than 1250 balls, from the top.
If I define random variable $X_i$ as the number of balls in bucket $i$, then I have no idea how to estimate the maximal value of $X_i$ for $i$ from 1 to 1000 (or at least these which have more than 1250 balls in it), given just some information on just one of them.
Any hints on directions, or how to pick adequate random variables?
The required probability, $$ p\equiv\mathsf{P}\!\left(\max_{1\le i\le 1000}X_i>1250\right), $$ is hard to compute directly. A possible approximation is given in this paper. Specifically, $$ \frac{\max_{1\le i\le 1000}X_i-1111}{\sqrt{500/(3\ln(10))}}+0.5\ln(4\pi)\overset{d}{\approx}\text{Gumbel}(0,0). $$ Therefore, $p\approx e^{-e^{-17.6}}\approx 2.26\cdot10^{-8}$.