Maximum load is $O(\log\log n/\log\log\log n)$ There are $n$ bins labeled $0,1,\ldots,n-1$, and $\log_2n$ players. Each player chooses a starting location $k$ uniformly at random, and places one ball in each of the bins $$k\bmod n,k+1\bmod n,\ldots,k+n/\log_2n-1\bmod n.$$ Show that the maximum number of balls in any bin is $O(\log\log n/\log\log\log n)$ with high probability as $n\rightarrow\infty$.
I'm not really sure how to start here.
 A: For simplicity, when I say $\log n$, I mean $\log_2 n$.
I use Lemma 5.1 from the book "Probability and Computing":
When n balls are thrown independently and uniformly at random into $n$ bins, the probability that the maximum load is more than $3 \ln n / \ln \ln n$ is at most $1 / n$ for sufficiently large $n$.
Let $X_i$ be a random variable denoting the number of balls in bin $i$. It is equivalent to number of player whose starting location is between $i - n / \log n + 1$ and $i$.
Now, consider the set of variables $V = \{X_1, X_{1+n / \log n}, X_{1+2 n / \log n}, \ldots$ } -- that is, $X_i$ where $i$ is congruent to $1$ modulo $n / \log n$. Note that there are $\log n$ such variables. Consider each player as a ball and each random variable as a bin -- when a player select as its starting position $k$, then from amongst these variables there exist exactly one variable whose value is increased by $1$. Since there are $\log n$ players and the players throw the balls uniformly at random, we can use Lemma 5.1 and thus the probability that the any of the $X_i$ is more than $3 \ln \log n / \ln \ln \log n$ is at most $1 / \log n$. Thus, with probability at least $1 - 1 / \log n$, none of the variables in $P$ is above $3 \ln \log n / \ln \ln \log n$.
Now, consider $X_i$, where $i$ is not congruent to $1$ modulo $N / \log n$. It is equivalent to number of player whose starting location is between $i - n / \log n + 1$ and $i$, thus, this value is bounded by at most the sum of two variables in $V$. Thus, if we know that none of the variables in $V$ is above $3 \ln \log n / \ln \ln \log n$, then no variables $X_i$ is above $6 \ln \log n / \ln \ln \log n$. Thus, the probability that no variables $X_i$ is above $6 \ln \log n / \ln \ln \log n$ is at least $1 - 1 / \log n$, which approaches $1$ as $n$ approaches infinity.
