2
$\begingroup$

I generate $n$ random numbers, each one from a set $X={1,\ldots,N}$, where $n\geq N$. This results in a random permutation with repetition of length $n$ over $X$. Ideally for me, each number of $X$ would occur in a generated permutation $n/N$ times. Is there any way, how to calculate a probability that within a generated random permutation, any number from $X$ will occur more than $\alpha\cdot n/N$ times?

I am looking for a way other than testing all possible permutations, since my numbers are quite high, e.g., $N=10^5$, $n=10^{13}$. I assume an ideal random number generator with uniform distribution.

My question is motivated by the problem of random distribution of $n$ elements among $N$ processors. Ideally, each processor will get $n/N$ elements, and I want to know what is the probability of a load imbalance, e.g., for $\alpha=1.05$, thus that some processor will get at least $1.05$ times more elements than is their ideal per-processor count.

$\endgroup$
1
$\begingroup$

This is a neat problem as it uses both a multinomial distribution and the principle of inclusion/exclusion. The end result is not a particularly nice expression, but it is easily computable (which is what I am assuming you would like to do). Let $$ f\left(x_{1},\ldots,x_{N};n,p_{1},\ldots,p_{N}\right)=\begin{cases} \frac{n!}{x_{1}!\ldots x_{N}!}p_{1}^{x_{1}}\ldots p_{N}^{x_{N}} & \text{if }\sum_{i}x_{i}=n\\ 0 & \text{otherwise} \end{cases} $$ be the probability mass function for a multinomial distribution (see https://en.wikipedia.org/wiki/Multinomial_distribution for a more thorough definition). Let $\alpha n/N=m$, and assume $m$ is a positive integer. We say $j\in\left\{ 1,2,\ldots,N\right\} $ is a category. Because $p_{j}=p$ is constant over $j$ in your problem, let's define $$ g\left(\mathbf{x};n,p\right)\equiv f\left(x_{1},\ldots,x_{N};n,p,\ldots,p\right) $$ to simplify notation ($\mathbf{x}$ denotes the vector with components $x_{1},\ldots,x_{N}$). Let $\mathbf{e}^{j}$ denote the $j^{\text{th}}$ Euclidean basis vector (i.e. $0$s everywher save for a $1$ in position $j$). For a vector $y\in\mathbb{N}^{N}$, define the norm $$ \left|y\right|\equiv y_{1}+y_{2}+\ldots+y_{N}. $$ If $n<2m$, only 1 category $j\in\left\{ 1,2,\ldots,N\right\} $ can be witnessed $m$ times. Hence, for $n<2m$, the answer to your problem is $$ K_{N,n,m}=\sum_{j=1}^{N}\sum_{k=m}^{n}\sum_{\substack{\left|\mathbf{y}\right|=n-k\\ y_{j}=0 } }g\left(\mathbf{y}+k\mathbf{e}^{j};n,\frac{1}{N}\right), $$ where the summation $\sum_{\left|\mathbf{y}\right|=c}$ is understood as over all vectors in $y\in\mathbb{N}^{N}$ with $\left|y\right|=c$. Because of the symmetry in your problem, we can further reduce this to $$ K_{N,n,m}=N\sum_{k=m}^{n}\sum_{\substack{\left|\mathbf{y}\right|=n-k\\ y_{1}=0 } }g\left(\mathbf{y}+k\mathbf{e}^{1};n,\frac{1}{N}\right). $$ However, if $n\geq2m$, the above expression for $K_{N,n,m}$ no longer holds. Instead, we must account for overcounting using the princple of inclusion/exclusion. I will omit the details, as the notation gets pretty messy, but perhaps you can extrapolate from what I've given you and make the necessary modifications. If not, I can steer you in the right direction in the comments.

$\endgroup$
  • $\begingroup$ Thanks much for your answer, I will try to understand it or to get some help from our mathematicians :). In most our cases, $n\geq 2m$ will hold. $\endgroup$ – Daniel Langr Jun 17 '13 at 9:28
  • $\begingroup$ Just one more thing - don't you know about some literature that deals with this problem (or some similar ones)? It would be fine to cite it. $\endgroup$ – Daniel Langr Jun 17 '13 at 9:30
  • $\begingroup$ $n\geq 2m$ is the case where you have to apply the principle of inclusion/exclusion. As for the literature, it's a combination of the multinomial distribution and the principle of inclusion/exclusion. Do not have anything off the top of my head that does this exactly. Also, I would spend some time and make sure that nothing more clever exists. This is sort of a brute-force approach. $\endgroup$ – parsiad Jun 17 '13 at 19:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.