信息安全原理与数学基础(四)

基本信息

授课教师：qz

Lecture 10 概率论

实质内容可以不听回头自己看
有手有脑得个八九十分不是问题
来听就一定能听懂；不来听也能懂
作业 = 没有意义的东西

研究随机事件发生的可能性的应用数学

集合论 Set Theory

• 并集 Union $\cup$
• 交集 Intersection $\cap$
• 补集 Complement $A^{C}$
• 互斥 mutually Exclusive
• 穷尽 Collectively Exhaustive
• 分割 Partition

 

Applying Set Theory to Probability

• 随机实验 Random Experience
• 样本空间 Sample Space
• 事件 Events

 

Probability Axioms

• A1: $P[A]\ge0$
• A2: $P[S]=1$
• A3: mutually exclusive events $P[A_1\cup A_2\cup…]=P[A_1]+P[A_2]+…$
• $P[A\cup B]=P[A]+P[B]-P[A\cap B]$

 

Discrete Sample Space

$S=\lbrace{a_1,a_2,…a_n}\rbrace$

$P[\lbrace a_i\rbrace]=1/n$

 

Conditonal Probability

Defination

$P[A|B]=P[AB]/P[B]$

 

Theorem

• $P[A|B]>0$
• $P[B|B]=1$
• If $A_i$ is the partition of A, then $P[A|B]=P[A_1|B]+P[A_2|B]+…$

 

Partitions & the Law of Total Probability

If the partition is $B = \{B_1,B_2,…,B_n\}$, and $C_i=A\cap B_i$, then $A=C_1\cup C_2\cup …\cup C_n$

Bayel’s Law

$P[B|A]=\displaystyle\frac{P[A|B]P[B]}{P[A]}$

 

Independence

A and B are independent if only if $P(A\cap B)=P(A)P(B)\iff P(A|B)=P(A),P(B|A)=P(B)$

Independence & Mutually Exclusive

independence ans mutually exclusive are not synonyms

only when $P(A)P(B) = 0$, Ind = M.E.

 

Random Variables

$X\in S$

$S_X$: random variable range

map the sample outcomes $s$ to the corresponding value of the random variable $X$

 

Discrete Random Variables

Probablity Mass Function

Defination: $P_X(x)= P[X=x]$

 

Classical Distribution

Name	Meaning	PMF	Expected Value	Variance
Bernoulli(p)	one test, result is 0, or 1	$\begin{cases}1-p&,x=0\\p&,x=1\end{cases}$	$p$	$p(1-p)$
Geometric(p)	the number of tests that result occurs 1 time	$p(1-p)^{x-1},x=1,2,...$	$\displaystyle\frac{1}{p}$	$\displaystyle\frac{1-p}{p^2}$
Binomial(p)	the number of result occurs in n times of tests	$\dbinom{k}{n}p^k(1-p)^{n-k},k=0,1,2,...$	$np$	$np(1-p)$
Pascal(k, p)	the number of tests when the result occurs $k$ times	$\displaystyle\binom{x-1}{k-1}p^k(1-p)^{x-k}$	$\displaystyle\frac{k}{p}$	$\displaystyle\frac{k(1-p)}{p^2}$
Discrete Uniform(k, l)	in range $[k,l+1)$, all events have equal probability	$\displaystyle\frac{1}{(l+1)-k}$	$\displaystyle\frac{(l+1)+k-1}{2}$	$\displaystyle\frac{((l+1)-k-1)((l+1)-k+1)}{12}$
Poisson(a)	the number of events occuring in a fixed interval of time if each occurs with a known average rate $a$ and independently	$\displaystyle\frac{a^xe^{-a}}{x!}$	$a$	$a$

Expected Value: $E[X]=\mu_X=\displaystyle\sum_{x\in S_X} xP_X(x)$
Variance Value: $Var[X]=E[(X-\mu_X)^2]=E(X^2)-\mu_X^2$
Standard Deviation: $\sigma_X=\sqrt{Var[X]}$

Cumulative Distribution Function (CDF)

Defination: $F_X(x)=P[X\le x]=\displaystyle\sum_{x_i\le x} P[X=x_i]$

Derived Random Variable

$Y=g(x),E[Y]=\displaystyle\sum_{x\in S_X} g(x)P_X(x)$

• $E[aX+b]=aE[X]+b$
• $Var[aX+b]=a^2Var[X]$

Continuous Random Variables

CDF: $F_X(x)=P[X\le x]$

• $P[x_1\le X\le x_2]=\displaystyle\int_{x_1}^{x_2}f_X(x)\mathrm{d}x=F_X(x_2)-F_X(x_1)$

PDF: $f_X(x)=\displaystyle\frac{\mathrm{d}F_X(x)}{\mathrm{d}x}$

• $\displaystyle\int_{-\infty}^{+\infty}f_X(x)\mathrm{d}x=1$

Uniform Random Variables

X is a uniform (a, b), PDF: $f_X(x)=\displaystyle\frac{1}{b-a}$

CDF: $F_X(x)=(x-a)/(b-x),x\in(a,b)$

$E[X]=(a+b)/2$

$Var[X]=(b-a)^2/12$

Gaussian / Normal Random Variables

X is a Gaussian, PDF: $f_X(x)=\displaystyle\frac{1}{\sqrt{2\pi\sigma^2}}e^{-\frac{(x-\mu)^2}{2\sigma^2}}$

CDF: $F_X(x)=\Phi(\displaystyle\frac{x-\mu}{\sigma})$

Deifine: $\Phi(x)=\displaystyle\frac{1}{\sqrt{2\pi}}\int_{-\infty}^xe^{-\frac{t^2}{2}}\mathrm{d}t$

$E[X]=\mu$

$Var[X]=\sigma^2$

Standard Normal Random Variables

Gaussian Random Variables when $\mu=0,\sigma=1$

X is a Standard Normal, PDF: $f_X(x)=\displaystyle\frac{1}{\sqrt{2\pi}}e^{-\frac{x^2}{2}}$

CDF: $F_X(x)=\Phi(x)=\displaystyle\frac{1}{\sqrt{2\pi}}\int_{-\infty}^xe^{-\frac{t^2}{2}}\mathrm{d}t$

$E[X]=0$

$Var[X]=1$

In Gaussian($\mu$, $\sigma$), test $x=x_0$, in Standard Normal, $x^\prime=(x_0-\mu)/\sigma$

• $\Phi(z)+\Phi(-z)=1$

Binary Random Variables

Joint Probability Mass Function(PMF)

$P_{X,Y}(x,y)=P[X=x,Y=y]$

use table to present P(x, y)

Joint CDF

$F_{X,Y}(x,y)=P[X\le x,Y\le y]$

Joint PDF

$f_{X,Y}(x,y)=\displaystyle\frac{\partial^2F_{X,Y}(x,y)}{\partial x\partial y}$

Marginal PMF

$P_X(x)=\displaystyle\sum_{y\in S_Y}P_{X,Y}(x,y)$

$P_Y(y)=\displaystyle\sum_{x\in S_X}P_{X,Y}(x,y)$

Marginal PDF

$f_X(x)=\displaystyle\int_{-\infty}^{\infty}F_{X,Y}(x,y)\mathrm{d}y$

Covariance

$Cov[X,Y]=E[(X-\mu_X)(Y-\mu_Y)]$

• $Cov[X,Y]=E[X\cdot Y]-\mu_x\mu_y$

If 2 variables tend to show

• similar behaviour, cov is positive
• opposite behaviour, cov is negative
• uncorrelated behaviour, cov is zero

Correlation

$r_{X,Y}=E[X\cdot Y]$

A normalization of correlation: $\rho_{X,Y}\in[-1,1]$

$\rho_{X,Y}=\displaystyle\frac{Cov[X,Y]}{\sqrt{Var[X]Var[Y]}}=\frac{Cov[X,Y]}{\sigma_X\sigma_Y}$

独立则无关，无关不一定独立

$\hat X=aX+b,\hat Y=cY+d$

• $\rho_{\hat X,\hat Y}=\rho_{X,Y}$
• $Cov[\hat X,\hat Y]=ac\cdot Cov[X,Y]$

Other Theorem

• $Cov[X,Y]=r_{X,Y}-\mu_X\mu_Y$
• $Var[X+Y]=Var[X]+Var[Y]+2Cov[X,Y]$

Independence

Bivariate Gaussian Random Variables

Conditional PMF

$P_{X|Y}(x|y)=P[X=x|Y=y]=\displaystyle\frac{P_{X,Y}(x,y)}{P_Y(y)}$

Sample

Expected Value of Sums

$W_n=X_1+X_2+…+X_n$

$E[W_n]=E[X_1]+E[X_2]+…+E[X_n]$

$Var[W_n]=\displaystyle\sum_{i=1}^n Var[X_i]+2\sum_{i=1}^{n-1}\sum_{j=i+1}^n Cov[X_i,X_j]=\sum_{i=1}^{n}\sum_{j=1}^n Cov[X_i,X_j]$

其实就是任意两项（包括自己与自己）的协方差之和

Central Limit Theorem

$X_i:iid\Rightarrow\displaystyle Z_n=\frac{W_n-n\mu_{X}}{\sqrt{n\sigma_{X}^2},}\lim_{n\to+\infty}F_{Z_n}(z)=\Phi(z)=\frac{1}{\sqrt{2\pi}}\int_{-\infty}^ze^{-u^2/2}\mathrm{d}u$

iid：independent and identically distributed 独立同分布

Approximation: $F_{W_n}(w)\approx\Phi(\displaystyle\frac{W_n-n\mu_X}{\sqrt{n\sigma_X^2}})$

一种无视具体分布类型，利用 X 的期望和反差，用标准正态分布估计原 iid 的 CDF 的方法

DML Formula

$K = Binomial(n, p)$

$P[k_1\le K\le k_2]\approx\Phi(\displaystyle\frac{k_2+0.5-np}{\sqrt{np(1-p)}})-\Phi(\displaystyle\frac{k_2-0.5-np}{\sqrt{np(1-p)}})$

上下界~随意~扩展 0.5

Sample Mean

$M_n(X)=\displaystyle\frac{1}{n}(X_1+X_2+…+X_n)$

$M_n(X)$: Random Variable
$E[X]$: A Constant Number
$\displaystyle\lim_{n\to\infty}M_n(X)=E[X]$

$E[M_n(X)]=E[X]$

$Var[M_n(X)]=\displaystyle\frac{Var[X]}{n}$

$\displaystyle\lim_{n\to\infty}Var[M_n(X)]=0$

Useful Inequalities in Probability

Markov Inequality

$P[X<0]=0\to P[X\ge c^2]\le \displaystyle\frac{E[X]}{c^2}$

Chebyshev Inequality

let $X=(Y-\mu_Y)\to P[X\ge c^2]=P[(Y-\mu_Y)^2\ge c^2]\le\displaystyle\frac{Var[Y]}{c^2}$ or $P[X\ge c^2]=P[|Y-\mu_Y|\ge c]\le\displaystyle\frac{Var[Y]}{c^2}$

Laws of Large Numbers

$P[|M_n(X)-\mu_X|\ge c]\le Var[X]/(nc^2)$

$\lim_{n\to\infty}P[|M_n(X)-\mu_X|\ge c]= 0,c\to0\Rightarrow M_n(X)=\mu_X$

Point Estimates of Model Parameters

estimate: $r$

general estimates: $\hat R_n$ is a function of $X_1,X_2,…,X_n$

Consistent Estimator

defination(weak): $\forall\epsilon>0,\displaystyle\lim_{n\to\infty}P[|\hat R_n-r|\ge\epsilon]=0$

defination(strong): $\hat R=r$

Unbiased Estimator

defination: $E[\hat R]=r$

Asymptotically Unbiased Estimator

definaton: $\displaystyle\lim_{n\to\infty}E[\hat R_n]=r$

Mean Square Error

$e=E[(\hat R-r)^2]$

$\lim_{n\to\infty} e_n=0\Rightarrow\hat R_n$ is consistent

$M_n(X)$ is an unbiased estimate of $E[X]$

Standard Error

$\sqrt{e}$

Sample Variance

defination: $V_n(X)=\displaystyle\frac{1}{n}\sum_{i=1}^n(X_i-M_n(X))^2$

$E[V_n(X)]=\displaystyle(1-\frac{1}{n})Var[X]$

$E[V_n(X)]<Var[X]$