带有伯努利反馈的Geo/Geo/1队列中性能度量的经典和贝叶斯估计
Classical and Bayesian Estimations of Performance Measures in Geo/Geo/1 Queue with Bernoulli Feedback
DOI: 10.12677/AAM.2023.1211453, PDF, HTML, XML, 下载: 106  浏览: 198 
作者: 刘欣颖:南京航空航天大学数学学院,江苏 南京
关键词: 贝叶斯推理伯努利反馈Geo/Geo/1队列UMVUEBayesian Inference Bernoulli Feedback Geo/Geo/1 Queue UMVUEs
摘要: 在本文中,我们从统计角度研究带有伯努利反馈的Geo/Geo/1队列。考虑了经典和贝叶斯框架下的参数和系统性能的估计。我们尝试研究各种排队特征的一致最小方差无偏估计量(UMVUE)和封闭的贝叶斯估计量。此外,我们进行了蒙特卡洛模拟,结果表明所构建的估计器具有大样本收敛特性,可用于近似有限样本中的性能度量,估计器选择没有绝对最优,但封闭形式的贝叶斯估计器在统计实践中更受欢迎,结果为我们在不同系统性能估计场景下最优估计器的选择提供了指导。
Abstract: In this paper, we consider a Geo/Geo/1 queue with Bernoulli feedback from the statistical perspec-tive. The estimations of parameters and system performances under classical and Bayesian frame-works are considered. We attempt to study the uniform minimum-variance unbiased estimators (UMVUEs) and the closed Bayesian estimators for various queueing characteristics. In addition, we conduct Monte Carlo simulations and the results show that the estimators have large sample con-vergence characteristics and can be used to approximate performance measures in finite samples. The estimator selection is not absolute optimal, but the closed form Bayesian estimator is more popular in statistical practice. The results provide guidance for us to choose the optimal estimator in different application scenarios.
文章引用:刘欣颖. 带有伯努利反馈的Geo/Geo/1队列中性能度量的经典和贝叶斯估计[J]. 应用数学进展, 2023, 12(11): 4622-4631. https://doi.org/10.12677/AAM.2023.1211453

1. 介绍

排队论在许多现实情况的设计和分析中起着至关重要的作用。它为分析人员提供了评估排队现象并做出适当决策的工具。对于电话交换系统和计算机网络,离散时间排队模型比连续时间排队模型更适合模拟消息传输过程。实际上,在许多通信系统中,时间轴被分成相等的间隔,称为时隙。当信息(客户)到达时,它们被存储在缓冲区中。信息的服务(转换)仅在时隙边界开始。

当系统受到外部干扰时,错误的消息会被重新发送。考虑到上述情况,反馈可以作为一种调度机制。Takacs [1] 首先研究了瞬时伯努利反馈队列。Atencia和Moreno [2] 首先在离散时间系统上研究了这种机制。

之前的大量研究讨论了Geo/Geo/1队列的平衡状态和性能指标 [3] [4] [5] [6] 。队列的关键性能被表示为系统参数的函数。有了这些结果,系统管理员就可以有效地设计系统来合理配置资源并获得预期收入。而对于客户来说,利用观察到的信息来估计未知参数可以帮助他们做出最优决策。从客户的角度来看,对未知参数或排队性能度量的估计是有意义的。所以在本文中,我们研究经典框架和贝叶斯框架下的排队系统性能的估计。

Clarke [7] 首先从频率理论的角度对M/M/1队列进行统计推断,给出了服务速率、到达速率的最大似然估计量(MLE)。Basawa和Prabhu [8] 推导了GI/G/1队列中系统参数的MLE。Basawa等人 [9] 利用等待时间数据来研究单个服务器队列的MLE。McGrath和Singpurwalla [10] 首先应用贝叶斯方法进行排队统计推断。从那时起,出现了大量关于排队系统的贝叶斯推理的研究。近几十年来,Chowdhury和Mukherjee [11] 使用Beta-Stacy分布作为先验推导了贝叶斯估计量。Deepthi和Jose [12] 在M/M/1队列中使用Mckay双变量Gamma先验进行贝叶斯估计。Jose和Deepthi [13] 使用贝叶斯过程分析了具有可选重试服务的M/PH/1排队系统。于等人 [14] 为M/M/1队列中的各种性能度量构建了UMVUE和封闭式贝叶斯估计。然而,与连续时间排队模型不同,离散时间排队模型中顾客的到达和离开可能同时发生。所以后者的分析变得更加复杂。此外,我们注意到很少有工作从统计角度涵盖离散时间排队模型,这促使我们关注这个主题。

本文的结构如下:在第二节中,我们简要介绍了带有伯努利反馈的Geo/Geo/1队列,并推导了重要的系统性能度量。在第三节中,我们使用Lehmann-Scheffé定理来构造一些重要系统性能的UMVUE。在第四节中,我们使用信息先验和无信息先验进行贝叶斯推理。我们得到一些性能指标和系统状态的后验分布的封闭式贝叶斯估计器。在第五节中,我们使用均方误差(MSE)标准进行蒙特卡洛模拟来评估这些估计量。在第六节中,我们对本文进行总结并提出不足之处和之后的可能研究方向。

2. 模型说明

在本文中,我们考虑具有伯努利反馈的早到Geo/Geo/1队列。假设客户按照伯努利过程到达服务器,并且仅在时隙开始时到达,到达概率为 p ( 0 < p < 1 ) 。客户服务时间相互独立,服务速率服从参数为 μ ( 0 < μ < 1 ) 的几何分布,并且客户离开仅发生在时段结束时。到达后,每个客户以概率 θ 成功完成服务并离开系统,或以概率 1 θ 服务失败回到队列末尾。到达时间和服务时间是相互独立的。服务器遵循先到先服务(FCFS)规则。用 L n ( n = 0 , 1 , 2 , ) 表示n时刻系统中的客户数量,令 p ¯ = 1 p μ 1 = μ θ μ ¯ 1 = 1 μ 1 ,那么我们有

P { L n + 1 = 1 | L n = 0 } = p μ ¯ 1 , P { L n + 1 = 0 | L n = 0 } = p ¯ + p μ 1 = 1 p μ ¯ 1 ,

k 1

P { L n + 1 = k + 1 | L n = k } = p μ ¯ 1 , P { L n + 1 = k 1 | L n = k } = p ¯ μ 1 , P { L n + 1 = k | L n = k } = μ 1 p + μ ¯ 1 p ¯ = 1 p μ ¯ 1 p ¯ μ 1 .

{ L n , n 0 } 的转移概率矩阵是

P = ( 1 p μ ¯ 1 p μ ¯ 1 p ¯ μ 1 1 p μ ¯ 1 p ¯ μ 1 p μ ¯ 1 p ¯ μ 1 1 p μ ¯ 1 p ¯ μ 1 p μ ¯ 1 ) .

{ L n , n 0 } 是一个离散时间的生灭链。我们引入符号 ρ = p μ 1 α = p μ ¯ 1 p ¯ μ 1 。当 ρ < 1 ,我们有

k = 1 p μ ¯ 1 k p ¯ μ 1 k = k = 1 α k = α 1 α . (1)

马尔可夫过程 { L n , n 0 } 是正常返的,其平稳分布为

π k = P { L = k } = lim n P { L n = k } = ( 1 α ) α k , k 0 , (2)

其中L表示平稳状态下系统中的客户数。(2)表明我们得到一个修正的参数为 1 α 的几何分布。

根据(2),我们可以找到带有伯努利反馈的Geo/Geo/1队列的一些重要的性能度量。例如,系统中客户的平均数量由下式给出

L s = k = 0 k π k = α ( 1 α ) k = 0 k α k 1 = α 1 α . (3)

队列中客户的平均数量由下式给出

L q = k = 1 ( k 1 ) π k = α 2 ( 1 α ) k = 1 ( k 1 ) α k 2 = α 2 1 α . (4)

我们把服务器被占用的概率定义为繁忙概率 ρ 0 ,可写为

ρ 0 = 1 π 0 = 1 ( 1 α ) = α . (5)

3. 性能度量的UMVUE

我们使用Lehmann-Scheffé定理构建上述三个性能指标的一致最小方差无偏估计量(UMVUE)。 X 1 , X 2 , , X n 是来自(2)的独立同分布的随机变量。由于几何分布是一种单参数分布, Y = i = 1 n X i 对于估计 α 是充分的。得到Y之后,可以通过生成相应的无偏估计量来获得性能度量的UMVUE,其形式为 h ( Y )

其中h为Borel函数。我们接下来求Y的分布

P ( Y = y ) = ( C n 1 + C n 2 + ... + C n y ) ( 1 α ) n α y = C n + y 1 y ( 1 α ) n α y , (6)

这与负二项分布一致。

因此,系统中的平均客户数 L s 的无偏估计量 h 1 ( Y ) 应该满足

E α [ h 1 ( Y ) ] = y = 0 h 1 ( y ) C n + y 1 y ( 1 α ) n α y = L s = α 1 α . (7)

通过一些数学运算,将(7)式右边展开为级数形式,有

y = 0 h 1 ( y ) C n + y 1 y α y 1 = ( 1 α ) ( n + 1 ) = i = 0 ( 1 ) i C i + n n ( α ) i = y = 1 C n + y 1 n α y 1 . (8)

比较在(8)式两边 α y 1 的系数,我们有

h 1 ( Y ) = L ^ s = { C Y + n 1 n C Y + n 1 Y Y = 1 , 2 , 0 Y = 0. . (9)

按照同样的思路,我们可以很容易得到队列中的平均顾客数 L q 和繁忙概率 ρ 0 的UMVUE。如果构建Y的Borel函数 h 2 ( Y ) h 3 ( Y ) ,也就是 L q ρ 0 的无偏估计量,那么 h 2 ( Y ) h 3 ( Y ) 是这些量的UMVUE。可以得到

E α [ h 2 ( Y ) ] = y = 0 h 2 ( y ) C n + y 1 y ( 1 α ) n α y = L q = α 2 1 α , (10)

E α [ h 3 ( Y ) ] = y = 0 h 3 ( y ) C n + y 1 y ( 1 α ) n α y = ρ 0 = α . (11)

类似地,由(10)我们有

y = 0 h 2 ( y ) C n + y 1 y α y 2 = ( 1 α ) ( n + 1 ) = i = 0 ( 1 ) i C i + n n ( α ) i = y = 2 C y + n 2 n α y 2 . (12)

因此,比较(12)中 α y 2 前面的系数可得

h 2 ( Y ) = L ^ q = { C Y + n 2 n C Y + n 1 Y Y = 2 , 3 , 0 , Y = 0 , 1 . (13)

由(11)我们有

y = 0 h 3 ( y ) C n + y 1 y α y 1 = ( 1 α ) n = i = 0 ( 1 ) i C i + n 1 n 1 ( α ) i = y = 1 C y + n 2 n 1 α y 1 . (14)

比较(14)中 α y 1 前面的系数可得

h 3 ( Y ) = ρ ^ 0 = { C Y + n 2 n 1 C Y + n 1 Y Y = 1 , 2 , 0 , Y = 0 . (15)

4. 系统性能的贝叶斯估计

在第三节中,我们推导了 L s L q ρ 0 的UMVUE。由于UMVUE的表达式涉及阶乘运算,增加样本量n会大大增加计算复杂度。这使得进行经典统计估计变得困难。因此,我们在本节中讨论贝叶斯方法,该方法用于以简单的方式估计这些性能指标。

4.1. 有先验信息的贝叶斯估计

在贝叶斯统计中,如果后验分布和先验分布属于同一族,则先验分布和后验分布称为共轭分布,先验分布称为似然函数的共轭先验。共轭先验的优点主要在于代数上的方便,可以直接给出后验分布的闭合形式。共轭先验可以被认为是信息量最大的,因为它最小化了参数推断的观察权重。共轭先验还有助于直观地了解似然函数如何更新先验分布。因此,在本节中,我们考虑超参数为a和b的Beta分布作为 α 的自然共轭先验分布,

π C ( α ) = 1 B ( a , b ) α a 1 ( 1 α ) b 1 , a , b > 0 , α > 0 , (16)

使用样本值 x = ( x 1 , x 2 , , x n ) α 的后验分布由贝叶斯定理可以推导出来,即

p C ( α | x 1 , x 2 , , x n ) = α a + n x ¯ 1 ( 1 α ) n + b 1 B ( a + n x ¯ , n + b ) , α > 0. (17)

性能指标的贝叶斯估计包括平均队列长度 L ^ q BC ,平均系统大小 L ^ s BC 和繁忙概率 ρ ^ 0 BC ,由下式给出

L ^ s BC = 0 1 α ( 1 α ) B ( a + n x ¯ , n + b ) α a + n x ¯ 1 ( 1 α ) n + b 1 d α = B ( a + n x ¯ + 1 , n + b 1 ) B ( a + n x ¯ , n + b ) , (18)

L ^ q BC = 0 1 α 2 ( 1 α ) B ( a + n x ¯ , n + b ) α a + n x ¯ 1 ( 1 α ) n + b 1 d α = B ( a + n x ¯ + 2 , n + b 1 ) B ( a + n x ¯ , n + b ) , (19)

ρ ^ 0 BC = 0 1 α B ( a + n x ¯ , n + b ) α a + n x ¯ 1 ( 1 α ) n + b 1 d α = B ( a + n x ¯ + 1 , n + b ) B ( a + n x ¯ , n + b ) . (20)

另外,得到系统规模的样本数据 { x 1 , x 2 , , x n } 后,我们可以通过(21)利用贝叶斯方法来预测任意给定时刻队列中的顾客数量

Pr C { L = k | x 1 , x 2 , , x n } = 0 1 π k p C ( α | x 1 , x 2 , , x n ) d α = 0 1 α a + n x ¯ + k 1 ( 1 α ) n + b d α B ( a + n x ¯ , n + b ) = B ( a + n x ¯ + k , n + b + 1 ) B ( a + n x ¯ , n + b ) . (21)

4.2. 具有无信息先验的贝叶斯估计

在一些复杂问题中,反映主观意见的先验并不存在,将主观意见纳入分析与尽可能做出科学推论的目标相矛盾。在贝叶斯实践中,人们通常对采用无信息先验感兴趣,本章节中我们使用Jeffreys先验,定义为

π J ( α ) I ( α ) , (22)

其中

I ( α ) = E [ 2 log q ( X | α ) α 2 ] = E [ 2 ( X log ( 1 α ) + k log α ) α 2 ] = E [ X α 2 + 1 ( 1 α ) 2 ] = α 1 2 ( 1 α ) 1 . (23)

因此,Jeffreys先验由下式给出

π J ( α ) α 1 2 ( 1 α ) 1 , α > 0. (24)

通过样本值 x = ( x 1 , x 2 , , x n ) α 的先验可以得到 α 的后验分布

p J ( α | x 1 , x 2 , , x n ) = ( 1 α ) n 1 α n x ¯ 1 2 0 1 ( 1 α ) n 1 α n x ¯ 1 2 d α , α > 0. (25)

我们可以进一步推导性能指标的估计量,包括平均队列长度 L ^ q BJ ,平均系统大小 L ^ s BJ 和繁忙概率 ρ ^ 0 BJ

L ^ s BJ = 0 1 α ( 1 α ) B ( n x ¯ + 1 2 , n ) α n x ¯ 1 2 ( 1 α ) n 1 d α = B ( n x ¯ + 3 2 , n 1 ) B ( n x ¯ + 1 2 , n ) , (26)

L ^ q BJ = 0 1 α 2 ( 1 α ) B ( n x ¯ + 1 2 , n ) α n x ¯ 1 2 ( 1 α ) n 1 d α = B ( n x ¯ + 5 2 , n 1 ) B ( n x ¯ + 1 2 , n ) , (27)

ρ ^ 0 BJ = 0 1 α B ( n x ¯ + 1 2 , n ) α n x ¯ 1 2 ( 1 α ) n 1 d α = B ( n x ¯ + 3 2 , n ) B ( n x ¯ + 1 2 , n ) . (28)

另外,根据我们之前对先验的讨论,任意时刻系统中客户数量的后验预测分布如下

Pr J { L = k | x 1 , x 2 , , x n } = 0 1 π k p J ( α | x 1 , x 2 , , x n ) d α = 0 1 α n x ¯ + k 1 2 ( 1 α ) n d α B ( n x ¯ + 1 2 , n ) = B ( n x ¯ + k + 1 2 , n + 1 ) B ( n x ¯ + 1 2 , n ) . (29)

5. 数值模拟

在本节中,我们进行蒙特卡洛模拟以比较不同排队性能度量的UMVUE和贝叶斯估计。首先构造一个与Geo/Geo/1排队系统相似的概率模型或随机过程,利用MATLAB进行不同分布下的随机抽样试验来模拟系统的随机特性,基于大数定理,利用抽样后样本发生的频率来估计概率,最终求得近似解,随着样本数的增多,近似解逼近精确解。在MATLAB中利用概率分布进行抽样并估计的过程总结如下。

设置 α = 0.75 ,超参数 a = 2 b = 1.5 。对于不同的样本量 n = 20 , 25 , , 135 , 140 ,取重复次数 m = 1000

创建一个循环来模拟 L s L q ρ 0 以及相应的MSE。设 i = 1 : m ,生成遵循(2)的随机数后,使用(9),(13)和(15)得到 L s L q ρ 0 的UMVUE的估计结果。使用(3)~(5)中给出的 L s L q ρ 0 的真实值得到MSE的模拟结果,即

MSE ( L ^ s ) = 1 m i = 1 m ( L ^ s i L s ) 2 , (30)

MSE ( L ^ q ) = 1 m i = 1 m ( L ^ q i L q ) 2 , (31)

MSE ( ρ ^ 0 ) = 1 m i = 1 m ( ρ ^ 0 i ρ 0 ) 2 . (32)

与上面提到的数值模拟程序类似,我们利用(18)~(20)来计算Beta先验分布下贝叶斯估计量的模拟结果,并使用真实值来计算MSE的模拟结果。之后利用(26)~(28)来计算根据Jeffreys先验分布下的模拟结果。

Figure 1. The estimations of system length L s and the corresponding MSEs

图1. 系统大小 L s 的估计值以及相应的MSEs

Figure 2. The estimations of queue length L q and the corresponding MSEs

图2. 队列长度 L q 的估计值以及相应MSEs

Figure 3. The estimations of busy probability ρ 0 and the corresponding MSEs

图3. 繁忙概率 ρ 0 的估计值以及相应MSEs

上述数值模拟结果整理如图1~3所示。随着n增大,这些估计量的MSEs会减少。这些估计器均具有大样本收敛特性,可用于近似有限样本中性能度量的行为。UMVUE是 L s L q ρ 0 的最优无偏估计量,不会始终高估或低估真实价值。但对于贝叶斯估计来说,情况并非如此。

对于贝叶斯估计来说,不同先验下的结果和性质也不同。对于 ρ 0 ,Jeffreys先验提供的MSE低于共轭先验。该估计器具有较好的性能,并且可以使用较小的样本量给出相对准确的估计。对于系统大小 L s 和队列长度 L q ,这两个贝叶斯估计量的MSE非常接近。共轭先验提供了更好的点估计器,特别是当样本量较小时。这可能与共轭分布的优良性质以及先验分布中超参数的选择有关。正确选择超参数通常可以极大地提高贝叶斯估计器的性能

另外,在获得参数的后验分布后,我们使用(21)和(29)生成随机时刻系统中客户数量的后验预测分布。表1列出了有信息先验和无信息先验分布下的数值模拟结果。

Table 1. Predictive distribution of the system size at arbitrary epoch under steady state

表1. 稳态下系统规模的预测分布

6. 结论

我们对Geo/Geo/1排队模型进行统计推断。引入经典方法和贝叶斯方法来推导出性能度量的估计量。我们首先推导出UMVUE,然后通过计算后验分布的平均值,推导出不同先验信息下的贝叶斯估计量。

蒙特卡洛模拟结果表明,没有一个估计器绝对优于另一个估计器。当样本量较大时,这些估计量之间的MSE会减小,其间的差异性变得不显着。

由于计算组合时经常使用阶乘运算,估计器的计算复杂度随着样本量的增加而显着增加,因此封闭式贝叶斯估计器在统计实践中更受欢迎。

本文基于参数 α 进行分析,对于到达速率 p ,服务率速 μ θ 没有单独进行分析。未来可以在这方面进行研究。且由于参数 p μ 之间存在制约关系,可以寻求二元先验并进行相应的统计推断。

参考文献

[1] Takács, L. (1963) A Single-Server Queue with Feedback. Bell System Technical Journal, 42, 505-519.
https://doi.org/10.1002/j.1538-7305.1963.tb00510.x
[2] Atencia, I. and Moreno, P. (2004) Discrete-Time Geo[X]/GH/1 Retrial Queue with Bernoulli Feedback. Computers and Mathematics with Applications, 47, 1273-1294.
https://doi.org/10.1016/S0898-1221(04)90122-8
[3] Ata, B., Glynn, P.W. and Peng, X. (2017) An Equilibrium Analysis of a Discrete-Time Markovian Queue with Endogenous Abandonments. Queueing System, 86, 141-212.
https://doi.org/10.1007/s11134-017-9521-6
[4] Ma, Z., Wang, P. and Yue, W. (2017) Performance Analysis and Optimization of a Pseudo-Fault Geo/Geo/1 Repairable Queueing System with N-Policy, Setup Time and Multiple Work-ing Vacations. Journal of Industrial and Management Optimization, 13, 1467-1481.
https://doi.org/10.3934/jimo.2017002
[5] Goswami, V. and Panda, G. (2019) Optimal Information Policy in Dis-crete-Time Queues with Strategic Customers. Journal of Industrial and Management Optimization, 15, 689-703.
https://doi.org/10.3934/jimo.2018065
[6] Sudhesh, R. and Priya, R.S. (2019) An Analysis of Discrete-Time Geo/Geo/1 Queue with Feedback, Repair and Disaster. International Journal of Operational Research, 35, 37-53.
https://doi.org/10.1504/IJOR.2019.099542
[7] Clarke, B.A. (1957) Maximum Likelihood Estimates in a Simple Queue. Annals of Mathematical Statistics, 28, 1036-1040.
https://doi.org/10.1214/aoms/1177706808
[8] Basawa, I.V. and Prabhu, N.U. (1981) Estimation in Single Server Queues. Naval Research Logistics, 28, 475-487.
https://doi.org/10.1002/nav.3800280311
[9] Basawa, I.V., Bhat, U.N. and Lund, R. (1996) Maximum Likelihood Estimation for Single Server Queues from Waiting Time Data. Queueing Systems, 24, 155-167.
https://doi.org/10.1007/BF01149084
[10] McGrath, M.F. and Singpurwalla, N.D. (1987) A Subjective Bayesian Approach to the theory of Queues II-Inference and Information in M/M/1 Queues. Queueing Systems, 1, 335-353.
https://doi.org/10.1007/BF01150669
[11] Chowdhury, S. and Mukherjee, S.P. (2016) Bayes Estimation in M/M/1 Queues with Bivariate Prior. Journal of Statistics and Management Systems, 19, 681-699.
https://doi.org/10.1080/09720510.2015.1130905
[12] Deepthi, V. and Jose, J.K. (2021) Bayesian Inference on M/M/1 Queue under Asymmetric Loss Function Using Markov Chain Monte Carlo Method. Journal of Statistics and Management Systems, 24, 1003-1023.
https://doi.org/10.1080/09720510.2020.1794529
[13] Jose, J.K. and Deepthi, V. (2023) M/PH/1 Queueing Model with Re-Servicing. Communications in Statistics-Simulation and Computation, 52, 2865-2885.
https://doi.org/10.1080/03610918.2021.1921209
[14] Yu, M., Tang, J. and Tang, Y. (2023) UMVUEs and Bayes Estimators for Various Performance Measures on a Poisson Queue with Discouraged Arrivals. Communications in Sta-tistics-Theory and Methods, 52, 4468-4483.
https://doi.org/10.1080/03610926.2021.1995430