6.041

Seven Axioms of the Algebra of Events A+B = B +A; A+(B +C) = (A+B)+C; A(B +C) = AB +AC; (A′)′ == A; (AB)′ = A′ + B′; AA′ = ϕ; AU = A.

Three Axioms of Probability Measure (1) For any event A, P (A) ≥ 0; (2) P (U) = 1; (3) If AB = ϕ, then P (A + B) = P (A) + P (B).

Conditional Probability P (A | B) = \frac{P (AB)}{P (B)} defined only for P (B) ≠ 0; P (AB) = P (A)P (B | A) = P (B)P (A | B). For random variables, p_{x,y}(x_{0}, y_{0}) = p_{x}(x_{0})p_{y|x}(y_{0} | x_{0}) = p_{y}(y_{0})p_{x|y}(x_{0} | y_{0}).

Independence Two events are Independent if and only if P (A | B) = P (A). For random variables x and y, they are independent if and only if p_{y|x}(y_{0} | x_{0}) = p_{y}(y_{0}) for all possible values of x_{0} and y_{0}. If two random variables x and y are independent, E(xy) = E(x)E(y). Two random variables x and y are linearly independent (but not necessarilly independent) if E(xy) = E(x)E(y). Two PDF’s are (statistically) independent if and only if f_{x|y}(x_{0} | y_{0}) = f_{x}(x_{0}) for all possible x_{0}, y_{0}.

Bayes’ Theorem P (A_{i} | B) = \frac{P (A_{i})P (B|A_{i})}{Σ_{i=1}^{N}P (A_{i})P (B|A_{i})} with P (B) ≠ 0 and A_{1}, A_{2},…, A_{N} an event space.

Expected Value E[g(x)] ≡ ∑_{x_{0}} g(x_{0})p_{x}(x_{0}) ≡ \overline{g(x)}

Moments First: E(x) = ∑_{x_{0}} x_{0}p_{x}(x_{0}); n^{th}: \overline{x^{n}} = E(x^{n}) = ∑_{x_{0}} x_{0}^{n}p_{x}(x_{0}).

Central Moments Second (variance): σ_{x}^{2} = E{[x−E(x)]^{2}} = E(x^{2})−[E(x)]^{2} (σ_{x} is standard deviation); n^{th}: E{[x−E(x)]^{n}} = ∑_{x_{0}}[x_{0} − E(x)]^{n}p_{x}(x_{0}) = \overline{(x − \overline{x})^{n}}. (c is a constant) σ_{c}^{2} = 0; σ_{cx}^{2} = c^{2}σ_{x}^{2}; if x and y are independent, σ_{x+y}^{2} = σ_{x}^{2} + σ_{y}^{2}.

PDF Prob(a < x ≤ b) = ∫_{a}^{b} f_{x}(x_{0})dx_{0}. Prob(x_{0} < x ≤ x_{0} + dx_{0}) = f_{x}(x_{0}).

CDF F_{x}(x_{0}) = p_{x≤x_{0}}(x_{0}) = Prob(x ≤ x_{0}) = ∫_{−∞}^{x_{0}} f_{x}(x_{0})dx_{0}. f_{x}(x_{0}) = \frac{dF_{x}(x_{0})}{dx_{0}} . Prob(a < x ≤ b) = F_{x}(b) − F_{x}(a).

Conditional PDF f_{x,y|A}(x_{0}, y_{0} | A) = \frac{f_{x,y}(x_{0},y_{0})·(x_{0},y_{0}∈A)}{P (A)} .

Derived PDF’s ����� ����� Determine probability of event g ≤ g_{0} for all values of g_{0}. ������ ����� Differentiate this quantity with respect to g_{0} to obtain f_{g}(g_{0}).

S Transform f_{x}^{T} (s) ≡ E(e^{−sx}) = ∫_{−∞}^{∞} e−sxf_{x}(x_{0})dx_{0}; \frac{d^{n}f_{x}^{T} (s)}{ds^{n}} = ∫_{x_{0}=−∞}^{∞}(−x_{0})^{n}e^{−sx_{0}}f_{x}(x_{0})dx_{0}

[f_{x}^{T} (s)]_{s=0} = 1  E(x) = −[ \frac{df_{x}^{T} (s)}{ds}]_{s=0}  E(x^{2}) = [ \frac{d^{2}f_{x}^{T} (s)}{ds^{2}} ]_{s=0}

σ_{x}^{2} = E(x^{2}) − [E(x)]^{2} = \{ \frac{d^{2}f_{x}^{T} (s)}{ds^{2}} − [ \frac{df_{x}^{T} (s)]^{2}}{ds} \}_{s=0}

Z Transform p_{x}^{T} (z) ≡ E(z^{x}) = Σ_{x_{0}=0}^{∞}z^{x_{0}}p_{x}(x_{0})

\frac{d^{n}p_{x}^{T} (z)}{dz^{n}} = Σ_{x_{0}=0}^{∞}x_{0}(x_{0} − 1)(x_{0} − 2) ⋯ (x_{0} − n + 1)z^{x_{0}−n}p_{x}(x_{0})

[p_{x}^{T} (z)]_{z=1} = 1  E(x) = [ \frac{dp_{x}^{T} (z)}{dz}]_{z=1}  E(x^{2}) = [ \frac{d^{2}p_{x}^{T} (z)}{dz^{2}} + \frac{dp_{x}^{T} (z)}{dz}]_{z=1}

σ_{x}^{2} = [[ \frac{d^{2}p_{x}^{T} (z)}{dz^{2}} + \frac{dp_{x}^{T} (z)}{dz}]_{z=1} − [ \frac{dp_{x}^{T} (z)}{dz}]^{2}]_{z=1}

Sum of Random variables (w = x + y, x, y independent) f_{x}(w_{0}) = ∫_{x_{0}=−∞}^{∞} dx_{0}f_{x}(x_{0})f_{y}(w_{0} − x_{0}). Equivalently, in transform world: f_{x}^{T} (s) = f_{x}^{T} (s)f_{y}^{T} (s) and p_{x}^{T} (z) = p_{x}^{T} (z)p_{y}^{T} (z) . For any random variables x and y, E(x + y) = E(x) + E(y). σ_{w}^{2} = σ_{x}^{2} + σ_{y}^{2} if x, y are linearly independent.

Random number of iid random variables (r = x_{0} + x_{+} ⋯ x_{n})

f_{r}^{T} (s) = p_{n}^{T} [f_{x}^{T} (s)].  E(r) = E(n)E(r).  σ_{r}^{2} = E(n)σ_{x}^{2} + [E(x)]^{2}σ_{n}^{2}.
Infinite Sums Σ_{x=0}^{∞}a^{k−1}k = \frac{1}{(1−a)^{2}}  ∑_{k=1}^{∞} \frac{(−1)^{k+1}x^{k}}{k} = ln(1 + x)  n! = \sqrt{2π}e^{−n}n^{(n+0.5)}

Bernoulli Trial:

p_{x}(x_{0}) = \{ \begin{matrix}1 − P & x_{0} = 0(a “failure”) \\ P & x_{0} = 1(a “success”) \end{matrix}

p_{x}^{T} (z) = 1 − P + zP  E(x) = P  σ_{x}^{2} = P (1 − P)

Process: k is sum of n independent Bernoulli random variables. (Binomial)

p_{k}(k_{0}) = ( \begin{matrix}n \\ k_{0} \end{matrix} ) P^{k_{0}}(1 − P)^{n−k_{0}} k_{0} = 1, 2,…, n

p_{k}^{T} (z) = (1 − P + zP)^{n}  E(k) = nP  σ_{k}^{2} = nP (1 − P)

Interarrival Times: (Geometric, Pascal)

P_{l_{1}}(l) = P (1 − P)^{l−1}  l = 1, 2,…  p_{l_{1}}^{T}(z) = \frac{zP}{1−z(1−P)}  E(l_{1}) = \frac{1}{P}  σ_{l_{1}}^{2} = \frac{1−P}{P^{2}}

P_{l_{r}} (l) = ( \begin{matrix}l − 1 \\ r − 1 \end{matrix} ) P^{r}(1 − P)^{l−r} l = r, r + 1, r + 2,…; r = 1, 2,…

p_{l_{r}}^{T} (z) = [ \frac{zP}{1−z(1−P)} ]^{r}  E(l_{r}) = \frac{r}{P}  σ_{l_{r}}^{2} = \frac{r(1−P)}{P^{2}}

Poisson Process First-order interarrival times are independent identically distributed exponential random variables. k is the number of arrivals in an interval of duration t.

p_{k}(k_{0}) = \frac{(λt)^{k_{0}} e^{−λt}}{k_{0}!}  t ≥ 0; k_{0} = 0, 1, 2,…  p_{k}^{T} (z) = e^{λt(z−1)}  E(k) = λt  σ_{k}^{2} = λt

Interarrival Times: (Erlang)

f_{l_{1}}(l) = λe^{−λl}  l ≥ 0  f_{l_{1}}^{T}(s) = \frac{λ}{λ+s}  E(l_{1}) = \frac{1}{λ}  σ_{l_{1}}^{2} = \frac{1}{λ^{2}}
f_{l_{r}} (l) = \frac{λ^{r}l^{r−1}e^{−λl}}{(r−1)!}  l ≥ 0; r = 1, 2,…  f_{l_{r}}^{T} (s) = ( \frac{λ}{λ+s})^{r}  E(l_{r}) = \frac{r}{λ}  σ_{l_{r}}^{2} = \frac{r}{λ^{2}}

Combined Poisson Processes λ_{a} and λ_{b} are average interarrival time for two independent, simultaneous poisson processes. Prob(next event type A) = \frac{λ_{a}}{λ_{a}+λ_{b}} N is total number of events while waiting for R events of type A.

P_{N}(N_{0}) = ( \begin{matrix}N_{0} − 1 \\ R − 1 \end{matrix} ) (\frac{λ_{a}}{λ_{a}+λ_{b}} )^{R} (\frac{λ_{b}}{λ_{a}+λ_{b}} )^{N_{0}−R}; N_{0} = R, R + 1,…; R = 1, 2, 3,…

Renewal Process First-order interarrival times are mutually independent and described by the same PDF.

Random Incidence x 1st order interarrival time; y remaining gap length; w incident gap length:

p_{w}(w_{0}) = \frac{w_{0}p_{x}(w_{0})}{E(x)}  f_{w}(w_{0}) = \frac{w_{0}f_{x}(w_{0})}{E(x)}  f_{y|w}(y_{0} | w_{0}) = \frac{1}{w_{0}}  0 ≤ y_{0} ≤ w_{0}  E(w) = \frac{E(x^{2})}{x}
f_{y,w}(y_{0}, w_{0}) = \frac{f_{x}(w_{0})}{E(x)}  0 ≤ y_{0} ≤ w_{0} ≤ ∞  f_{y}(y_{0}) = ∫_{y_{0}}^{∞} \frac{f_{x}(w_{0})dw_{0}}{E(x)} = \frac{1−F_{x}(y_{0})}{E(x)}  E(y) = \frac{E(x)}{2}

Linear Algebra Eigenvalues: det(A − λI) = 0; Eigenvectors: all x⃗ satisfying (A − λI)x⃗ = 0; For Markov Matrix probabilities to converge, it must be neutral stable. Neutral stable: for all eigenvalues, λ, λ ≤ 1, and for one eigenvalue, λ = 1. For Markov Matrix, set up probability matrix so columns sum to 1 (as opposed to rows as done in text/class – take the transpose of the matrix if it comes from class/text). Then as n → ∞ for A^{n}, p_{j,1} … p_{j,m} all converge to P_{j}. Alternately, solve for the eigenvector for λ = 1 and normalize so the values sum to 1 and you get the corresponding probability vector P⃗.

Book Markov Ergodic Theorem says should be recurrent, nonperiodic, and finite number of states. Limiting state probabilities: P_{j} = ∑_{i=1}^{m}(P_{i})(p_{ij});∑_{i=1}^{m} P_{i} = 1. Birth and Death Processes P_{i+1} = (\frac{b_{i}}{d_{i+1}} ) P_{i}. Then normalize so probabilities sum to one.

Chebyshev Inequality Prob [|x − E(x)| ≥ t] ≤ (\frac{σ_{x}}{t} )^{2}

Stochastic Convergence Sequence {y_{n}} = y_{1}, y_{2},…, is stochastically convergent to C if, for every ϵ > 0, lim_{n→∞} Prob (|y_{n} − C| > ϵ) = 0.

Weak Law for Large Numbers

lim_{n→∞} Prob [|\frac{1}{n} ∑_{i=1}^{n} y_{i} − E(y)| ≥ ϵ] = 0  (1)

Gausian f_{x}(x_{0}) = \frac{1}{\sqrt{2π}σ_{x}} e^{−[x_{0}−E(x)]^{2}/2σ_{x}^{2}}  −∞ ≤ x_{0} ≤ ∞  f_{x}^{T} (s) = e^{(s^{2}σ_{x}^{2}/2)−sE(x)}.

PDf for sum of independent Gaussians random variables is a Gaussian PDF.

Unit Gausian f_{y}(y_{0}) = \frac{1}{\sqrt{2π}} e^{−y_{0}^{2}/2}  −∞ ≤ x_{0} ≤ ∞,  E(y) = 0,  σ_{y} = 1.

Normalize arbitrary Gaussian: y = \frac{x−E(x)}{σ_{x}}. CDF for unit Gaussian: Φ(y_{0}) ≡ F_{y}(y_{0}). CDF for arbitrary Gaussian: F_{x}(x_{0}) = Φ [\frac{x_{0}−E(x)}{σ_{x}}]. Φ(−y_{0}) = 1 − Φ(y_{0}).

Centeral Limit Theorem As n → ∞, the CDF of any sum of random variables approaches that of a Gaussian.

lim_{n→∞} F_{r}(r_{0}) = Φ [\frac{r_{0}−E(r)}{σ_{r}}]  E(r) = nE(x)  σ_{r} = \sqrt{n}σ_{x}

Binomial PMF When using the Central Limit Theorem to approximate the binomial PMF (P close to 0.5):

Prob(a ≤ k ≤ b) ≈ Φ [\frac{b+ \frac{1}{2} −nP}{\sqrt{nP (1−P)}}] − Φ [\frac{a− \frac{1}{2} −nP}{\sqrt{nP (1−P)}}]

For P or (1-P) small and n large, use Poisson approximation: lim_{n→∞} p_{k}(k_{0}) = \frac{(nP)^{k_{0}} e^{−(nP)}}{k_{0}!}

Significance Tests Let α be level of significance. Select “unlikely” range for variable. Select unlikely range such that: Prob(value in unlikely range) = α. Run test/experiment. If value in unlikely range, reject; otherwise, accept.

Hypothesis Testing α = probability of false rejection of H_{0} given H_{0} is true; β = condictional probability of false accpetance of H_{0} given H_{0} is false (i.e. H_{1} is true). [n.b. if H_{0} centered to left, β is left tail of H_{1}.]

Cost Analysis E(cost) = Cost(false acceptance of H_{0})(1 − P (H_{0}))β + Cost(false rejection of H_{0})P (H_{0})α+ Cost(valid acceptance ofH_{0})P (H_{0})(1 − α) + Cost(valid rejection of H_{0})(1 − P (H_{0}))(1 − β).

Estimators Q sequence is consistent if: lim_{n→∞} Prob (|Q_{n} − Q| > ϵ) = 0 for any ϵ > 0. Q_{n} is an unbiased estimator of Q if: E(Q_{n}) = Q for n = 1,2,… Q_{n} is an asymptotically unbiased estimator of Q if: lim_{n→∞} E(Q_{n}) = Q

Maximal Likelihood Estimator Express a priori probability of obtaining Experimental result as a function of the parameter of interest. Q^{∗} is the parameter Q which maximizes this a priori probability (i.e. differentiate the probability expression with respects to Q, solve for 0 of the derivative to maximize expression, will get expression for Q^{∗} in terms of the experimental results).