独立同分布均匀随机变量和的概率公式证明：结合广义二项式定理

Alright, let's walk through how to prove this probability identity using the generalized binomial formula. I'll break it down into manageable steps, starting from the basics so it's easy to follow.

First, let's restate the problem clearly: we have $n$ independent, identically distributed (i.i.d.) random variables $Y_1, Y_2, ..., Y_n$, each uniformly distributed over the set ${1, 2, ..., m}$. We need to show that for $n \le k \le mn$,
$$P(Y_1 + Y_2 + ... + 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}$$

Step 1: Turn It Into a Counting Problem #

Probability here is just the number of valid sample points (where the sum equals $k$) divided by the total number of possible sample points ($m^n$). So our core task is to count how many positive integer solutions exist to the equation:
$$Y_1 + Y_2 + ... + Y_n = k$$
with each $1 \le Y_i \le m$.

Let's make a substitution to simplify this: let $X_i = Y_i - 1$. Now each $X_i \ge 0$, and the equation becomes:
$$X_1 + X_2 + ... + X_n = k - n$$
with the constraint $X_i \le m-1$ (since $Y_i \le m$). Now we just need to count the number of non-negative integer solutions to this new equation that satisfy the upper bounds.

Step 2: Use Inclusion-Exclusion Principle #

First, without any upper bounds, the number of non-negative solutions to $X_1 + ... + X_n = k-n$ is given by the stars-and-bars theorem: $\binom{(k-n) + n - 1}{n-1} = \binom{k-1}{n-1}$.

But we need to exclude solutions where one or more $X_i \ge m$. This is where inclusion-exclusion comes in:

• Pick $i$ variables to "violate" the upper bound (i.e., $X_j \ge m$). For each such variable, let $X_j' = X_j - m$, so $X_j' \ge 0$. The equation now becomes $X_1' + ... + X_n' = k - n - i \cdot m$.
• If $k - n - i \cdot m \ge 0$, the number of solutions here is $\binom{(k-n - i\cdot m) + n -1}{n-1} = \binom{k - mi -1}{n-1}$. If the right-hand side is negative, there are 0 solutions.

Applying inclusion-exclusion, the total number of valid solutions is:
$$\sum_{i=0}^{\lfloor (k-n)/m \rfloor} (-1)^i \binom{n}{i} \binom{k - mi -1}{n-1}$$

Step 3: Bring In the Generalized Binomial Formula #

Now let's connect this to the generalized binomial formula by using generating functions—this is where the formula you mentioned becomes essential.

Each $Y_i$ has a generating function:
$$G_Y(x) = x + x^2 + ... + x^m = x \cdot \frac{1 - x^m}{1 - x}$$
For $n$ independent variables, the generating function for their sum is $[G_Y(x)]^n = x^n \left( \frac{1 - x^m}{1 - x} \right)^n$.

We need the coefficient of $x^k$ in this generating function, which is the same as the coefficient of $x^{k-n}$ in $\left( \frac{1 - x^m}{1 - x} \right)^n$. Let's split this into two parts:

1. Expand $(1 - x^m)n$ using the standard binomial theorem:
   $$(1 - x^m)n = \sum_{i=0}^n (-1)^i \binom{n}{i} x^{mi}$$
2. Expand $(1 - x)^{-n}$ using the generalized binomial formula (where $|x| < 1$):
   $$(1 - x)^{-n} = \sum_{t=0}^{\infty} \binom{-n}{t} (-x)^t$$
   Remember that for negative integers, the generalized binomial coefficient $\binom{-n}{t} = (-1)^t \binom{n + t - 1}{t}$, so this simplifies to:
   $$(1 - x)^{-n} = \sum_{t=0}^{\infty} \binom{n + t - 1}{t} x^t$$

Now multiply these two series together. The coefficient of $x^{k-n}$ comes from terms where $mi + t = k - n$, so $t = k - n - mi$. Substituting this into the product, we get:
$$\sum_{i: mi \le k-n} (-1)^i \binom{n}{i} \binom{n + (k-n - mi) - 1}{k-n - mi}$$
Using the symmetry of binomial coefficients ($\binom{a}{b} = \binom{a}{a-b}$), this becomes:
$$\sum_{i=0}^{\lfloor (k-n)/m \rfloor} (-1)^i \binom{n}{i} \binom{k - mi -1}{n-1}$$

This is exactly the count we got from inclusion-exclusion! Divide by $m^n$ (the total number of sample points) and we arrive at the desired probability formula.

Wrap-Up #

The key here was using generating functions to bridge the counting problem to the generalized binomial formula. The formula let us handle the $(1-x)^{-n}$ term, which is crucial for expanding the generating function into a form we can work with. Combine that with inclusion-exclusion, and we get the identity we needed to prove.

内容的提问来源于stack exchange，提问作者james black