3
$\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 Answer 1

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$
3
  • $\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$ Jun 17, 2013 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$ Jun 17, 2013 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, 2013 at 19:29

You must log in to answer this question.

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