preliminaries

指数分布

定义

$F(x)=1-e^{-\theta x}$ or $f(x)=\theta e^{-\theta x}$

如何理解：考虑一个时间长度，它的分布如果服从指数分布，那么这个时间越长概率越低。

而如果时间非常短，在一个几乎为0的区间，那么这个概率和这个分布的参数一样。

考虑一个寿命情景，设寿命随机变量为$X$，所谓错误可以描述为
$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)}$
如果$\Delta t\to 0$就相当于是垂死前最后一刻，这个概率就可以表征错误概率，于是
$\alpha (t)\Delta t=\frac{f_X(t)\Delta t}{1-F_X(t)}=\frac{d{F}_X(t)}{1-F_X(t)}$
两侧求积分，解得，
$F_X(t)=1-e^{(-{\int }_0^t\alpha (t^{\prime })d{t}^{\prime })},f_X(t)=\alpha (t)e^{{\int }_0^t\alpha (t^{\prime })d{t}^{\prime }}$
$\alpha$如果是const，服从指数分布，无后效性。

性质

• 分布的数理性质

$E[X]={\int }_0^{\infty }xf(x)=\frac{1}{\theta }$
$Var[X]=\frac{1}{{\theta }^2}$

• 无记忆性

$\mathrm{Pr}[X>s+t|X>t]=\mathrm{Pr}[X>s]$

不论之前过去多长时间，再等待多长时间并不会因为之前的等待而发生变化。这里反直觉的地方在于：从整个概率分布来看，时间越长的概率就是更低的，那为啥等了这么长时间再等的概率和从头等一样呢？这是因为已经等待的时间已经发生了，不在有随机性，体现在公式上就是条件概率的那个分母。这就导致随机性完全体现在了接下来等待的时间上了。

• 最小值概率按参数成比例分配

一系列独立的指数分布，参数分别为${\theta }_1,\dots ,{\theta }_n$，那么$\mathrm{Pr}[\min (x_1,x_2,\dots ,x_n)]$服从参数为${\sum }_i{\theta }_i$的指数分布。且$\mathrm{Pr}[\min (x_1,\dots ,x_n)=x_i]=\frac{{\theta }_i}{{\sum }_k{\theta }_k}$

直观解释：指数分布的参数的含义是取值几乎为0的概率。那和明显谁的参数越大，谁越有可能取值几乎为0，而进一步的准确分析发现刚好是成正比的。

应用：有反馈的球和箱子

模型

假设两个箱子，里面球的数量是分别是x和y，下一个球落入两个箱子中的一个，概率为$\frac{x^p}{(x^p+y^p)},p>1$

解释：这个模型适合解释垄断现象，比如电脑的操作系统，人们会根据周围人使用的情况来选择自己的型号，所以可以近似把他选择的看成是上面的分布。

分析

这个模型的分析思路是构造了一个精确模仿过程。考虑下面的过程

两个箱子，每一个箱子隔一段时间会到来一个球，时间的间隔服从指数分布，参数分别为$x^p,y^p$。那么按照前面成比例分配到定理，下一个进入第一个箱子等价于该箱子的时间间隔是最小间隔，那这个概率恰好是$\frac{x^p}{x^p+y^p}$，所以两个独立指数分布的相互作用恰好描述了一次球的到达分布。

接下来分析球落入过程是否存在极限。定义$F_1={\sum }_i{T}_i$，那么$E[F_1]=E[{\sum }_i{T}_i]={\sum }_{i}E[T_i]={\sum }_i{i}^{-p}\le 1+\frac{1}{p-1}$，说明期望有限，这意味着极限情况下，球的数量不会无限制的增长。

此外，$F_1$和$F_2$以概率1不相同，这是因为假设$F_1=F_2$，那么 $T_1={\sum }_2^{\infty }{T}_i-F_2$，因为$T_1$的任何取值概率都为0，所以两者相等的概率也是0。

假设$F_1<F_2$，那一定存在一个n，$F_1<{\sum }_i^{n+1}{U}_i$，也就是说，在2号箱子到达n个球之前，1号箱子可以得到无穷的球。这是因为1号箱子的期望时间有限，说明球会疯狂进入这个箱子，而2号拿不到比n个球更多的球了。

Poisson过程

定义

计数过程：$N(t)$满足如下三个条件

• $N(0)=0$
• ${\lim }_{t\to 0}\mathrm{Pr}[N(t)=1]/t=\lambda$
• ${\lim }_{t\to 0}\mathrm{Pr}[N(t)\ge 2]=0$

后两条的意思是，在一个极短的时间内，数字增加1的概率是确定的，而增加2或更多几乎不可能。

经过一系列推理，其实他分布刚好是一个possion分布

$\mathrm{Pr}[N(t+s)-N(s)=k]=e^{-\lambda t}\frac{(\lambda t{)}^k}{k!}$

补充一点和Poisson相关但和这块没太有关系的知识点
如果我们有一个随机变量$Y$，他服从的分布$P$是一个到达强度随机变化的分布，但是对一个确定的到达强度是服从Poisson的，设到达强度分布为$f(x)$，假设我们可以观测到$Y$的数据从而估计$P$，如何倒推估计$f$呢？
$P(Y)={\int }_0^{\infty }P(Y|x)f(x)dx$
对$f(x)$，乘$e^{-x}$后做傅立叶变换
$F^{\prime }(\omega )={\int }_0^{\infty }{e}^{-x}f(x)e^{-j\omega x}dx$，之后taylor展开
$F^{\prime }(\omega )={\int }_0^{\infty }{e}^{-x}f(x){\sum }_{k=0}^{\infty }\frac{(-j\omega x{)}^k}{k!}dx$，交换顺序
$F^{\prime }(\omega )={\sum }_{k=0}^{\infty }(-j\omega {)}^k{\int }_0^{\infty }{e}^{-x}{x}^k/k!f(x)dx$，
发现刚好能凑出来一个poisson分布，然后积分完就是原始的$P$分布，所以
$F^{\prime }(\omega )={\sum }_{k=0}^{\infty }(-j\omega {)}^{k}P(Y)$，通过观测可以把$P$估计出来，然后就能进一步估计出$F^{\prime }$，再对F’做逆变换得到$e^{-x}f(x)$，再乘$e^x$即可。

性质

• 间隔是独立指数分布

考虑事件$X_i$表示从i-1增加到i的间隔时间。
那么$\mathrm{Pr}[X_1>t]=\mathrm{Pr}[N(t)=0]=e^{-\lambda t}$, 所以$\mathrm{Pr}[X_1<t]=1-e^{-\lambda t}$
对于一般的i,$\mathrm{Pr}[X_t>t_i|X_0=t_0,X_1=t_1,\dots ,X_{i-1}=t_{i-1}]=\mathrm{Pr}[N({\sum }_k^i{t}_k)-N({\sum }_k^{i-1}{t}_k)=0]=e^{-\lambda t_i}$
这也蕴含了他们之间是独立的。因为算$X_i$的时候其他的作为条件了但最后没有影响。

• 合并与分解

如果两个独立的poisson过程$N_1(t)$和$N_2(t)$求和，那么整体是一个服从${\lambda }_1+{\lambda }_2$的poisson。
如果按照p的概率分解成两个，那两个新的possion过程竟然独立，而且参数是$\lambda p$
当然从证明的角度可以从定义出发展开这些公式，但是从直观上感受一下，这一切的来源都是因为间隔时间是指数分布并且无记忆

• 条件分布

$\mathrm{Pr}[X_1<s|N(t)=1]=\frac{s}{t}$ 即，已知t时间内出现一个时间，那这个时间在s之前发生的概率刚好是时间的比值。
$\mathrm{Pr}[X_1<s|N(t)=1]=\frac{\mathrm{Pr}[X_1<s,N(t)=1]}{\mathrm{Pr}[N(t)=1]}=\frac{\mathrm{Pr}[N(t)-N(s)=0,N(s)=1]}{e^{-\lambda t}\lambda t}=\frac{\mathrm{Pr}[N(t)-N(s)=0]\mathrm{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(s)$的独立性
推广到n如果$N(t)=n$，那么n个到达时间与$[0,t]$上的n个均匀随机变量的顺序统计量同分布。

remark

性质1的计算从时间概率转移到计数概率上，而性质3的计算从计数概率转移到时间概率上。这种技巧很常用。

连续时间Markov过程

定义

关键是定义连续时间上的Markov Property：

$\mathrm{Pr}[X(s+t)|X(u),\forall u\in [0,t]]=\mathrm{Pr}[X(s+t)|X(t)]$

表示

表示的思路肯定是利用之前的离散时间Markov Chain。那么怎么利用呢，把状态转移之间时间看作是一个连续的时间随机，而每一次状态转移和以前是一样的。所以定义如下：

• 状态转移的骨架：$P_{ij}$表示从i转移到j的概率
• 参数向量：$({\theta }_1,\dots ,{\theta }_n)$，对应每个状态有一个指数分布，表示在状态i时，发生转移的时间间隔满足的分布。

平稳分布

定义${\pi }_i={\lim }_t{P}_{ji}(t)$ .

那么考虑导数$P_{ji}^{\prime }(t)={\lim }_{h\to 0}\frac{P_{ji}(t+h)-P_{ji}(t)}{h}={\lim }_{h\to 0}\frac{{\sum }_k{P}_{jk}(t)P_{ki}(h)-P_{ji}(t)}{h}$

这里最后一个等号的意思是，把t+h的时间拆成两步，第一步是t时间，第二步是h的时间，然后假设在h这里发生转移是从任何一个概率走的。

$P_{ji}^{\prime }(t)={\lim }_{h\to 0}({\sum }_{k\ne i}\frac{P_{ki}(h)}{h}{P}_{jk}(t)-\frac{1-P_{ii}(h)}{h}{P}_{ji}(t))$

对于$\frac{P_{ki}(h)}{h}$，h趋于0的时候表示在时间很短的时间发生转移并且从k转移到i的概率，这个按照定义就是${\theta }_k{p}_{ki}$，后面$\frac{1-P_{ii}(h)}{h}$这个注意1-P必须看成一个整体，因为1也在分子上。所以这个整体的含义是在极短的时间内，发生转移但没有留在i状态的概率，即${\theta }_i(1-p_{ii})$。

所以最后$P_{ji}^{\prime }(t)={\sum }_k{\theta }_k{p}_{ki}{\pi }_k-{\theta }_i{\pi }_i$，平稳分布的话，t趋于无穷的时候导数为0，然后利用${\lim }_t{P}_{ji}(t)={\pi }_i$所以得到如下速度方程

${\pi }_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)$表示队列长度随时间变化的随机过程，试分析其平稳分布，即${\lim }_{t\to \infty }\mathrm{Pr}[M(t)=k]\forall k$

先分析$\mathrm{Pr}[M(t)=0]=P_0(t)$的稳定分布，思路和前面一样，还是分析导数

$P_0^{\prime }(t)={\lim }_h\frac{P_0^{\prime }(t+h)-P_0^{\prime }(t)}{h}$

之后就很神奇，还是把t+h的时间分成两段，在h这个极小的时间里，至多发生一次转移，所以在t+h变成0有两种可能，一种是本来就是0没发生转移（概率为$P_0(t)(1-\lambda h)$），一种是之前是1，转移到了0（概率为$P_1(t)\mu h$），带入可得$P_0^{\prime }(t)=-\lambda P_0(t)+\mu P_1(t)$，两侧去极限可以得到关于平稳分布的方程，其他情况也类似。解方程组，并满足概率分布和为1，可得

${\pi }_k=(1-\frac{\lambda }{\mu })(\frac{\lambda }{\mu }{)}^k$

有了平稳分布可以求期望，这个期望是长度，所以用Length的L表示$L=\frac{\lambda }{\mu -\lambda }$

等待时间用Waiting time是W表示。

$W={\sum }_{k=0}^{\infty }E[W|L(k)]Pr[L(k)]$

对于$E[W|L(k)]=(k+1)\frac{1}{\mu }$，这是因为队列前面有k个人，算上我自己有k+1个人，每个人等待时间独立，然后期望时间$\mu$，所以在到达时队列有k个人的时候，期望很容易。接下来分析$\mathrm{Pr}[L(k)]$。这里用到了PASTA原则，即如果顾客到达满足poisson分布，那么他身处这个队列看到前面有k个人和外部观察这个队列有k个人的分布是一样的，这是因为Poisson分布的无记忆性，后面的人分布不受前面影响。所以$Pr[L(k)]={\pi }_k$。

因此，$W=\frac{L}{\lambda }$。

上面这个W和L的关系被称为Little结果，对任意稳定排队系统成立。

M/M/1/K

容量为K的分析和前面基本一致，递推方程组也是一样的，只是他最多只分析到K，然后可以得出分布列

${\pi }_k={\pi }_0(\lambda /\mu {)}^k,{\pi }_0=\frac{1}{{\sum }_k(\lambda /\mu {)}^k}$

M/M/$\infty$

${\pi }_k=\frac{e^{-\lambda /\mu }(\lambda /\mu {)}^k}{k!}$