$Y_1, Y_2, Y_3,...,Y_n$ are independent and identically distributed random variables and they have uniform distribution on ${\{1,...,m\}}$.

Prove that for $n\le k\le mn$, we have

$$P(Y_1+Y_2+Y_3+...+Y_n=k)=\frac 1 {m^n} \sum_{0\le i \le(k-n)/m} (-1)^i \binom{n}{i} \binom{k-mi-1}{n-1}$$

So I think this is related to the binomial formula with $$\{1+x\}^a=\sum_{i=0}^{\infty}\binom{a}{i}x^i$$ where $|a| \lt 1$. How would I transform this formula to the given identity in the question?


Supposing that an algebraic proof is sought here we have from first principles for the probability that it is

$$\frac{1}{m^n} [z^k] (z+\cdots+z^m)^n.$$

Using basic algebra this becomes

$$\frac{1}{m^n} [z^k] z^n (1+\cdots+z^{m-1})^n \\ = \frac{1}{m^n} [z^{k-n}] \frac{(1-z^m)^n}{(1-z)^n} \\ = \frac{1}{m^n} [z^{k-n}] \frac{1}{(1-z)^n} \sum_{q=0}^n {n\choose q} (-1)^q z^{mq} \\ = \frac{1}{m^n} \sum_{q=0}^n {n\choose q} (-1)^q [z^{k-n-qm}] \frac{1}{(1-z)^n} \\ = \frac{1}{m^n} \sum_{q=0}^{\lfloor (k-n)/m \rfloor} {n\choose q} (-1)^q [z^{k-n-qm}] \frac{1}{(1-z)^n} \\ = \frac{1}{m^n} \sum_{q=0}^{\lfloor (k-n)/m \rfloor} {n\choose q} (-1)^q {k-n-qm+n-1\choose n-1} \\ = \frac{1}{m^n} \sum_{q=0}^{\lfloor (k-n)/m \rfloor} {n\choose q} (-1)^q {k-qm-1\choose n-1}.$$

This is the claim.

  • $\begingroup$ how did you get the first line from the first principles of probability? $\endgroup$ – james black Feb 20 '18 at 23:29
  • $\begingroup$ Every possible combination of values for the RVs appears in the product exactly once (having the same weight) with the coefficient on $[z^k]$ representing values that sum to $k.$ $\endgroup$ – Marko Riedel Feb 20 '18 at 23:41
  • $\begingroup$ im sorry but I dont think i understand very well; can you explain in a little more detail? (is coefficient [z+...+z^m]?) $\endgroup$ – james black Feb 20 '18 at 23:53

This answer is a mere supplement to @MarkoRiedel's answer focusing at commenting the steps due to a request of the OP.

We encode the realisation of the iid random variable $Y_j, 1\leq j\leq n$ with values in $\{1,2,\ldots,m\}$ as \begin{align*} z^1+z^2+\cdots+z^m=z\frac{1-z^m}{1-z}\tag{1} \end{align*}

We need to extract coefficients of series. It is convenient to use the coefficient of operator $[z^k]$ to denote the coefficient of $z^k$ in a series. This way the probability that $Y_j$ is $k$ can be represented according to (1) as \begin{align*} P(Y_j=k)=\frac{1}{m}[z^k]z\frac{1-z^m}{1-z}\qquad\qquad 1\leq j\leq n \end{align*}

We obtain \begin{align*} \color{blue}{P(Y_1}&\color{blue}{+Y_2+\cdots +Y_n=k)}\\ &=\frac{1}{m^n}[z^k]z^n\left(\frac{1-z^m}{1-z}\right)^n\tag{1}\\ &=\frac{1}{m^n}[z^{k-n}]\sum_{j=0}^n\binom{n}{j}(-1)^jz^{mj}\frac{1}{(1-z)^n}\tag{2}\\ &=\frac{1}{m^n}\sum_{j=0}^{\left\lfloor\frac{k-m}{n}\right\rfloor} \binom{n}{j}(-1)^j[z^{k-n-mj}]\frac{1}{(1-z)^n}\tag{3}\\ &=\frac{1}{m^n}\sum_{j=0}^{\left\lfloor\frac{k-m}{n}\right\rfloor} \binom{n}{j}(-1)^j[z^{k-n-mj}]\sum_{l=0}^\infty\binom{-n}{l}(-z)^l\tag{4}\\ &=\frac{1}{m^n}\sum_{j=0}^{\left\lfloor\frac{k-m}{n}\right\rfloor} \binom{n}{j}(-1)^j[z^{k-n-mj}]\sum_{l=0}^\infty\binom{n+l-1}{l}z^l\tag{5}\\ &\,\,\color{blue}{=\frac{1}{m^n}\sum_{j=0}^{\left\lfloor\frac{k-m}{n}\right\rfloor} \binom{n}{j}\binom{k-mj-1}{n-1}(-1)^j}\tag{6}\\ \end{align*} and the claim follows.


  • In (1) we use the representation via power series as $n$-fold product of (1) representing the $n$ iid realisations of the variables $Y_1,Y_2,\ldots,Y_n$.

  • In (2) we apply the rule $[z^{p-q}]A(z)=[z^p]z^qA(z)$ and expand the numerator.

  • In (3) we use the linearity of the coefficient of operator apply again the rule as in (2) and set the upper limit of the series accordingly since the coefficient of $z^{k-n-mj}$ is non-negative.

  • In (4) we use the binomial series expansion.

  • In (5) we use the binomial identity $\binom{-p}{q}=\binom{p+q-1}{p-1}(-1)^q$.

  • In (6) we select the coefficient of $z^{k-n-mj}$ accordingly.

  • $\begingroup$ Very nice. (+1). We'll have to see if this answers concerns of OP. Should the $=k$ be moved into the parenthesis? $\endgroup$ – Marko Riedel Feb 24 '18 at 20:35
  • $\begingroup$ @MarkoRiedel: Thanks Marko. Typo corrected. $\endgroup$ – Markus Scheuer Feb 24 '18 at 20:40

This can be proven by principle of inclusion and exclusion.

Firstly, consider number of solution to $Y_1+Y_2+Y_3+...+Y_n=k$ with no constraint on upper bound, but $Y_i\ge 1$ for all $i=1,2,3,...,n$

Substitute in the variable that $Z_i=Y_i-1$, so now $Z_i\ge 0$

Equation becomes $Z_1+Z_2+...+Z_n=k-n$, number of its non-negative solutions is given by Balls in Urns, which is $ {(k-n)+n-1}\choose{n-1}$= $ {k-1}\choose{n-1}$, this gives the first term in the sum when $i=0$.

Then as we know that each of the random variable have the upper bound of $m$,

Consider the case when (at least) $i$ of the random variables exceed $m$, say $Y_1,Y_2,..,Y_i$. There are ${n}\choose{i}$ ways to choose them.

With substitution that $Z_j=Y_j-(m+1)$ when $j=1,2,...,i$,

$Z_q=Y_q-1$ when $q=(i+1),...,n$

Then $Y_1+Y_2+Y_3+...+Y_n=k \longrightarrow Z_1+Z_2+...+Z_n=k-(m+1)\cdot i -(n-i)=k-mi-n$

Again the number of solutions to this is ${(k-mi-n)+n-1}\choose{n-1}$=${k-mi-1}\choose{n-1}$, this corresponds to the $i$ th term in the sum.

So principle of inclusion & exclusion gives the sum.


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.