Generating function for sum of i.i.d. random variables

Question

This question is related to probelm 10.(f) of the book Generatingfunctionology (available from the author here: https://www2.math.upenn.edu/~wilf/DownldGF.html), but generic enough to be asked independently (I believe).

The question asks:

A loaded die has probabilities $.1, .2, .1, .2, .2, .2$ of turning up with, respectively, 1, 2, 3, 4, 5, or 6 spots showing. The die is then thrown 100 times, and we want to calculate the probability $p^∗$ that the total number of spots on all 100 throws is $\leq 300$. Identify $p^∗$ as the coefficient of $x^{300}$ in the power series expansion of a certain function. Say exactly what the function is (you are not being asked to calculate $p^∗$).

First, I defined $G(x) = \sum_{i=1}^6 p_i x^i$, with $p_i$ the probability of sampling $i$ spots. And from the previous exercise (10.c) I already know that $[x^n]G(x)^{100}$ is the probability that the sum of all dice throws equals $n$. Then, I want to find $F(x)$ as a power series with coeficients representing the probability of the spots summing $\leq n$. Which I try to do as follows (let $X$ be the R.V. of the loaded die): $$ f(n) = \Pr\left[\sum_{i=1}^{100} X \leq n\right] = \sum_{j=1}^n \Pr\left[\sum_{i=1}^{100} X = n\right] = \sum_{j=1}^n [x^j]G(x)^{100} $$ Now, I believe my function $F(y)$ should be $$F(y) = \sum_{n} f(n) y^n = \sum_{n}\left(\sum_{j=1}^n [x^j]G(x)^{100}\right) y^n $$ and $[y^{300}]F(y)$ should give the probability of the sum of the $100$ dice are $\leq 300$.

Still, in the book, the solution states that I should arrive at $[x^n]\frac{G(x)^{100}}{1-x}$, which I can only compute by taking the $f(n)$ out of the summation, as $$F(y) = \sum_{n} f(n) y^n = f(n) \sum_{n} y^n = \frac{f(n)}{1-y}.$$ But I don't understand how can this be, as $f(n)$ depends on the variable of the summation (I'm summing multiple $f(n)$, each representing the probaility of getting exactly $n$ spots, from $1$ up to $n$ go get all possibilities $\leq n$). I appreciate anyone that could provide some clarification to where my reasoning fails.

Answer 1

We already know that the generating $G(x)^{100}$ represents the situation after $100$ rolls of the loaded die. Let's assume this generating function has the following expansion \begin{align*} G(x)^{100}=\sum_{k=0}^{\infty}a_kx^k\tag{1} \end{align*} where $a_k$ represents the probability of getting $k$ points after $100$ rolls.

We are looking for a generating function $H(x)$ with \begin{align*} \color{blue}{[x^{300}]H(x)=\sum_{k=0}^{300}a_k} \end{align*}

A useful aspect is to recall that multiplication of a generating function $\sum_{k=0}^{\infty}a_kx^k$ with $\frac{1}{1-x}$ adds up the coefficients $a_k$. We have according to (1) using the geometric series expansion \begin{align*} \color{blue}{\frac{1}{1-x}G(x)^{100}}&=\left(\sum_{j=0}^{\infty}x^j\right)\left(\sum_{k=0}^{\infty}a_kx^k\right)\\ &=\sum_{n=0}^{\infty}\left(\sum_{{k+j=n}\atop{k,j\geq 0}}a_k\right)x^n\tag{2.1}\\ &\,\,\color{blue}{=\sum_{n=0}^{\infty}\left(\sum_{k=0}^na_k\right)x^n}\tag{2.2} \end{align*}

We conclude a wanted generating function is $\frac{1}{1-x}G(x)^{100}$ and the solution is according to (2.2): \begin{align*} \color{blue}{[x^{300}]\frac{1}{1-x}G(x)^{100}=\sum_{k=0}^{300}a_k} \end{align*}

Comment:

• In (2.1) we multiply out using the Cauchy product

• In (2.2) we eliminate $j$ by respecting $j=n-k$.