0
$\begingroup$

Let $U_1, ..., U_n$ be Poisson random variables with rates $ \lambda_1, ..., \lambda_n$ such that $\lambda =\sum_i \lambda_i = O(1)$ (i.e the sum of the rates is bounded). Suppose we have $n$ buckets. We get a uniformly random permutation $\sigma\in \mathbb{S}_n$, and sample from $U_{\sigma(i)}$ balls into bucket $i$. Hence, the buckets have $B_1, ..., B_n$ balls. I am interested in the joint distribution of $(B_1, \ldots, B_n)$ as $n\to +\infty$.

Experimentally, $(B_1, ..., B_n)$ is distributed as $(R_1, ..., R_n)$ where $ R_i \sim Poisson(\frac{\lambda}{n})$ are independent, however I am not able to prove this. I am able to prove that the variational distance $d(B_i, R_i) = O(1/n)$, but this is not sufficient to conclude that the joint distributions behave the same as $n\to +\infty$ with the triangle inequality. Any ideas?

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
2
$\begingroup$

Suppose for example $\lambda_1=10000$, $\lambda_2=1000$, and all the other $\lambda_i$ sum to less than $1$.

Then with probability greater than $0.999$ for all sufficiently large $n$, you will see precisely one value $B_i$ in the range $(5000,15000)$, precisely one value in the range $(500,1500)$, and all the other values less than $50$. Of course this kind of behaviour couldn't hold in the case of a collection of i.i.d. random variables such as your $(R_1,\dots, R_n)$.

Whether "the joint distributions behave the same as $n\to\infty$"? - well, it depends precisely what you mean by that! But for example in the case above, it's not true that the total variation distance between $(B_1,\dots, B_n)$ and $(R_1,\dots, R_n)$ tends to $0$.

If I understand right, the property $d(B_i, R_i)=O(1/n)$ holds for rather trivial reasons; because of your assumption that $\lambda$ is bounded as $n\to\infty$, both $B_i$ and $R_i$ take the value $0$ with probability $1-O(1/n)$.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I see, thank you. The property I need is that $\Pr[B_1=k_1, ..., B_n=k_n]\geq \Pr[R_1=k_1, ..., R_n=k_n] - O(1/n)$ (and I wrongly assumed that perhaps the the variational distance between them goes to zero as $n\to +\infty$ that justifies the inequality). Perhaps I can use something else here such as negative association of the permutation distribution to get the above inequality. Any ideas? (Or should I post this as a separate question?) $\endgroup$
    – AspiringMat
    Commented Sep 17, 2023 at 20:05
  • 2
    $\begingroup$ I think your property does hold, but again for rather degenerate reasons. You have equality in the case $k_1=k_2=\dots=k_n=0$, when both probabilities equal $e^{-\lambda}$. And then for literally any other way of choosing $k_1, \dots, k_n$, both the probabilities are within $O(1/n)$ of $0$. Indeed if some given $k_i$ is non-zero, then $P(B_i=k_i)\leq P(B_i>0)\leq \lambda/n$ and similarly for $R_i$, so both probabilities are less than $\lambda/n$. $\endgroup$
    – James Martin
    Commented Sep 17, 2023 at 20:33

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .