计算机网络数学基础

Blockchain

字数统计: 6.6k阅读时长: 26 min

 2020/10/28   Share

区块链中的数学很重要，推荐《计算机网络数学基础》这本书重点学习，搭配《应用随机过程概率模型导论》食用更佳。

参考链接：https://blog.csdn.net/bitcarmanlee/article/details/82819860

马尔可夫链

马尔可夫不等式

如果X是均值为μ的非负随机变量，则对于任一常量a>0有：

$p(X≥a)≤{μ \over a}$

什么是马尔可夫链

马尔可夫链（Markov chain），又称离散时间马尔可夫链（discrete-time Markov chain），因俄国数学家安德烈·马尔可夫得名，为状态空间中经过从一个状态到另一个状态的转换的随机过程。该过程要求具备“无记忆”的性质：下一状态的概率分布只能由当前状态决定，在时间序列中它前面的事件均与之无关。这种特定类型的“无记忆性”称作马尔可夫性质。

对于一个马尔可夫链，在给定过去的状态$X_0,X_1,…，X_{n-1}$和现在的状态$X_n$时，将来的状态$X_{n+1}$的条件分布独立于过去的状态，且只依赖于现在的状态。用数学公式来描述就是：

$P(x_{n+1}|…,x_{n-2},x_{x-1},x_n)=P(x_{n+1}|x_n)$

这个马尔科夫链是表示股市模型的，共有三种状态：牛市（Bull market）, 熊市（Bear market）和横盘（Stagnant market）。每一个状态都以一定的概率转化到下一个状态。比如，牛市以0.025的概率转化到横盘的状态。这个状态概率转化图可以以矩阵的形式表示。如果我们定义矩阵阵P某一位置P(i, j)的值为P(j|i)，即从状态i变为状态j的概率。另外定义牛市、熊市、横盘的状态分别为0、1、2，这样我们得到了马尔科夫链模型的状态转移矩阵为：

$\begin{matrix} 0.9 & 0.075 & 0.025 \\ 0.15 & 0.8 & 0.05 \\ 0.25 & 0.25 & 0.5 \end{matrix}$

当这个状态转移矩阵P确定以后，整个股市模型就已经确定。

转移概率矩阵(状态转移矩阵)

转移概率矩阵
●对于一个马尔可夫链{$P_n,n=1,2…$}，称以m步转移概率$P_{ij}(m)$为
元素的矩阵P(m)=($P_{ij}(m)$)为马尔可夫链的m步转移矩阵。
性质:
(1) 0 ≤$P_{ij}(m)$ ≤1:概率在0~1之间
(2) 对于任意的i∈E，$\sum_{j∈E}P_{ij}(m)$: 概率之和为1

从上面的例子不难看出来，整个马尔可夫链模型的核心是状态转移矩阵P。那这个矩阵P有一些什么有意思的地方呢？接下来再看一下。
以股市模型为例，假设初始状态为t0 = [ 0.1 , 0.2 , 0.7 ] ，然后算之后的状态。

def markov():
    init_array = np.array([0.1, 0.2, 0.7])
    transfer_matrix = np.array([[0.9, 0.075, 0.025],
                               [0.15, 0.8, 0.05],
                               [0.25, 0.25, 0.5]])
    restmp = init_array
    for i in range(25):
        res = np.dot(restmp, transfer_matrix)
        print i, "\t", res
        restmp = res

markov()

最终输出的结果：

0 [0.295 0.3425 0.3625]
1 [0.4075 0.38675 0.20575]
2 [0.4762 0.3914 0.1324]
3 [0.52039 0.381935 0.097675]
4 [0.55006 0.368996 0.080944]
5 [0.5706394 0.3566873 0.0726733]
6 [0.58524688 0.34631612 0.068437 ]
7 [0.59577886 0.33805566 0.06616548]
8 [0.60345069 0.33166931 0.06487999]
9 [0.60907602 0.32681425 0.06410973]
10 [0.61321799 0.32315953 0.06362248]
11 [0.61627574 0.3204246 0.06329967]
12 [0.61853677 0.31838527 0.06307796]
13 [0.62021037 0.31686797 0.06292166]
14 [0.62144995 0.31574057 0.06280949]
15 [0.62236841 0.31490357 0.06272802]
16 [0.62304911 0.31428249 0.0626684 ]
17 [0.62355367 0.31382178 0.06262455]
18 [0.62392771 0.31348008 0.06259221]
19 [0.624205 0.3132267 0.0625683]
20 [0.62441058 0.31303881 0.06255061]
21 [0.624563 0.31289949 0.06253751]
22 [0.624676 0.3127962 0.0625278]
23 [0.62475978 0.31271961 0.06252061]
24 [0.6248219 0.31266282 0.06251528]

从第18次开始，状态就开始收敛至[ 0.624 , 0.312 , 0.0625 ] 。最终数字上略有不同，只是计算机浮点数运算造成的罢了。

如果我们换一个初始状态t0，比如[ 0.2 , 0.3.0.5 ]，继续运行上面的代码，只是将init_array变一下，最后结果为：

0 [ 0.35 0.38 0.27]
1 [ 0.4395 0.39775 0.16275]
2 [ 0.4959 0.39185 0.11225]
3 [ 0.53315 0.378735 0.088115]
4 [ 0.558674 0.365003 0.076323]
5 [ 0.5766378 0.3529837 0.0703785]
6 [ 0.5895162 0.34322942 0.06725438]
7 [ 0.59886259 0.33561085 0.06552657]
8 [ 0.6056996 0.32978501 0.06451539]
9 [ 0.61072624 0.32538433 0.06388944]
10 [ 0.61443362 0.32208429 0.06348209]
11 [ 0.61717343 0.31962047 0.0632061 ]
12 [ 0.61920068 0.31778591 0.06301341]
13 [ 0.62070185 0.31642213 0.06287602]
14 [ 0.62181399 0.31540935 0.06277666]
15 [ 0.62263816 0.31465769 0.06270415]
16 [ 0.62324903 0.31410005 0.06265091]
17 [ 0.62370187 0.31368645 0.06261168]
18 [ 0.62403757 0.31337972 0.06258271]
19 [ 0.62428645 0.31315227 0.06256128]
20 [ 0.62447096 0.31298362 0.06254542]
21 [ 0.62460776 0.31285857 0.06253366]
22 [ 0.62470919 0.31276586 0.06252495]
23 [ 0.62478439 0.31269711 0.0625185 ]
24 [ 0.62484014 0.31264614 0.06251372]

到第18次的时候，又收敛到了[ 0.624 , 0.312 , 0.0625 ]这个转移矩阵就厉害了。不管我们的初始状态是什么样子的，只要状态转移矩阵不发生变化，当n→∞时最终的状态永远会收敛到一个固定的值。

马尔可夫链细致平稳条件

首先，马尔科夫链要能收敛，需要满足以下条件：
1.可能的状态数是有限的。
2.状态间的转移概率需要固定不变。
3.从任意状态能够转变到任意状态。
4.不能是简单的循环，例如全是从x到y再从y到x。

以上是马尔可夫链收敛的必要条件。

马尔可夫过程

马尔可夫过程性质（时间参数离散的随机过程情形）的形式化表示：

$P(X_{n+1})=P(X_{n+1}=j|X_n=i_n)$

条件概论$P(X_{n+1}=j|X_n=i_n)$称之为从状态$i_n$转移到j的转移概论。

马尔可夫性质允许我们忘记除了当前随机变量的值（其中包括了所有过去的行为）外所有的历史信息。

为了简化问题，在考虑时间连续马尔可夫过程之间，我们首先讨论遵守马尔可夫性质的时间参数离散过程，其又可称为离散时间马尔可夫链。

如果一个随机过程的转移概率是依赖于时间的，则称其为非齐次马尔可夫过程

设定转移概率是时间独立的，这样的过程位置为时齐或齐次马尔可夫过程。其定义为：对于任意n，我们定义时间独立的从状态$i$转移到$j$的转移概率为$P_{ij}=P(X_n=j|X_{n-1}=i)$。

右随机矩阵：是实方阵，其中每一行求和为1。

齐次马尔可夫过程

给定一个齐次马尔可夫链的状态转移概率$P_{ij}$的集合，我们可以定义从状态$i$到$j$的m步转移概率为：

$p_{ij}^{(m)}=P(X_{n+m}=j|X_n=i)=\sum_kp_{ik}^{m-1}p_{kj}\qquad m=2,3,....$

上式乘积形式的和来自于独立事件的相加（即通过m-1步跳转到某个中间状态），每一个相加的项都是一个乘积，这是因为这是两个独立事件的组合（从状态$i$到$k$事件和从状态$k$到$m$事件）。这些关系仅仅因为马尔可夫链的特性而存在。相应的切普曼-柯尔莫戈洛夫方程表述如下：

$p_{ij}^{(m)}=P(X_{n+m}=j|X_n=i)=\sum_kp_{ik}p_{kj}^{m-1}\qquad m=2,3,....$

以上两个公式的区别：第一个公式中的过程轨迹是经过m-1步从状态$i$到达$k$，然后再经过一步从状态$k$到达$j$。第二个公式中的过程轨迹是经过一步从状态$i$到达$k$，然后再经过$n-1$步从状态$k$到达$j$。很明显这两个公式等价。

不可简约性

如果一个随机过程中的每一个状态都可以经过有限步从其他任意状态到达，那么这样的过程称之为不可简约的，否则就是可简约的。更进一步，如果一个随机过程的状态可以分为几个子集，子集之间是互相不可到达的，那么我们称之为可分离的子链。

常返性

对于一个随机过程中的每个状态$j$，一下两个条件必定有一个成立：在进入状态$j$之后，经过有限步回到状态$j$的概率为1，或者在有限步之内不能重返的概率非零。如果返回一个状态是肯定的，我们称这个状态为常返的，否则称为过渡的。

用$f_j^n$表示经过n步之后第一次返回状态j的概率。如果有$\sum_{n=1}^∞f_j^n=1$，那么状态$j$为常返的，否则为过渡的。

尽管一个状态是常返的，它的期望返回时长（定义为$\sum_{n=1}^∞nf_j^n$）可能是无限大的。当平均常返时长为无限大，则称这个状态为零常返态，否则称之为非零常返态。

周期性

给定一个常返态$j$，假设返回这个状态的唯一方法是经过r,2r,3r,…步，其中r≥2。我们称该状态$j$为周期性的，且周期为r。当马尔可夫链出现圆圈时就会有周期状态。判别的方法是观察是否存在自循环，即$P_{jj}>0$。如果有，这个状态在任意步之内都可以再次返回，其中r=1，这个状态就是非周期性。对于一个不可简约马尔可夫链，如果任意一个状态都有自循环，那么所有的状态都是非周期性的。

各态历经性

一个随机过程访问状态的序列称之为轨迹。这个统计量是该状态出现次数占轨迹长度的比率极限。我们称这个极限为时间平均。

建设我们想要计算在任意一时间步骤上所有轨迹的统计量。如果这个统计量计算存在，通过使得总体足够大，我们可以尽可能地近似它。我们称这样的极限为总体均值。

如果每个统计数据既可以通过单个足够长的轨迹上计算出时间平均，又可以在数量足够多的轨迹上计算出总体均值，那么成这样的随机过程是各态经历的。

一个有限非周期且不可简约的马尔可夫链总是各态经历的。（换句话说，一个有限不可简约的马尔可夫链中的所有状态都是非零常返的）。

各态经历的马尔可夫链

如果一个各态经历的链对初始状态π(0)不敏感：独立于初始状态，$X_n$的分布π(n)（n的取值要足够大）都是一样的。非各态经历的链要么是零常返的（这样需要花费很长的时间才能返回到同样的状态或则是可简约的（这样链中的一些部分不和其他部分联系），又或者是周期性的。

马尔可夫链的平稳概率

一个齐次马尔可夫链，状态转移概率是与时间无关的。

对于一个齐次链，期望在一个某一个状态的概率也是时间无关的（如果从一个状态转移到另一个状态的概率与时间无关，那么处于这一状态的概率也应该是与时间无关的）。

马尔可夫链的平稳概率分布如下：假定我们从初始分布π(0)=$π^$开始。那么如果对于所有的n有π(0)=$π^$。$π^*$同样也是这个链的平稳分布。如果我们以每个状态$j$所定义平稳分布开始，那么根据转移概率从各个状态转移到其他状态，并不会改变马尔可夫链处于每个状态的概率。

两个基本定理

定理一：一个不可简约的马尔可夫链的状态处于一下几种情况之一：都是过渡的，都是零常返的或者都是非零常返的。如果任意一个状态是周期的，那么所有的状态都是周期的，且有相同的周期r。

定理二：在一个不可简约且非周期的齐次马尔可夫链中，概率分布的极限

$π^*=\lim_{n \to ∞}π(n)$

总是存在并且与初始状态概率分布π(0)独立。更进一步，如果所有的状态是各态经历的(非零常返，且非周期)，那么处于状态$j$的平稳概率$π_j^*$非零且可以通过以下公式组唯一确定：

$f(x)=\left\{ \begin{aligned} \sum_jπ_j^* =1 \\ π_j^* =\sum_jπ_j^*p_{ij} \end{aligned} \right.$

连续时间马尔可夫链

时间参数离散的马尔可夫链：每一次时钟步进就发生状态改变。而连续时间参数的链中状态转移的发生于时钟步进无关。其中两者的主要差异在于：需要考虑连续时间链中状态转移发生在某些瞬间$t_1,t_2,t_3…$而不是每次时钟步进就发生一次状态转移。时间参数连续过程中最特殊的类型为：生灭过程。

连续时间随机过程的马尔可夫性质：随机过程X(t)是一个连续时间的马尔可夫链，如果对于所有的整数n和任意的时间序列$t_1,t_2,…,t_{n+1}$且$t_1<t_2<…<t_{n+1}$有：

$P(X(t_{n+1}))=j|X(t_1)=i_1,X(t_2)=i_2,...,X(t_n)=i_n)$ $=P(X(t_{n+1}))=j|X(t_n)=i_n$

直观上来看，这意味着未来的状态$X(t_{n+1})$仅仅依赖于当前的状态$i_n$。

连续时间马尔可夫链中的平稳概率分布

连续时间马尔可夫链中的平稳概率分布的定义与时间参数离散情形下类似。

用以下公式定义从状态$i$到$j$的状态转移概率：

$p_{ij}(t)=P(X(s+t)=j|X(s)=i)$

在任一时间$s$处于状态$i$，那么经过一段时间$t$之后它转移到状态j的概率$p_{ij}(t)$

给出。此概率值与$s$的取值独立，因为这个过程是齐次的。

定义变量$q_{ij}$，其表示该过程离开状态$i$到$j$（此外$i$和$j$不同）的速率为：

$q_{ij}=\lim_{\Delta t \to ∞}[p_{ij}(\Delta t)]/\Delta t$

该式子意义为：已经在状态$i$的条件下，在任一长度为$\Delta t$的时间区域内该过程从$i$到$j$的概率为$q_{ij}\Delta t$。另外用以下公式定义值为负的变量$q_{ii}$：

$q_{ii}=-\sum_{j≠i}q_{ij}$

$-q_{ij}$表示在时间长度为$\Delta t$的区域中该过程不在停留在状态$i$的速率。因为有$\sum_jp_{ij}(t)=1$（在任一时刻t，该链转移到某些状态，包括当前的状态），我们有

$\sum_jq_{ij}(t)=0$

通过以上的变量，定义在时刻t处于状态j的概率随着时间的变化为$π_j(t)$：

$\frac {dπ_j(t)}{dt}=q_{jj}π_j(t)+\sum_{k≠j}q_{kj}π_k(t)$

接下来需要注重一个更小的子类：连续时间生灭过程。

生灭过程

连续时间齐次马尔可夫链中一个特殊的分类，该分类过程状态的转移只允许从状态$j$到$j-1$或者$j+1$（如果这些状态存在）。这类随机过程非常适合描述队列中顾客的到达与离开过程，其中状态下标对应于等待服务的顾客数量。

具体的来说：如果在系统中的顾客数量为j，那么这个马尔可夫链就认为处于状态$j$。到达一个顾客，该过程转移到状态$j+1$，转移发生的速率为$q_{j,j+1}$。相对的顾客的离开使该过程从状态$j$移动到$j-1$，并且发生速率为$q_{j,j-1}$。具体公式

$\lambda_j=q_{j,j+1}$ $\mu_j=q_{j,j-1}$

这两个式子为出生和死亡速率。这些速率可以是状态独立，但是由于该过程的齐次性，不能是时间独立的。同样根据定义，在状态$i$，对于除了取值$i,i+1,i-1$的所有$j$转移概率$q_{ij}$都为0。即：只有$q_{ii},q_{i,i+1},q_{i,i-1}$三个式子有取值，其余的式子取值均为0。另外根据以上的式子可以得出：

$q_{jj}=-(\lambda_j+\mu_j)$

对于一个生灭过程，处于状态$j$有一个直观上的意义：人口数量为$j$，即排队系统中有$j$个顾客。一般来说，在状态$j$的时候，我们有一个顾客在接受服务并且有$j-1$个顾客在队列中等待服务。

生灭过程的平稳概率分布

因为生灭过程是一个各态历经的时间连续的马尔可夫链，它的平稳概率分布为：

$\left\{ \begin{aligned} q_{jj}π^*_j+\sum_{k≠j}q_{kj}π_k^*=0 \\ \sum_jπ_j^*=1 \end{aligned} \right.$

用$π_j^*P_j$表示在状态$j$的平稳概率，并用以上的公式替代相关的变量可以得到以下的公式：

$\left\{ \begin{aligned} &0=-(\lambda_j+\mu_j)π_j^*+\lambda_{j-1}π_{j-1}+\mu_{j+1}π^*_{j+1} \qquad &j≥1 \\ &0=-\lambda_0π_0^*+\mu_1π_1^* \qquad &j=0 \\ &\sum_jπ_j^*=1 \end{aligned} \right.$

以矩阵形式表示，我们可以将前两个公式写为

$PQ=0$

其中

$P=\left[ \begin{matrix} π_0^* \qquad π_1^* \qquad π_2^* \qquad... \end{matrix} \right]$ $Q=\left[ \begin{matrix} -\lambda_0 & \lambda_0 & 0 & 0 &...\\ \mu_1 & -(\lambda_1+\mu_1) & \lambda_1 & 0 & ...\\ 0 & \mu_2 & -(\lambda_2+\mu_2) & \lambda_2 & ... \\ ... & ... & ... & ... & ... \end{matrix} \right]$

如果人口的规模有界限那么，这两个矩阵也是有限维的。定义$P(t)$如下：

$P=\left[ \begin{matrix} π_0(t) \qquad π_1(t) \qquad π_2(t) \qquad ... \end{matrix} \right]$

最终可以将式子重写为：

$dP(t)/dt=P(t)Q$

矩阵Q被称为转移速率矩阵，研究生灭过程的第一步就是写出其Q矩阵。

注意到的是Q的对角线上的元素，即$q_{jj}$是离开状态$j$的概率值的负值。另外第$j$列中$q_{j-1,j}$比如($q_{01}$)，表示从状态$j-1$到状态$j$的速率，相应的$q_{j+1,j}$比如($q_{32}$)，表示从状态$j+1$到状态$j$的速率。其他所有的元素均为0。并且每一行所有元素加起来为0。

M/M/1队列

M/M/1队列是对简单的排队系统。这里的a/b/c记号又称为肯达尔记号，字母的意义为：

a部分，即到达过程，具有马尔可夫性；是一个到达间隔时间服从指数分布的泊松过程。
b部分，即离开过程，具有马尔可夫性；是一个离开间隔时间服从指数分布的泊松过程。
c部分，系统中只有一个服务器。

到达时间是泊松过程（Poisson process）；
服务时间是指数分布（exponentially distributed）；
只有一部服务器（server）
队列长度无限制
可加入队列的人数为无限
接受完服务的顾客和到达的顾客相互独立

M/M/1队列是一个生灭马尔可夫过程，其中到达速率$\lambda$和离开速率$\mu$都是状态独立的。

根据M/M/1队列的长期特性可以得到

$π_0^*=1-\frac {\lambda}{\mu}$

其中比率$\lambda/\mu$表示到达速率占服务速率的比例，该比例可以看作系统利用率。这个值单独用$\rho$表示。因此可以得到

$π_0^*=1-\rho$

其直观意义为系统闲置（即$π_0^*$）的概率为（1—系统利用率）。

现在表示处于某一状态$j$的平稳概率为：

$π_j^*=\rho^j(1-\rho)$

对于具体的实例，当数据包达到速率接近链路的容量时，连接该链路的路由器或交换机的队列将无限增长，造成数据包丢失。根据大量数据分析得出，我们应该保证系统利用率不会超过大约70%。一旦界限被超过，要么服务请求被丢弃，要么增加新的服务容量使得利用率降低。

根据Little定理可知，系统中的平均顾客数量=平均等待时间×平均到达率

$平均等待时间=\frac{\frac{\rho}{\lambda}}{(1-\rho)}=\frac{\frac{1}{\mu}}{(1-\rho)}$

这个量在系统利用率接近1时同样将无限增长。

M/M/∞队列：及时响应的服务器

假设一个队列服务提供者为每一个新到达顾客提供一个新的服务器，当有$j$个顾客时，同时也有$j$个服务器。可以得到处于状态$j$的平稳概率为：

$\pi_j^*=\pi_0^*\prod _{i=1}^{j-1}\frac{\lambda}{(i+1)\mu}=\pi_0^*(\frac{\lambda}{\mu})^j\frac{1}{j!}$

利用标准多项式展开$e^x=\sum_{j=0}^∞\frac{x^j}{j!}$。

$\pi_0^*=e^{-\frac{\lambda}{\mu}}$

以及

$\pi_j^*=\pi_0^*\prod_{i=0}^{i-1}\frac{\lambda}{(i+1)\mu}=e^{-\frac{\lambda}{\mu}}(\frac{\lambda}{\mu})^j\frac{1}{j!}$

该式子表明处于状态$j$的平稳概率由参数为$\frac{\lambda}{\mu}$的泊松分布给出。因此，在“无限”服务器情形下，队列中的顾客数量服从泊松分布。我们通过计算参数为$\frac{\lambda}{\mu}$的泊松分布，其平均值来得到队列中顾客的期望数量。

M/M/1/K:有限缓存

假设队列系统只有K-1个缓存。总顾客数量（包括正在被服务的顾客）不能超过K，状态K时到达的顾客都将丢失。意味着这个系统将不会进入状态K+1，K+2，…。

状态转移速率为：

$\lambda_j= \left\{ \begin{aligned} &\lambda \qquad j<K \\ &0 \qquad j≥K \end{aligned} \right.$

并且有$\mu_j=\mu \qquad j=1,2,…,K$

可以推出公式：

$\pi_j^*= \left\{ \begin{aligned} &\pi_0^*(\frac{\lambda}{\mu})^j &\qquad j≤K \\ &0 \qquad &j>K \end{aligned} \right.$ $\pi_0^*= \left\{ \begin{aligned} &\frac{1-\frac{\lambda}{\mu}}{1-(\frac{\lambda}{\mu})^{(k+1)}}(\frac{\lambda}{\mu})^j=\frac{1-\rho}{1-\rho^{(k+1)}}\rho^j &\qquad j≤k \\ &0 \qquad &j>k \end{aligned} \right.$

其意义为$\pi_k^$的直观意义是当系统的缓存大小为k-1时，系统处于“满”的状态。所以$\pi^_k$可以理解为M/M/1/K队列的阻塞概率。

M/D/1:确定服务时间

考虑这么一个派对系统，用户的到达是一个泊松过程，但是服务时间是确定的。用$\mu$表示离开间隔时间，用$\rho=\frac{\lambda}{\mu}$表示利用率，那么只要有$\lambda<\mu$系统就是稳定的。

$系统中的平均顾客数量为=\rho+\frac{\rho^2}{2(1-\rho)}$ $平均响应时间=\frac{1}{\mu}+\frac{\rho}{2\mu(1-\rho)}$

排队网络

开放系统

考虑一个拥有两条服务线的系统，顾客按速率为$\lambda$的泊松过程到达服务线1。在接收完服务线1的服务后，他们加入服务线2前面的队列。我们假设两个服务线都有无穷的等到空间。每个服务线一次服务一个顾客且服务线$i$服务一个顾客需花费速率为$\mu_i(i=1,2)$的指数时间。这样的系统称为串联系统或序贯系统。

服务线1有n个顾客的概率是：

$P(n个顾客在服务线1)=(\frac{\lambda}{\mu_1})^n(1-\frac{\lambda}{\mu_1})$ $P(m个顾客在服务线2)=(\frac{\lambda}{\mu_2})^m(1-\frac{\lambda}{\mu_2})$

如果服务线1和服务线2的顾客数是独立的随机变量，那么就有：

$P_{n,m}=(\frac{\lambda}{\mu_1})^n(1-\frac{\lambda}{\mu_1})(\frac{\lambda}{\mu_2})^m(1-\frac{\lambda}{\mu_2})$

系统中顾客的平均数L为：

$L=\frac{\lambda}{\mu_1-\lambda}+\frac{\lambda}{\mu_2-\lambda}$

因此可以得到顾客在系统中平均的停留时间是：

$W=\frac{L}{\lambda}=\frac{1}{\mu_1-\lambda}+\frac{1}{\mu_2-\lambda}$

如果以$\lambda_j$记顾客到服务线$j$的总到达率，那么$\lambda_j$可以作为：

$\lambda_j=r_j+\sum_{i=1}^k\lambda_iP_{ij}, \qquad i=1,...,k$

泊松分布

日常生活中，大量事件是有固定频率的。

某医院平均每小时出生3个婴儿
某公司平均每10分钟接到1个电话
某超市平均每天销售4包xx牌奶粉
某网站平均每分钟有2次访问

它们的特点就是，我们可以预估这些事件的总数，但是没法知道具体的发生时间。已知平均每小时会来3个顾客，请问下一个小时，会到来几个顾客？

有可能一下子来6个，也有可能一个都不来。这是我们没法知道的。

泊松分布就是描述某段时间内，事件具体的发生概率。

$P(N(t)=n)=\frac{(\lambda t)^ne^{-\lambda t}}{n!}$

概率分布：

$P(X=k)=\frac{\lambda^k}{k!}e^{-\lambda}$

等号的左边，P 表示概率，N表示某种函数关系，t 表示时间，n 表示数量，假如要表示一小时内来3个顾客的概率，就表示为P(N(1) = 3) 。等号的右边，$\lambda$表示事件的频率。

接下来两个小时，一个顾客都不来的概率是0.25%，基本不可能发生。

$P(N(2)=0)=\frac{(3*2)^0e^{-3*2}}{0!}≈0.0025$

接下来一个小时，至少到来两个顾客的概率是80%。

$\begin{aligned} P(N(1)≥2) &=1-P(N(1)=1)=P(N(1)=0)\\ &=1-\frac{(3*1)^1 e^{-3*1}}{1!}-\frac{(3*1)^0 e^{-3*1}}{0!}\\ &1-3e^{-3}-e^{-3}\\ &1-4e^{-3}\\ &≈0.8009\\ \end{aligned}$

泊松分布的示意图

可以看到，在频率附近，事件的发生概率最高，然后向两边对称下降，即变得越大和越小都不太可能。每小时到达3个顾客，这是最可能的结果，到达人数越多或越少，就越不可能。

封闭系统

开放系统中，因为顾客可以进入和离开系统。一个新的顾客决不进入，且现有的顾客决不离开的系统，称为封闭系统。

到达定理：在有$m$个顾客的封闭系统中，到达服务线$j$的到达者所看到的系统的分布于只有$m-1$个顾客的同样的网络系统的平稳分布相同。

原文作者：Sma11_Tim3

原文链接：http://yoursite.com/2020/10/28/计算机网络数学基础/

发表日期：October 28th 2020, 7:57:03 pm

更新日期：March 3rd 2021, 2:32:40 pm

Next Post

MATLAB使用教程(一)
Previous Post

红黑树(Red Black Tree)



缺失模块。
1、请确保node版本大于6.2
2、在博客根目录（注意不是archer根目录）执行以下命令：
npm i hexo-generator-json-content --save
3、在根目录_config.yml里添加配置：

jsonContent:
  meta: false
  pages: false
  posts:
    title: true
    date: true
    path: true
    text: false
    raw: false
    content: false
    slug: false
    updated: false
    comments: false
    link: false
    permalink: false
    excerpt: false
    categories: true
    tags: true