10 12 Probability generating functions Flashcards
Assume X
assume that X is a discrete random variable on the support (state space) of non-negative integers, {0, 1, 2, . . .} (typically representing the number of individuals in a
population)
pgf of X
φ(z) =
E(zˣ) ≡ Σ{k=0,..∞} P {X = k}zᵏ
with |z| ≤ 1
E(zˣ) deontes the mean of random var zˣ
(φₓ(z))
This means that φ(z) is an increasing function when we do not have pk = 0 for all 0 < k < ∞.
pₖ
pₖ
Probability(X = k) ≡ P {X = k} = pₖ
with all 0 ≤ pₖ ≤ 1
Typical graph of pgf φₓ(z) of RV X
φ(z) against z
φₓ(0)= p₀
curve, increases as z increases
φₓ(1)=1
φₓ’(1)=E[X]
values with pgf φₓ(z)
** φₓ(0) = p₀**
** φₓ(1) = 1**
** φₓ’(1) = E[X]**
φₓ(z) =p₀+p₁z+p₂z²+p₃z³+p₄z⁴+….
φ’(z) = p₁+2p₂z+3p₃z²+4p₄z³+….
sum from k=0 to infinity of kp_k
pgf φₓ(z) for variance of RV X
** φₓ’(1) = E[X]**
** φₓ”(1)+φₓ’(1) = E[X²]**
φ’(z) = p₁+2p₂z+3p₃z²+4p₄z³+….
φ”(z) = 2p₂+6p₃z+12p₄z²+….
Var[X]=E[X²] - E[X]²
Var[X] = [ φₓ”(1)+φₓ’(1)] - (φₓ’(1))²
=φₓ”(1) + E[X][1-E[X]]
standard dev sqrt of Var
If X is the number obtained when rolling a dice, pₖ ≡ P {X = k} with k ∈ {1, . . . , 6}
What is φ(z)?
E[X]
Var[X]
pₖ = 1/6 for k=1,2,..6
φ(z) = (1/6)z+(1/6)z² +…+ (1/6)z⁶
check
φ(1)=1
φ’(1)=21/6
φ”(1)=
E[X]=21/6
Var[X]=35/12
s.d= sqrt(35/12)
RVs stochastic process
A stochastic process
{Xₜ: t ∈ T} is a collection of random variables labelled by time t (T can be discrete or continuous). For instance, {X₀, X₁, . . . } may describe the random # individuals in a population over time, and corresponds to the sample path (or stochastic realization) of the process Xₜ at time t = 0, 1, . . . . To characterize the properties
of Xₜ, we thus need a generating function that is a probability generating function of time t
and z.
probability generating function of the stochastic process
function of two variables, z and t
G(z, t) =
Σ_{k=0,..∞} pₖ(t)zᵏ
|z| ≤ 1
absolutely convergent
time dependent
probability generating function of the stochastic process time dependent useful formulae
PARTIAL DERIVATIVES
Partial derivative wrt t and z:
∂G(z, t)/∂t =
Σ_{k=0,..∞} [dpₖ(t)/dt]zᵏ
∂G(z, t)/∂z =
Σ_{k=1,..∞} pₖ(t)zᵏ ⁻¹
useful formulae:
g(z,t) = E(zˣᵗ) ( E( (z^{X_t}))
∂G(z, t)/∂z |z=1
≡ [∂G(1, t)/∂z)
= Σ_{k=1,..∞} kpₖ(t)=E(Xₜ)
why are pgfs useful?
if we can find it,
then all the p_k(t) can be deduced from G(z, t). Typically, G(z, t) is obtained by solving a suitable partial differential equation derived from the properties of G(z, t) and of its derivatives
Important values for stochastic pgf
z=0: only p₀(t) contributes to the pgf G(0,t)= p₀(t) = P(Xₜ=0) there are no individuals at time t (population extinction probability at time t)
z=1 G(1,t)=Σ_{k=0,..∞} pₖ(t = 1 by probability conservation requires finding pop at any of its states at time t =1
(when we set z=1 we set the limit from below z → 1−)
(when we set z=0 we set z → 0+ from above)
MASTER EQUATION
Example. The simple birth process
where each cell gives birth to another cell (cell division) with a rate β. When the population consists of k cells, the probability that a cell division (birth) occurs in a small interval ∆t is βk∆t.
Initially n₀ cells (pₙ₀(0) = 1)
{pₖ(t) = 0 if k < n₀,
{dpₙ₀(t)dt = −βn₀,pₙ₀(t) &
{dpₖ(t)/dt= −kβpₖ(t) + (k−1)βpₖ₋₁(t) if k > n₀,
master equation
master equation” of the stochastic process, and describes via an ODE how the probabilities of the process evolve over time
PGF
Example. The simple birth process
where each cell gives birth to another cell (cell division) with a rate β. When the population consists of k cells, the probability that a cell division (birth) occurs in a small interval ∆t is βk∆t.
G(z,t) =Σ_{k=0,..∞} pₖ(t)zᵏ found from solving below (not covered in this course)
obeys the pde:
∂G(z, t)/∂t = −βz(1 − z) (∂G(z, t)/∂z)
with initial condition
G(z,0)= zⁿ⁰ since pₖ(0)=0 for all k≠n₀
DERIVATION
G(z,t) =Σ_{k=0,..∞} pₖ(t)zᵏ found from solving below (not covered in this course)
obeys the pde:
∂G(z, t)/∂t = −βz(1 − z) (∂G(z, t)/∂z)
with initial condition
G(z,0)= zⁿ⁰ since pₖ(0)=0 for all k≠n₀
G(z,t) =Σ_{k=n₀,..∞} pₖ(t)zᵏ
∂G/∂z =Σ_{k=n₀,..∞} k pₖ(t)zᵏ⁻¹
∂G(z, t)/∂t =(dp_{n₀}(t)/dt)zⁿ⁰ +
Σ_{k=n₀+1,..∞} (dpₖ(t)/dt)zᵏ
substituting master eq
rearranging for two sums we will find,
∂G(z, t)/∂t = β(−z + z²)∂G(z, t)/∂z
= −βz(1 − z)[∂G(z, t)/∂z]
LEVEL 5 The Poisson process
Key features
counts events occurring independently at random times
X_t #events occurred up to time t
events occur with constant rate λ in interval (t, t + ∆t) :
P { no events occur } = 1 − λ∆t
P {one event occurs } = λ∆t
P { more than one event occurs } ∝ (∆t)^2
LEVEL 5 The Poisson process
p_0(t) if X_0=0
p_0(t+ ∆t) = P(X_(t+ ∆t) =0)
p_0(0)=1 (P(X_0=0)=1)
p0(t)(1 − λ∆t) as ∆t → 0.
(no event at time t and no event in interval)
LEVEL 5 The Poisson process
What can we do with:
p_0(t+ ∆t) = P(X_(t+ ∆t) =0)
=
p0(t)(1 − λ∆t) as ∆t → 0.
(no event at time t and no event in interval)
to obtain ODE
rearrange take limit as ∆t → 0.
dp_0(t)/dt= −λp_0(t),
with initial condition p0(0) = 1.
We thus readily integrate and find:
p_0(t) = exp(−λt)
This means that in the Poisson process, the probability that no events occurred by time t
vanishes exponentially in time. Now, what about p_1(t)? We similarly find:
LEVEL 5 The Poisson process
what about p_1(t)?
P(X_t=1)
ODE involving
p_1(t + ∆t) = p_1(t)(1 − λ∆t) + p_0(t)λ∆t
rearranged again to give
dp_1(t)/dt =
−λp_1(t) + λp_0(t)
= −λp_1(t) + λexp(−λt)
, with p1(0) = 0.
p_1(t) = λtexp(−λt)
LEVEL 5 The Poisson process
what about p_n(t)
The logic that we used for p1(t) works for all larger integers, and we get
p_n(t + ∆t) =
p_{n−1}(t)λ∆t + p_n(t)(1 − λ∆t).
This equation can be rearranged to give
dp_n(t)/dt
= −λp_n(t) + λp_{n−1}(t) for n ≥ 1, with p_n(0) = 0
LEVEL 5 The Poisson process
G(z,t)
How is it found?
partial deriv of G wrt t and then substituting the dp_n/dts we found
(using G(z,t) terms and changing limits on series, taking out factors)
Gives**
∂G(z,t)/∂t
= λ(z − 1)G(z, t), with **
G(z, 0) = 1,
gives solution
G(z, t) = exp(λt(z−1))
= exp(−λt) exp(λtz)
LEVEL 5 The Poisson process given
G(z,t)
how do we use to find p_n(t)
e.g.
G(z, t) = exp(λt(z−1))
= exp(−λt) exp(λtz)
expand the generating function as a power
series in z:
G(z, t) = exp(λt(z−1))
= exp(−λt) exp(λtz)
=exp(−λt)[1+ λtz +(1/2)(λt)^2z^2 + · · · +
(λt)^k/k! z^k + · · ·]
We then compare coeffs of z^k
Thus p_k(t) = (λt)^k/k! *exp(−λt)
LEVEL 5 The Poisson process
given G(z,t)
how do we use to find E(X_t) and Var(X_t)
e.g
G(z, t) = exp(λt(z−1))
= exp(−λt) exp(λtz)
∂G(z, t)/∂z at z=1
and second partial deriv
E(X_t)=λt.
var(Xt) ≡ (λt)^2 + λt − (λt)^2 = λt.
same values for Poisson
The probability generating function of sums of independent random variables
Branching processes that we have seen involve the sum of independent and identically distributed (iid) random variables, see e.g. (11.1). In this context, we are interesting in finding
the generating function of a sum of random variables
probability that two random
events occur together, say A and B, then
P {A and B}
P {A and B} = P(A ∩ B) = P(A|B)P(B),
where P(A|B) = P {A given B} is the conditional probability of A given B
if random events are independent:
P(A|B) = P(A).
if X and Y are independent,
P {X = x and Y = y}
= P(X = x ∩ Y = y) = P(X = x)P(Y = y)
Can be generalized to continuous random variables and to an arbitrary sum of random
variables.
probability that a number of random independent events occur = the product of the probability of each individual event
Independent events example
We toss a fair coin and roll a fair dice. Let X be 1 if the coin shows “head” and 0 if it shows tail, and let Y be the result obtained by rolling the dice. Since, tossing the coin
and rolling the dice are independent processes, the probability of obtaining “head” and a 6 is
P {X = 1 and Y = 6} = P(X = 1 ∩ Y = 6) = P(X = 1)P(Y = 6) = 1/2·1/6=1/12
where P(X = 1) = 1/2 since the coin is fair and P(Y = 6) = 1/6 as there is a chance 1/6 that the dice shows any of its six faces
We assume that X₁ and X₂ are independent random variables with same distribution as X.
pgf of X₁ and X₂
pgf of X₁ + X₂
1)the same as X
2)S= X₁ + X₂ pgf is
φₛ(z) = E(zˢ) = E(zˣ¹⁺ˣ²)
= Σ_k P(X₁ + X₂ = k)zᵏ
( where k= ℓ+m)
=Σ_ℓ P(X₁ = ℓ )zˡ Σₘ P(X₂ = m )zᵐ
= E(zˣ¹)E(zˣ²) =(E(zˣ))²= (φX(z))²
pgf of S is product of φₓ₁(z) * φₓ₂(z).
valid for sum of n indep RVs
Sₙ= X₁+X₂+X₃+… Xₙ
where all Xᵢ i=1,..n are independent and same probability distribution and pgf φₓ(z) = E(zˣ)
pgf of Sₙ
φ_Sₙ(z) = E(Z^(Sₙ))
= E(zˣ¹⁺ˣ²⁺…⁺ˣⁿ) =
E(zˣ¹)E(zˣ²)…E(zˣⁿ)
= (E(zˣ))ⁿ
= (φₓ(z))ⁿ
Example. We toss independently two coins and count the number of “heads” S =
X1 + X2 shown by the two coins, where X1 = 1 if the first coin shows “head” and
X1 = 0 otherwise. Similarly, X2 = 1 if the second coin shows “head” and X2 = 0
otherwise. Assuming fair coins, X1 and X2 are independent
pgf of sum of heads
φₓ(z) = 0.5 + 0.5z
compute individually or product of this
Sn is the number of heads obtained when tossing n coins then
φ_Sₙ(z) =
(1/2 + (1/2)z) ⁿ
pgf of RANDOM SUMS of independent vars: if n is random too
Xᵢ independent RVs all same pgf and n random
Sₙ = Σ_{i=1,..n} Xᵢ
φ_Sₙ(z) = E(Z^(Sₙ))
= Σ_k P(n=k)E(z^Sₙ| n=k)
= Σₖ P(n=k)(φₓ(z))ᵏ
=φₙ(φₓ(z))
where pgf of sum of k indep RVs X_i:
φₙ(y) = Σₖ P(n=k)yᵏ with y=φₓ(z)
Example. Suppose I have a fair coin and a fair dice. I roll the dice, then toss the coin the same number of times as the number on the dice. What is the pgf of the #heads? This is random # 0-6. What is the probability to draw six, three and five heads?
P(Z=3) = 1/6
P(Z=5)=1/48
P(Z=6)=1/384
Let X be #heads from tossing a coin
Y result on die
φₓ(z)=0.5(1+z)
φᵧ(z)=(1/6)(z+z²+z³+z⁴+z⁵+z⁶)
φ_Z(z)=φᵧ(φₓ(z)) = φᵧ( 0.5(1+z))
which we would sub in to find pgf and coeffs of z^3,z^5 z^6 etc
