Skip to main content
6 votes
Accepted

Filling bins with pairs of balls

TL;DR -- No, there is no better strategy than the simple strategy. Here is the main idea of the proof. When there are not enough balls, there will be a "ball path" from a $k$-full bin to a bin with ...
John L.'s user avatar
  • 39.1k
1 vote
Accepted

Distribution maximizing ratio of expected maximum over the mean

For non-negative random variables, the answer is $\Theta(n)$. Notice that $Y \leq X_1 + \cdots + X_n$, and so $E[Y] \leq n E[X]$. In the other direction, consider the following random variable: $X = 1$...
Yuval Filmus's user avatar
1 vote

Assigning $m$ balls to $n$ buckets - recursive algorithm

An assignment of balls into $n$ bins falls into either one of the following two cases. Every bin has as last one ball. So let us assign one ball to each bin first. What remains to do is to assign the ...
John L.'s user avatar
  • 39.1k

Only top scored, non community-wiki answers of a minimum length are eligible