Upper bound for probability of no collision for two balls-into-bins processes

Instead of forcing the situation to suit the existing theorem (for the single-process balls-into-bins) described in the post and found in standard references, we prove a new theorem specifically for the two-process case.

First, we show that the Poisson approximation holds for the general multinomial distribution $(p_1, \dots, p_n)$, and not just for the uniform case ($p_i = \frac{1}{n}$), which is the case typically handled in the literature.

---

Theorem 1 (Poisson Approximation for a Single Process)

Let $X = (X_1, \dots, X_n) \sim \mathrm{Multinomial}(m, p_1, \dots, p_n)$, and let $Y = (Y_1, \dots, Y_n)$, where the $Y_i$ are independent and $Y_i \sim \mathrm{Poisson}(m p_i)$. Let $f : \mathbb{N}^n \to \mathbb{R}_{\geq 0}$ be any non-negative function such that $\mathbb{E}[f(X_1, \dots, X_n)]$ is either monotonically increasing or decreasing in $m$. Then:

$$ \mathbb{E}[f(X_1, \dots, X_n)] \leq 2 \cdot \mathbb{E}[f(Y_1, \dots, Y_n)]. $$

In particular, if $ e $ is an event (depending only on the vector of bin occupancies) that is monotone in the number of balls $ m $, then: $$ \Pr[e(X)] \leq 2 \cdot \Pr[e(Y)]. $$

---

Proof Sketch:

Let us assume without loss of generality that $ f $ is increasing in $ m $ (the decreasing case is analogous).

Let $ Z = \sum_{i=1}^n Y_i $. Note that $ Z \sim \mathrm{Poisson}(m) $, and conditioned on $ Z = m $, the vector $ (Y_1, \dots, Y_n) \sim \mathrm{Multinomial}(m, p_1, \dots, p_n) $—this is a standard fact in Poisson approximation (see e.g., Mitzenmacher and Upfal for the multinomial uniform case; the general multinomial case is similar).

We use the law of total expectation:

$$ \mathbb{E}[f(Y)] \geq \mathbb{E}[f(Y) \mid Z \geq m] \cdot \Pr(Z \geq m). $$

Since $ f $ is increasing, conditioning on $ Z \geq m $ increases the expectation. In particular, $ \mathbb{E}[f(Y) \mid Z = m] = \mathbb{E}[f(X)] $, so:

$$ \mathbb{E}[f(Y) \mid Z \geq m] \geq \mathbb{E}[f(Y) \mid Z = m] = \mathbb{E}[f(X)]. $$

It is a known result (Mitzenmacher and Upfal, Exercise 5.11) that if $ Z \sim \mathrm{Poisson}(\mu) $ with $ \mu \geq 1 $ an integer, then:

$$ \Pr(Z \geq \mu) \geq 1/2 \quad \text{and} \quad \Pr(Z \leq \mu) \geq 1/2. $$

Therefore:

$$ \mathbb{E}[f(Y)] \geq \mathbb{E}[f(X)] \cdot \Pr(Z \geq m) \geq \frac{1}{2} \cdot \mathbb{E}[f(X)]. $$

(For the decreasing case we just use $ \Pr(Z \leq \mu) \geq 1/2 $ from Exercise 5.11.)

---

Theorem 2 (Poisson Approximation for Two Independent Processes)

Let $ A = (A_1, \dots, A_n) \sim \mathrm{Multinomial}(m, p_1, \dots, p_n) $, and independently $ B = (B_1, \dots, B_n) \sim \mathrm{Multinomial}(m, q_1, \dots, q_n) $. Let $ C = (C_1, \dots, C_n) $, $ D = (D_1, \dots, D_n) $ be independent Poisson vectors where $ C_i \sim \mathrm{Poisson}(m p_i)$ and $D_i \sim \mathrm{Poisson}(m q_i) $.

Let $ f : \mathbb{N}^{2n} \to \mathbb{R}_{\geq 0} $ be a non-negative function such that $ \mathbb{E}[f(A_1, \dots, A_n, B_1, \dots, B_n)] $ is either monotonically increasing or decreasing in $ m $. Then:

$$ \mathbb{E}[f(A, B)] \leq 4 \cdot \mathbb{E}[f(C, D)]. $$

That is, the Poisson approximation is a 4-approximation for monotonic events over two independent multinomial processes with general bin probabilities.

---

Proof:

We apply Theorem 1 twice using the law of total expectation. Again assume without loss of generality that $ f $ is increasing in $ m $.

First, condition on $ B $. Then $ f(A, B) $ as a function of $ A $ is still increasing. So:

$$ \mathbb{E}[f(A, B)] = \mathbb{E}_B\left[ \mathbb{E}[f(A, B) \mid B] \right] \leq \mathbb{E}_B\left[ 2 \cdot \mathbb{E}[f(C, B) \mid B] \right] = 2 \cdot \mathbb{E}[f(C, B)]. $$

Now, we apply the law of total expectation again, this time conditioning on $ C $. Since $ f(C, B) \mid C $ is increasing in $ B $, we apply Theorem 1 again:

$$ \mathbb{E}[f(C, B)] = \mathbb{E}_C\left[ \mathbb{E}[f(C, B) \mid C] \right] \leq \mathbb{E}_C\left[ 2 \cdot \mathbb{E}[f(C, D) \mid C] \right] = 2 \cdot \mathbb{E}[f(C, D)]. $$

Putting it all together:

$$ \mathbb{E}[f(A, B)] \leq 2 \cdot \mathbb{E}[f(C, B)] \leq 4 \cdot \mathbb{E}[f(C, D)]. $$

---

This gives us a general Poisson approximation result for any monotonic event over two balls-into-bins processes. In particular, if $ e $ is any monotone event, we have:

$$ \Pr[e(A, B)] \leq 4 \cdot \Pr[e(C, D)]. $$

---

From here I supposed we can use Jensen's inequality, Lagrange multiplier optimization, or, using Taylor series, upper bound the positive $e^x$ terms and lower bound the negative $e^y$ terms, in order to reach the goal of an upper bound of the form $n^{-c'}$. I don't include this as part of the answer since I did not try this thoroughly (as I discovered my case is even more difficult than I thought, two different distributions p and q), but for my quick attempts these seem to have worked fine.