Probability of higher occurrence of an element within a random permutation with repetition 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.
 A: 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.
