preliminaries
指数分布
定义
F(x)=1−e−θxF(x) = 1 – e^{-theta x} or f(x)=θe−θxf(x)=theta e^{-theta x}
如何理解:考虑一个时间长度,它的分布如果服从指数分布,那么这个时间越长概率越低。
而如果时间非常短,在一个几乎为0的区间,那么这个概率和这个分布的参数一样。
考虑一个寿命情景,设寿命随机变量为XX,所谓错误可以描述为
P(t<X<t+Δt∣X>t)=P(t<X<t+Δt)P(X>t)=FX(t+Δt)−FX(t)1−FX(t)P(t<X<t+Delta t|X>t)=frac{P(t<X<t+Delta t)}{P(X>t)} =frac{F_X(t+Delta t)-F_X(t)}{1-F_X (t)}
如果Δt→0Delta trightarrow 0就相当于是垂死前最后一刻,这个概率就可以表征错误概率,于是
α(t)Δt=fX(t)Δt1−FX(t)=dFX(t)1−FX(t)alpha(t)Delta t=frac{f_X(t)Delta t}{1-F_X(t)}=frac{dF_X(t)}{1-F_X(t)}
两侧求积分,解得,
FX(t)=1−e(−∫0tα(t′)dt′),fX(t)=α(t)e∫0tα(t′)dt′F_X(t)=1-e^{(-int_0^talpha(t’)dt’)}, f_X(t)=alpha(t)e^{int_0^talpha(t’)dt’}
αalpha如果是const,服从指数分布,无后效性。
性质
- 分布的数理性质
E[X]=∫0∞xf(x)=1θE[X]=int_0^infty x f(x)=frac{1}{theta}
Var[X]=1θ2Var[X]=frac{1}{theta^2}
- 无记忆性
Pr[X>s+t∣X>t]=Pr[X>s]Pr[X>s + t|X>t] = Pr[X>s]
不论之前过去多长时间,再等待多长时间并不会因为之前的等待而发生变化。这里反直觉的地方在于:从整个概率分布来看,时间越长的概率就是更低的,那为啥等了这么长时间再等的概率和从头等一样呢?这是因为已经等待的时间已经发生了,不在有随机性,体现在公式上就是条件概率的那个分母。这就导致随机性完全体现在了接下来等待的时间上了。
- 最小值概率按参数成比例分配
一系列独立的指数分布,参数分别为θ1,…,θntheta_1, …, theta_n,那么Pr[min(x1,x2,…,xn)]Pr[min(x_1, x_2, …, x_n)]服从参数为∑iθisum_i theta_i的指数分布。且Pr[min(x1,…,xn)=xi]=θi∑kθkPr[min(x_1, …, x_n)=x_i]=frac{theta_i}{sum_k theta_k}
直观解释:指数分布的参数的含义是取值几乎为0的概率。那和明显谁的参数越大,谁越有可能取值几乎为0,而进一步的准确分析发现刚好是成正比的。
应用:有反馈的球和箱子
模型
假设两个箱子,里面球的数量是分别是x和y,下一个球落入两个箱子中的一个,概率为xp(xp+yp),p>1frac{x^p}{(x^p + y^p)}, p > 1
解释:这个模型适合解释垄断现象,比如电脑的操作系统,人们会根据周围人使用的情况来选择自己的型号,所以可以近似把他选择的看成是上面的分布。
分析
这个模型的分析思路是构造了一个精确模仿过程。考虑下面的过程
两个箱子,每一个箱子隔一段时间会到来一个球,时间的间隔服从指数分布,参数分别为xp,ypx^p, y^p。那么按照前面成比例分配到定理,下一个进入第一个箱子等价于该箱子的时间间隔是最小间隔,那这个概率恰好是xpxp+ypfrac{x^p}{x^p + y^p},所以两个独立指数分布的相互作用恰好描述了一次球的到达分布。
接下来分析球落入过程是否存在极限。定义F1=∑iTiF_1=sum_i T_i,那么E[F1]=E[∑iTi]=∑iE[Ti]=∑ii−p≤1+1p−1E[F_1]=E[sum_i T_i]=sum_i E[T_i]=sum_i i^{-p}le 1 + frac{1}{p-1},说明期望有限,这意味着极限情况下,球的数量不会无限制的增长。
此外,F1F_1和F2F_2以概率1不相同,这是因为假设F1=F2F_1=F_2,那么 T1=∑2∞Ti−F2T_1=sum_2^infty T_i – F_2,因为T1T_1的任何取值概率都为0,所以两者相等的概率也是0。
假设F1<F2F_1 < F_2,那一定存在一个n,F1<∑in+1UiF_1 < sum_i^{n+1} U_i,也就是说,在2号箱子到达n个球之前,1号箱子可以得到无穷的球。这是因为1号箱子的期望时间有限,说明球会疯狂进入这个箱子,而2号拿不到比n个球更多的球了。
Poisson过程
定义
计数过程:N(t)N(t)满足如下三个条件
- N(0)=0N(0)=0
- limt→0Pr[N(t)=1]/t=λlim_{trightarrow 0} Pr[N(t)=1]/t=lambda
- limt→0Pr[N(t)≥2]=0lim_{trightarrow 0} Pr[N(t)ge 2]=0
后两条的意思是,在一个极短的时间内,数字增加1的概率是确定的,而增加2或更多几乎不可能。
经过一系列推理,其实他分布刚好是一个possion分布
Pr[N(t+s)−N(s)=k]=e−λt(λt)kk!Pr[N(t+s)-N(s)=k]=e^{-lambda t}frac{(lambda t)^k}{k!}
补充一点和Poisson相关但和这块没太有关系的知识点
如果我们有一个随机变量YY,他服从的分布PP是一个到达强度随机变化的分布,但是对一个确定的到达强度是服从Poisson的,设到达强度分布为f(x)f(x),假设我们可以观测到YY的数据从而估计PP,如何倒推估计ff呢?
P(Y)=∫0∞P(Y∣x)f(x)dxP(Y)=int_0^infty P(Y|x)f(x)dx
对f(x)f(x),乘e−xe^{-x}后做傅立叶变换
F′(ω)=∫0∞e−xf(x)e−jωxdxF'(omega)=int_0^infty e^{-x}f(x)e^{-jomega x}dx,之后taylor展开
F′(ω)=∫0∞e−xf(x)∑k=0∞(−jωx)kk!dxF'(omega)=int_0^infty e^{-x}f(x)sum_{k=0}^inftyfrac{(-jomega x)^k}{k!} dx,交换顺序
F′(ω)=∑k=0∞(−jω)k∫0∞e−xxk/k!f(x)dxF'(omega)= sum_{k=0}^infty (-jomega)^k int_0^infty e^{-x}x^k/k! f(x) dx,
发现刚好能凑出来一个poisson分布,然后积分完就是原始的PP分布,所以
F′(ω)=∑k=0∞(−jω)kP(Y)F'(omega)= sum_{k=0}^infty (-jomega)^k P(Y),通过观测可以把PP估计出来,然后就能进一步估计出F′F’,再对F’做逆变换得到e−xf(x)e^{-x}f(x),再乘exe^x即可。
性质
- 间隔是独立指数分布
考虑事件XiX_i表示从i-1增加到i的间隔时间。
那么Pr[X1>t]=Pr[N(t)=0]=e−λtPr[X_1>t]=Pr[N(t)=0]=e^{-lambda t}, 所以Pr[X1<t]=1−e−λtPr[X_1<t]=1-e^{-lambda t}
对于一般的i,Pr[Xt>ti∣X0=t0,X1=t1,…,Xi−1=ti−1]=Pr[N(∑kitk)−N(∑ki−1tk)=0]=e−λtiPr[X_t>t_i|X_0=t_0, X_1=t_1, …, X_{i-1}=t_{i-1}]=Pr[N(sum_k^{i} t_k)-N(sum_k^{i-1} t_k)=0]=e^{-lambda t_i}
这也蕴含了他们之间是独立的。因为算XiX_i的时候其他的作为条件了但最后没有影响。
- 合并与分解
如果两个独立的poisson过程N1(t)N_1(t)和N2(t)N_2(t)求和,那么整体是一个服从λ1+λ2lambda_1+lambda_2的poisson。
如果按照p的概率分解成两个,那两个新的possion过程竟然独立,而且参数是λplambda p
当然从证明的角度可以从定义出发展开这些公式,但是从直观上感受一下,这一切的来源都是因为间隔时间是指数分布并且无记忆
- 条件分布
Pr[X1<s∣N(t)=1]=stPr[X_1<s | N(t)=1]=frac{s}{t} 即,已知t时间内出现一个时间,那这个时间在s之前发生的概率刚好是时间的比值。
Pr[X1<s∣N(t)=1]=Pr[X1<s,N(t)=1]Pr[N(t)=1]=Pr[N(t)−N(s)=0,N(s)=1]e−λtλt=Pr[N(t)−N(s)=0]Pr[N(s)=1]e−λtλt=e−λ(t−s)λse−λse−λtλt=stPr[X_1<s | N(t)=1]=frac{Pr[X_1<s, N(t)=1]}{Pr[N(t)=1]}=frac{Pr[N(t)-N(s)=0,N(s)=1]}{e^{-lambda t}lambda t}=frac{Pr[N(t)-N(s)=0]Pr[N(s)=1]}{e^{-lambda t}lambda t}=frac{e^{-lambda (t-s)}lambda s e^{-lambda s}}{e^{-lambda t}lambda t}=frac{s}{t}
这里利用了,N(t)−N(s)N(t)-N(s)和N(s)N(s)的独立性
推广到n如果N(t)=nN(t)=n,那么n个到达时间与[0,t][0,t]上的n个均匀随机变量的顺序统计量同分布。
remark
性质1的计算从时间概率转移到计数概率上,而性质3的计算从计数概率转移到时间概率上。这种技巧很常用。
连续时间Markov过程
定义
关键是定义连续时间上的Markov Property:
Pr[X(s+t)∣X(u),∀u∈[0,t]]=Pr[X(s+t)∣X(t)]Pr[X(s+t)|X(u), forall uin [0, t]]=Pr[X(s+t)|X(t)]
表示
表示的思路肯定是利用之前的离散时间Markov Chain。那么怎么利用呢,把状态转移之间时间看作是一个连续的时间随机,而每一次状态转移和以前是一样的。所以定义如下:
- 状态转移的骨架:PijP_{ij}表示从i转移到j的概率
- 参数向量:(θ1,…,θn)(theta_1,…, theta_n),对应每个状态有一个指数分布,表示在状态i时,发生转移的时间间隔满足的分布。
平稳分布
定义πi=limtPji(t)pi_i=lim_t P_{ji}(t) .
那么考虑导数Pji′(t)=limh→0Pji(t+h)−Pji(t)h=limh→0∑kPjk(t)Pki(h)−Pji(t)hP’_{ji}(t)=lim_{hrightarrow 0}frac{P_{ji}(t+h)-P_{ji}(t)}{h}=lim_{hrightarrow 0}frac{sum_k P_{jk}(t)P_{ki}(h)-P_{ji}(t)}{h}
这里最后一个等号的意思是,把t+h的时间拆成两步,第一步是t时间,第二步是h的时间,然后假设在h这里发生转移是从任何一个概率走的。
Pji′(t)=limh→0(∑k≠iPki(h)hPjk(t)−1−Pii(h)hPji(t))P’_{ji}(t)=lim_{hrightarrow 0}(sum_{kne i}frac{P_{ki}(h)}{h}P_{jk}(t)-frac{1-P_{ii}(h)}{h}P_{ji}(t))
对于Pki(h)hfrac{P_{ki}(h)}{h},h趋于0的时候表示在时间很短的时间发生转移并且从k转移到i的概率,这个按照定义就是θkpkitheta_k p_{ki},后面1−Pii(h)hfrac{1-P_{ii}(h)}{h}这个注意1-P必须看成一个整体,因为1也在分子上。所以这个整体的含义是在极短的时间内,发生转移但没有留在i状态的概率,即θi(1−pii)theta_i (1-p_{ii})。
所以最后Pji′(t)=∑kθkpkiπk−θiπiP’_{ji}(t)=sum_k theta_kp_{ki}pi_k-theta_ipi_i,平稳分布的话,t趋于无穷的时候导数为0,然后利用limtPji(t)=πilim_t P_{ji}(t)=pi_i所以得到如下速度方程
πiθi=∑kπkθkpkipi_i theta_i=sum_k pi_k theta_k p_{ki}
这个方程的含义,lhs表示离开i的速度,而rhs表示进入i的速度,动态平衡
两个排队论模型
排队论模型的公式一般表示为A/B/C/D,其中A是顾客到达的分布,B是顾客离开的分布,C是服务窗口数,D是队列的长度
顾客到来有3个动作,到达、进入、和离开。到达和进入的区别在于队列长度有限的时候,队列满了到达之后就不在进入了。
M/M/1
设M(t)M(t)表示队列长度随时间变化的随机过程,试分析其平稳分布,即limt→∞Pr[M(t)=k]∀klim_{trightarrow infty}Pr[M(t)=k] forall k
先分析Pr[M(t)=0]=P0(t)Pr[M(t)=0]=P_0(t)的稳定分布,思路和前面一样,还是分析导数
P0′(t)=limhP0′(t+h)−P0′(t)hP’_0(t)=lim_h frac{P’_0(t+h) – P’_0(t)}{h}
之后就很神奇,还是把t+h的时间分成两段,在h这个极小的时间里,至多发生一次转移,所以在t+h变成0有两种可能,一种是本来就是0没发生转移(概率为P0(t)(1−λh)P_0(t)(1-lambda h)),一种是之前是1,转移到了0(概率为P1(t)μhP_1(t)mu h),带入可得P0′(t)=−λP0(t)+μP1(t)P’_0(t)=-lambda P_0(t)+mu P_1(t),两侧去极限可以得到关于平稳分布的方程,其他情况也类似。解方程组,并满足概率分布和为1,可得
πk=(1−λμ)(λμ)kpi_k=(1-frac{lambda}{mu})(frac{lambda}{mu})^k
有了平稳分布可以求期望,这个期望是长度,所以用Length的L表示L=λμ−λL=frac{lambda}{mu – lambda}
等待时间用Waiting time是W表示。
W=∑k=0∞E[W∣L(k)]Pr[L(k)]W=sum_{k=0}^infty E[W|L(k)]Pr[L(k)]
对于E[W∣L(k)]=(k+1)1μE[W|L(k)]=(k+1)frac{1}{mu},这是因为队列前面有k个人,算上我自己有k+1个人,每个人等待时间独立,然后期望时间μmu,所以在到达时队列有k个人的时候,期望很容易。接下来分析Pr[L(k)]Pr[L(k)]。这里用到了PASTA原则,即如果顾客到达满足poisson分布,那么他身处这个队列看到前面有k个人和外部观察这个队列有k个人的分布是一样的,这是因为Poisson分布的无记忆性,后面的人分布不受前面影响。所以Pr[L(k)]=πkPr[L(k)]=pi_k。
因此,W=LλW=frac{L}{lambda}。
上面这个W和L的关系被称为Little结果,对任意稳定排队系统成立。
M/M/1/K
容量为K的分析和前面基本一致,递推方程组也是一样的,只是他最多只分析到K,然后可以得出分布列
πk=π0(λ/μ)k,π0=1∑k(λ/μ)kpi_k=pi_0(lambda/mu)^k, pi_0=frac{1}{sum_k (lambda/mu)^k}
M/M/∞infty
πk=e−λ/μ(λ/μ)kk!pi_k=frac{e^{-lambda/mu}(lambda/mu)^k}{k!}