高階多元Markov鏈聯(lián)合穩(wěn)定分布向量的擾動界

鄭 華, 林彩鳳, 祝長華*

(1. 韶關學院數(shù)學與統(tǒng)計學院, 韶關 512005;2. 華南師范大學數(shù)學科學學院, 廣州 510631)

高階多元Markov鏈聯(lián)合穩(wěn)定分布向量的擾動界

鄭 華1, 林彩鳳2, 祝長華1*

(1. 韶關學院數(shù)學與統(tǒng)計學院, 韶關 512005;2. 華南師范大學數(shù)學科學學院, 廣州 510631)

給出了高階多元Markov鏈聯(lián)合穩(wěn)定分布向量的幾個擾動界:結合高階多元Markov鏈概率轉(zhuǎn)移矩陣左、右特征向量的相關性質(zhì),得到高階多元Markov鏈聯(lián)合穩(wěn)定分布向量的擾動界,新的擾動界結果是一階多元Markov鏈聯(lián)合穩(wěn)定分布向量擾動界結果的推廣;利用高階多元Markov鏈概率轉(zhuǎn)移矩陣的特殊性,給出其聯(lián)合穩(wěn)定分布向量可計算形式的擾動界,也是已有一階多元Markov 鏈聯(lián)合穩(wěn)定分布向量相應擾動界結果的推廣;結合Paz不等式,通過分析高階多元Markov鏈聯(lián)合穩(wěn)定分布向量的分量擾動,得到了聯(lián)合穩(wěn)定分布向量基于分量形式的擾動界,便于觀察高階多元Markov 鏈中具體某條鏈某個狀態(tài)的擾動.

高階多元Markov鏈; 聯(lián)合穩(wěn)定分布向量; 擾動界

Markov鏈模型[1]在現(xiàn)實生活中已經(jīng)廣泛地應用于各個領域,如排隊模型[2]、工業(yè)系統(tǒng)[3]和存儲系統(tǒng)[4]等. 在許多實際應用問題中,往往需要對幾類數(shù)據(jù)進行分析,即同時考慮多條Markov鏈,稱多元Markov鏈[5],簡化的多元Markov鏈模型也廣泛應用于各個領域,如市場需求預測[4]、基因布爾網(wǎng)絡的建立[6]等. 進一步地，還需要考慮多步之間的關系和刻畫各條鏈之間、每條鏈內(nèi)部的相互關系, 即高階Markov 鏈[7]以及高階多元Markov鏈[8].

Markov鏈模型中的參數(shù)通過解某些線性優(yōu)化問題[5]或最小二乘問題[9]來估計,不同的估計方法得到不同的模型參數(shù),從而影響模型的穩(wěn)定性,因此需要分析其穩(wěn)定分布向量在轉(zhuǎn)移矩陣受到微小擾動后的變化,即給出擾動界. 關于Markov鏈聯(lián)合穩(wěn)定分布向量的擾動理論結果已經(jīng)有很多[10-14],但關于高階多元Markov鏈聯(lián)合穩(wěn)定分布向量的擾動分析目前還沒有相關的理論結果.

本文將在文獻[5]、[8]、[14]的基礎上給出高階多元Markov鏈聯(lián)合穩(wěn)定分布的3個擾動界結果,包括可計算的擾動界,并得到了分量形式的擾動界.

1 預備知識

本節(jié)回顧高階多元Markov鏈模型[8]的相關概念和性質(zhì). 在后續(xù)討論中,1l表示元素全為1的l維列向量,0l表示元素全為0的l維列向量;對于矩陣M,ρ(M)表示M的譜半徑,M(i)表示矩陣M去掉第i 行后剩下的子矩陣,M*k表示矩陣M的第k列,Mk*表示矩陣M的第k行,Mj表示M去掉第j行和第j列后的順序主子陣.

(1)

其中

(2)

(j=1,2,…,s;r=n,n+1,…).

Xt+1=QXt,

其中

(3)

當i≠j時，有B(ij)=

(4)

此處Q稱為聯(lián)合轉(zhuǎn)移矩陣.

注1 特別地，當n=1時，模型(1)就轉(zhuǎn)化為一階多元Markov鏈模型[5].

引理1[8]如果對于所有的1≤j,k≤s和1≤h≤n都有不可約,則

(i)矩陣Q有一個特征值為1,Q的模最大特征值小于等于1,且存在正向量v和u,使得

(5)

(ii)存在唯一的正向量Π,使得

QΠ=Π,‖Π‖1=ns,

(6)

(7)

且

(8)

(iii)存在唯一正向量X,使得

XTQ=XT,‖X‖1=nm,

(9)

其中

(10)

2 主要結果

首先給出高階多元Markov鏈聯(lián)合穩(wěn)定分布向量的擾動界.

證明 由Perron-Frobenius定理,1是Q的單特征值,因此其對應的特征子空間維數(shù)是1,又X和Π分別是Q對應于1的左、右特征向量,因此存在k和l使得v=kΠ,u=lX (k,l>0),結合式(5)和式(8)有

(11)

vuT=klΠXT=klQΠXT=klQtΠXT.

(kl)2nΠXT,即klΠXT=(kl)2nΠXT,因此kl=1/n,結合式(11)得：

(12)

另一方面，由式(6)和式(9),用數(shù)學歸納法可得

結合式(12)就有

(13)

證明

由式(6)可得

(14)

結合XTΠ=n, 有

則

(15)

由式(9)易得

(16)

在式(14)的兩邊同時左乘B,結合式(15)和式(16),有

注2 定理1得到了高階多元Markov鏈聯(lián)合穩(wěn)定分布向量的擾動界(13). 當n=1時,擾動界(13)即轉(zhuǎn)化為一階多元Markov鏈聯(lián)合穩(wěn)定分布向量的擾動界[14].

擾動界(13)中含有聯(lián)合穩(wěn)定分布向量的信息, 這將導致其難以計算,下面給出高階多元Markov鏈聯(lián)合穩(wěn)定分布向量可計算的擾動界.

定義1[15]設ARn×n,并且可表示為A=sI-B(s>0,B≥0),如果s≥ρ(B),則稱A為M矩陣;如果s>ρ(B),則稱A為非奇異M矩陣.

引理3[15]設A是一個n階奇異不可約的M矩陣,則A的秩為n-1,且A的所有順序主子陣(不包含A自身)都是非奇異的M矩陣.

由引理3易得：

(17)

證明 從式(6)和式(8)可得：

(18)

且

(19)

結合式(18)和式(19)有:

(20)

兩邊取范數(shù)后對右端取最小化即得到了式(17).證畢.

注3 當n=1時，擾動界(17)即轉(zhuǎn)化為一階多元Markov鏈穩(wěn)定分布向量的擾動界[14].

注4 和擾動界(13)相比,擾動界(17)未包含聯(lián)合穩(wěn)定分布向量信息,因此是可計算的擾動界.

接下來推導基于聯(lián)合穩(wěn)定分布向量分量形式的擾動界.

引理5[16](Paz不等式)設zT=(z1,z2,…,zN), 如果對于n維非零向量δ,有δT1N=0,則

定理3 沿用和定理2相同的記號和假設,以下不等式成立:

(21)

(22)

考慮式(22)的第N個元素,即得

進一步得到

(23)

結合式(23),可得

從而式(21)成立.

注5 定理3的意義是:對于給定的某條鏈中的某個狀態(tài),可以由式(21)給出擾動界.

注6 式(21)也是可以計算的擾動界.

3 小結

本文給出了幾個高階多元Markov鏈聯(lián)合穩(wěn)定分布向量的擾動界,其中結合概率轉(zhuǎn)移矩陣特征向量得到了擾動界(13),進一步得到可計算形式的擾動界(17),它們都是已有一階多元Markov鏈相應擾動界結果的推廣,最后還得到了基于分量形式的擾動界(21),極大地豐富了高階多元Markov鏈的理論.

[1]CHINGWK,NGM.Markovchains[M].Berlin:Springer,2006.

[2]CHINGWK.Iterativemethodsforqueuingandmanufacturingsystems[M].Berlin:Springer,2001.

[3]BUZACOTTJA,SHANTHIKUMARJG.Stochasticmo-delsofmanufacturingsystems[M].EnglewoodCliffs:PrenticeHall,1993.

[4]CHINGWK,FUNGE,NGM.Ahigher-orderMarkovchainmodelfortheNewsboy’sproblem[J].JournaloftheOperationsResearchSociety,2003,54:291-298.

[5]CHINGWK,FUNGE,NGM.AmultivariateMarkovchainmodelforcategoricaldatasequencesanditsapplicationsindemandpredictions[J].IMAJournalofManagementMathematics,2002,13:187-199.

[6]CHINGWK,FUNGE,NGM,etal.OnconstructionofstochasticgeneticnetworksbasedonGeneexpressionsequences[J].InternationalJournalofNeuralSystems,2005,15:297-310.

[7]CHINGWK,FUNGE,NGM.Higher-orderMarkovchainmodelsforcategoricaldatasequences[J].NavalResearchLogistics,2004,51:557-574.

[8]CHINGWK,NGM,FUNGE.Higher-ordermultivariateMarkovchainsandtheirapplications[J].LinearAlgebraandItsApplications,2008,428:492-507.

[9]ZHUD,CHINGWK.MultivariateMarkovchainmodelsforproductionplanning[J].InternationalJournalofIntelligentEngineeringInformatics,2011,1:156-173.

[10]CHOG,MEYERC.ComparisonofperturbationboundsforthestationarydistributionofaMarkovchain[J].LinearAlgebraandItsApplications,2001,335:137-150.

[11]FUNDERLICR,MEYERC.PerturbationboundsforthestationarydistributionvectorforanergodicMarkovchain[J].LinearAlgebraandItsApplications,1986,76:1-17.

[12]IPSENI,MEYERC.UniformstabilityforMarkovchains[J].SIAMJournalonMatrixAnalysisandApplications,1994,15:1061-1074.

[13]KIRKLANDS,NEUMANNM,SHADERB.ApplicationsofPaz’sinequalitytoboundsforMarkovchains[J].LinearAlgebraandItsApplications,1998,268:183-196.

[14]LIW,JIANGL,CHINGWK,etal.PerturbationboundsforjointstationarydistributionsofmultivariateMarkovchainsmodels[J].EastAsianJournalonAppliedMathematics,2013,3:1-17.

[15]BERMANA,PLEMMONSRJ.Nonnegativematricesinthemathematicalsciences[M].Philadelphia:SIAM,1994.

[16]SENETAE.Non-negativematricesandMarkovchains[M].NewYork:Springer,1981.

【中文責編：莊曉瓊 英文編校：肖菁】

The Perturbation Bounds of the Joint Stationary Distribution Vector of the High-Order Multivariate Markov Chains

ZHENG Hua1, LIN Caifeng2, ZHU Changhua1*

(1. School of Mathematics and Statistics, Shaoguan University, Shaoguan 512005, China;2. School of Mathematical Sciences, South China Normal University, Guangzhou 510631, China)

The perturbation bounds of the joint stationary distribution vector of the high-order multivariate Markov chains are established. By the properties of the left and right eigenvectors of the probability transition matrix of the high-order multivariate Markov chains, the perturbation bound of the joint stationary distribution vector of the high-order multivariate Markov chains is obtained, which generalizes the results of the existing perturbation bounds of the joint stationary distribution vector of one-order multivariate Markov chains. Then the computational perturbation bound is given by the characteristic of the probability transition matrix of the high-order multivariate Markov chains, which also generalizes the corresponding perturbation bound of the joint stationary distribution vector of one-order multivariate Markov chains. Moreover, considering the perturbation in the item of the joint stationary distri-bution vector of high-order multivariate Markov chains, the perturbation bound of the joint stationary distribution vector based on component form is established by Paz’s inequality, to observe the perturbation of a state in a chain of the high-order multivariate Markov chains.

high-order multivariate Markov chains; joint stationary distribution vector; perturbation bounds

2016-09-08 《華南師范大學學報(自然科學版)》網(wǎng)址：http://journal.scnu.edu.cn/n

國家自然科學基金項目(11601340)；中山大學廣東省計算科學重點實驗室開放基金項目(2016005)；廣東省數(shù)據(jù)科學工程技術研究中心開放基金項目(2016KF11)； 韶關學院科研項目(S201501018)

O241.1

A

1000-5463(2017)03-0092-05

*通訊作者:祝長華,講師,Email:sguzhuchanghua@163.com.