The cumulative distribution function is $F_X(x)=\mathbb{P}(X\le x)$. In the absolutely continuous setting of a probability density function, the probability density function is a nonnegative integrable function $f_X$ satisfyingThus $\mathbb{P}(a<X\le b)={\int }_a^b{f}_X(t)dt$ and $F_X^{\prime }=f_X$ almost everywhere. A merely continuous cumulative distribution function need not possess a probability density function; the density assumption means absolute continuity.

The extra ancestor multiplies the probability generating function by $s$. The preceding probability generating function of an independent random sum formula therefore yieldsFor $0\le s<1$ the two roots are $1\pm \sqrt{1-s}$. A probability generating function lies in $[0,1]$ there, so the plus root is impossible. Also $Z\ge 1$ gives $G_Z(0)=0$. Consequently the total progeny with critical geometric offspring hasAt $s=1$ the value is $1$, consistent with almost-sure finiteness. For complex $|s|<1$, the same expression uses the analytic square root that equals $1$ at $s=0$.

For $0\le s\le 1$, condition on $N=k$. Independence of the descendant total progeny variables givesincluding the empty product $1$ when $k=0$. Taking expectation over $N$ proves the probability generating function of an independent random sum formulaThe same identity holds for complex $|s|<1$ by absolute convergence.

The ancestor contributes one individual. Given its offspring count $N$, the descendant family rooted at each child is an independent branching process with the same offspring distribution as the original one. Its total progeny therefore has the same distribution as $Z$. The independent reproduction choices let these descendant total progeny variables be represented by independent copies $Z_1,Z_2,\dots$, independent of $N$. Hence, on this family-tree construction,where the sum is zero when $N=0$.

This is the geometric distribution on $\{0,1,2,\dots \}$ with success parameter $1/2$. Its probability generating function is a geometric series:

For a nonnegative integer-valued random variable, its probability generating function isThe series converges absolutely at least for $|s|\le 1$, with $0^0=1$ in the $k=0$ term; it may converge on a larger domain.

By linearity of expectation, $\mathbb{E}{N}_n=n{p}_n$. The variance of a sum and the negative covariance just proved giveApply Chebyshev's inequality to the empty-box indicators in uniform allocation:This proves the required concentration of the empty-box fraction. Since $p_n\to e^{-1}$, it also yields convergence in probability of $N_n/n$ to $e^{-1}$.

Let $q_n=(1-2/n{)}^n$. The product of two distinct empty-box indicators in uniform allocation is the indicator random variable of both boxes being empty, so $\mathbb{E}(I_i{I}_j)=q_n$. ThusIndeed $0\le 1-2/n<(1-1/n{)}^2$ for $n\ge 2$, and taking the positive integer power $n$ preserves this strict inequality. This proves the negative covariance directly.

Write $p_n=(1-1/n{)}^n$, the probability that all balls avoid a specified box. Each of the empty-box indicators in uniform allocation is an indicator random variable with success probability $p_n$. Since $I_i^2=I_i$, its expectation and variance are

For both boxes to be empty, each ball must avoid two specified boxes. The individual avoidance probability is $(n-2)/n$, and the choices of different balls are independent. ThereforeThis also covers $n=2$, when the answer is zero.

In the uniform balls-in-bins allocation, each ball enters box 1 independently with probability $1/n$. Thus $M_1$ has the binomial distribution $\mathrm{Bin}(n,1/n)$, with probability mass functionand zero outside that range.

For finite second moments, the variance of a sum is

Assume finite second moments and set $Y_i=X_i-\mathbb{E}{X}_i$. By linearity of expectation, centring $X_1+X_2$ gives $Y_1+Y_2$. Expanding its square and using the definitions of variance and covariance,No independence assumption is required for this variance of a sum identity.

Every nonzero integer $a$ has $a^2>0$, proving reflexivity. Because $ab=ba$, the relation is symmetric. If $ab>0$ and $bc>0$, then $ac=(ab)(bc)/b^2>0$, proving transitivity. Thus this is an equivalence relation, whose two equivalence classes are the positive integers and the negative integers:

This binary relation is not an equivalence relation, because it is not symmetric: $(0,0)R(0,1)$ since $0\le 1$, but $(0,1)R(0,0)$ is false. In fact the injective encoding $(a,b)\mapsto 10a+b$ gives a total order. There are no equivalence classes for this binary relation.

Write $q(x,y)=x^2+y^2$. Equality of $q$-values defines an equivalence relation induced by a function: equality is reflexive, symmetric, and transitive, so all three properties hold for $R$. The equivalence class of $(x,y)$ isFor $(x,y)\ne (0,0)$ this is the circle centred at the origin with radius $\sqrt{x^2+y^2}$; the remaining equivalence class is the singleton $\{(0,0)\}$.

A binary relation is an equivalence relation precisely when it is reflexive, symmetric, and transitive.

A binary relation $R$ on $A$ is a transitive relation precisely when $(aRb\text{and}bRc)\Rightarrow aRc$ for all $a,b,c\in A$.

A binary relation $R$ on $A$ is an antisymmetric relation precisely when $(aRb\text{and}bRa)\Rightarrow a=b$ for all $a,b\in A$.

A binary relation $R$ on $A$ is a symmetric relation precisely when $aRb\Rightarrow bRa$ for all $a,b\in A$.