Markov鏈中的轉(zhuǎn)移過程張量與超隨機(jī)張量

朱桂滿，趙金玲，徐 爾，湯國斌

（北京科技大學(xué) 數(shù)理學(xué)院，北京100083）

0 引 言

2005年，Qi Liqun［1］首次提出了張量特征值與張量特征向量的概念，引起了廣泛的關(guān)注．人們相繼提出了許多張量的相關(guān)概念和性質(zhì)，其中對(duì)于特殊張量的研究也十分活躍．Qi Liqun［1］給出了高階張量對(duì)稱的定義，研究了超對(duì)稱張量的性質(zhì)，并 定 義 了 張 量 的 秩［2］．2011 年，Chang 又補(bǔ)充了弱對(duì)稱張量［3］和本原張量［4］的定義．同年，Yang Qingzhi等定義了隨機(jī)張量［5］并給出了相關(guān)性質(zhì)．考慮到隨機(jī)矩陣是隨機(jī)數(shù)學(xué)中研究Markov鏈的有力工具，但在Markov鏈的研究中，n 步轉(zhuǎn)移概率矩陣中存儲(chǔ)的信息僅表示狀態(tài)i 經(jīng)n 步到達(dá)狀態(tài)j 的總概率，而不能從中直接讀出途中經(jīng)過各狀態(tài)的概率．本文提出通過張量來存儲(chǔ)n 步轉(zhuǎn)移過程中各種可能情況的概率．依托于Markov鏈，類似于雙隨機(jī)矩陣的結(jié)構(gòu)提出了超隨機(jī)張量，并討論了此類特殊張量的一些性質(zhì)．

所謂張量，即是高維數(shù)組．例如，向量可以看成一階張量，矩陣可以看成二階張量．

設(shè)A＝（ai1…im），其中ai1…im∈R（ij＝1，…，n；j＝1，…，m），則A 稱為m 階n維實(shí)張量，記為A∈R［m，n］，A 中有nm個(gè)元素，若ai1…im≥0，則稱A 為非負(fù)張量［6］．設(shè)x＝（x1，…，xn）為n維向量，記x［m－1］＝（xm－11，…，xm－1n）T．若存在（λ，x）∈C×（Cn＼｛0｝），使得

其中

則稱λ為張量A 的特征值，x為特征值λ 對(duì)應(yīng)的特征向量［6］．若λ與x 分別為實(shí)數(shù)和實(shí)向量，則稱λ為張量A 的H－ 特征值，否則稱λ為A 的N－ 特征值．張量A的譜半徑為ρ（A）＝max｛｜λ｜∶λ為A 的特征值｝［7］．張量A 被稱為超對(duì)稱［1］的，當(dāng)且僅當(dāng)ai1…im＝aδ（i1…im）對(duì)所有的σ∈δm成立，這里δm為m 個(gè)指標(biāo)的任意排序所組成的集合．

引理1［8］（Chapman－Kolmogorov 方 程） 設(shè)

Markov鏈的狀態(tài)空間為E，i，j，k∈E，不作齊次性假定，那么當(dāng)時(shí)刻r＜s＜t時(shí)，有pij（r，t）＝∑k∈Epik（r，s）pkj（s，t）．對(duì)齊次性馬氏鏈，上述方程具有更簡明的形式，

該引理中的兩個(gè)等式即為求Markov鏈多步轉(zhuǎn)移概率的Chapman－Kolmogorov 方程．其中pij（s，t）＝P（X（t）＝j(luò)｜X（s）＝i），表示已知s時(shí)刻處于狀態(tài)i，t時(shí)刻將到達(dá)狀態(tài)j的轉(zhuǎn)移概率，而則表示齊次馬氏鏈已知時(shí)刻k處于狀態(tài)i，經(jīng)n步轉(zhuǎn)移后到達(dá)狀態(tài)j 的n 步轉(zhuǎn)移概率．

定義1［1］設(shè)m 為δi1…im的 下 標(biāo) 指 數(shù)，當(dāng)i1，…，im＝1，…，n時(shí)，

稱為一個(gè)m 階n 維的單位張量，記為I．為了簡化計(jì)算，定義det（I）＝1．

1 Markov鏈中的隨機(jī)張量與超隨機(jī)張量

1．1 Markov鏈中的轉(zhuǎn)移過程張量

對(duì)Markov鏈，設(shè)狀態(tài)集為E，時(shí)刻r＜s＜t，對(duì)于i，j，k ∈E，記pikj（r，s，t）＝P（X（t）＝j(luò)，X（s）＝k｜X（r）＝i），表示已知r時(shí)刻處于狀態(tài)i，途中s時(shí)刻經(jīng)狀態(tài)k，最終t時(shí)刻到達(dá)狀態(tài)j 的概率．若為齊次馬氏鏈，則轉(zhuǎn)移概率與絕對(duì)時(shí)間無關(guān)．記p（n＋m）ikj＝P（X（l＋n＋m）＝j(luò)，X（l＋n）＝k｜X（l）＝i），表示已知當(dāng)前處于狀態(tài)i，n個(gè)時(shí)間單位后到達(dá)狀態(tài)k，n＋m 個(gè)時(shí)間單位后轉(zhuǎn)移到狀態(tài)j的概率．稱這里的pikj（r，s，t）和p（n＋m）ikj為轉(zhuǎn)移過程概率．

由Markov過程的基本理論，易知轉(zhuǎn)移過程概率滿足如下結(jié)論：

定理1 設(shè)Markov鏈的狀態(tài)空間為E，i，j，k∈E，不作齊次性假定，那么當(dāng)時(shí)刻r ＜s＜t時(shí)，轉(zhuǎn) 移 過 程 概 率 滿 足pikj（r，s，t）＝pik（r，s）pkj（s，t）．對(duì)齊次馬氏鏈，則有p（n＋m）ikj＝p（n）ikp（m）kj．

為簡便計(jì)算，下面考察齊次馬氏鏈．設(shè)其狀態(tài)集 為E ＝｛1，2，…，n｝，一 步 轉(zhuǎn) 移 概 率pij＝P（X（l＋1）＝j(luò)｜（l）＝i），則從狀態(tài)i1依次經(jīng)過i2，…，im－1到達(dá)狀態(tài)（共m－1步）的概率ai1i2…im＝pi1i2·pi2i3…pim－1im，可視為轉(zhuǎn)移過程概率．以這樣的ai1i2…im（i1，…，im∈E）為元素，即構(gòu)成一個(gè)m階n維正方張量A ＝（ai1…im），稱為轉(zhuǎn)移過程張量．

1．2 超隨機(jī)張量的定義

隨機(jī)張量作為一種特殊張量，定義如下：

定義2［5］設(shè)A為一m 階n維非負(fù)張量，若滿足則稱A 為m 階n

維隨機(jī)張量．

例1 設(shè)齊次馬氏鏈狀態(tài)集有限，如E＝｛1，2，3｝．若以P＝（pij），｛i，j∈（1，2，3）｝表示一步轉(zhuǎn)移概率矩陣，三階張量（1，2，3）｝表示兩步轉(zhuǎn)移過程概率．這里，ai1i2i3＝

情況1 假設(shè)

易驗(yàn)證，當(dāng)i1＝1，2，3 時(shí)，當(dāng)i2＝1 時(shí)，當(dāng)i2＝2 時(shí)，；當(dāng)i2＝3 時(shí)，

情況2 假設(shè)

易驗(yàn)證，當(dāng)i1＝1，2，3 時(shí)，當(dāng)i2＝1，2，3 時(shí)，當(dāng)i3＝1，2，3 時(shí)，

在這兩種情況下，A 均為隨機(jī)張量，但情況2中的隨機(jī)張量顯然更為特殊．由此，引入超隨機(jī)張量的定義．

定理2 設(shè)齊次Markov鏈的狀態(tài)集E ＝｛1，2，…，n｝，假設(shè)其一步轉(zhuǎn)移概率矩陣為n×n 雙隨機(jī)矩陣，即行和、列和均為1，則m－1步轉(zhuǎn)移過程張量為m 階n 維超隨機(jī)張量．

證明：（數(shù)學(xué)歸納法）

作為領(lǐng)袖的蔣介石對(duì)于國民黨意識(shí)形態(tài)建設(shè)的影響是黨內(nèi)其他人無法代替的，由此領(lǐng)袖的個(gè)性與局限亦會(huì)滲透于意識(shí)形態(tài)的表述之中。時(shí)勢(shì)與人物是相互塑造的，蔣介石對(duì)國民黨意識(shí)形態(tài)建構(gòu)既受制于其本身的局限性，也無法突破外在困境。

即要證，

首先，設(shè)齊次Markov鏈的狀態(tài)集E ＝｛1，2，3｝，假設(shè)其一步轉(zhuǎn)移概率矩陣為3×3 雙隨機(jī)矩陣，P ＝（pij），｛i，j∈（1，2，3）｝，即其行和、列和均為1，這里pij指狀態(tài)i經(jīng)一步到達(dá)狀態(tài)j 的概率．下證2 步 轉(zhuǎn) 移 過 程 張 量，即3 階3 維 張 量A ＝

（ai1i2i3），ai1i2i3＝pi1i2·pi2i3，｛i1，i2，i3∈（1，2，3）｝

是超隨機(jī)張量，這里ai1i2i3指狀態(tài)i1經(jīng)i2到達(dá)i3的概率．

第一步：固定i1指標(biāo)，令i1＝1（當(dāng)i1＝2，i1＝3時(shí)同理）．

根據(jù)Chapman－Kolmogorov方程得

由P 的行和為1得

第三步：固定i3指標(biāo)，令i3＝1（當(dāng)i3＝2，i3＝3時(shí)同理）．由P 的列和為1得

可知A ＝（ai1i2i3）為超隨機(jī)張量．類似可得，當(dāng)齊次馬氏鏈狀態(tài)集為E ＝｛1，2，…，n｝時(shí)，相應(yīng)地轉(zhuǎn)移過程張量A 為3階n維時(shí)，即當(dāng)階數(shù)k＝3時(shí)，命題成立．

當(dāng)k＝m，j＝1時(shí)，

當(dāng)k＝m，j＝m 時(shí)，

證畢．

進(jìn)一步，這里是借助馬氏鏈的狀態(tài)轉(zhuǎn)移過程定義了張量，實(shí)際上是由P（矩陣）所生成的，結(jié)果表明：當(dāng)馬氏鏈的一步轉(zhuǎn)移概率矩陣為雙隨機(jī)矩陣時(shí)，其m－1步轉(zhuǎn)移過程張量為超隨機(jī)張量．當(dāng)然，另一方面也不難知道，超對(duì)稱的隨機(jī)張量都是超隨機(jī)張量．下面，將進(jìn)一步探討什么樣的張量會(huì)是超隨機(jī)張量．

定理3 假設(shè)m 階n 維張量A ＝（ai1i2…im）是由n維向量x＝（x1，…，xn）T生成的，即ai1i2…im＝xi1·xi2…xim．若x1＝x2＝…＝xn＝n1－mm，則A為超隨機(jī)張量．

2 超隨機(jī)張量的幾個(gè)簡單性質(zhì)

文獻(xiàn)［9－16］研究了許多關(guān)于特殊張量的性質(zhì)．由于超隨機(jī)張量是一類特殊的隨機(jī)張量，故而它也滿足隨機(jī)張量的性質(zhì)［5］．易見，超隨機(jī)張量有如下性質(zhì)：

性質(zhì)1 若A 為m 階n 維超隨機(jī)張量，則有：

1）λ＝1為A的一個(gè)特征值，e＝［1…1］T為A的對(duì)應(yīng)于λ＝1的一個(gè)特征向量．

2）ρ（A）＝1，這里ρ（A）為A 的譜半徑，即特征值的最大值．

3）若A 為不可約的，則λ＝1為單重特征值．

該性質(zhì)表明，超隨機(jī)張量具有隨機(jī)張量的性質(zhì)．當(dāng)然，作為一種特殊的隨機(jī)張量，超隨機(jī)張量具有更好的性質(zhì)．

性質(zhì)2 若A 為m 階n 維超隨機(jī)張量，則有：

可知，

由于A 為超隨機(jī)張量，故而

［1］Qi Liqun．Eigenvalues of a real supersymmatric tensor［J］．Journal of Symbolic Computation，2005，40（1）：1302－1324．

［2］Qi Liqun．Rank and eigenvalues of a surpersymmetric tensors，the multivariate homogeneous polynomial and the algebraic hypersurface it defines［J］．Journal of Symbolic Computation，2006，41（1）：1309－1327．

［3］Chang K C，Pearson K，Zhang T．On eigenvalue problems of real symmetric tensors［J］．J Math．Anal．Appl．，2009，350（1）：416－422．

［4］Chang K C，Pearson K，Zhang T．Primitivity，the convergence of the NQZ method，and the largest eigenvalue for nonnegative tensors［J］．SIAM J．Matrix Anal．Appl．，2011，32（1）：806－819．

［5］Yang Qingzhi，Yang Yuning．Further results for perron－frobenius theorem for nonnegative ten－sors 2［J］．Society for Industrial and Applied Mathematrics，2011，32（4）：1236－1250．

［6］Chang K C，Pearson K，Zhang T．Perron－frobenius theorem for nonnegative tensor［J］．Commun．Math．Sci．，2008，6（2）：507－520．

［7］Yang Yuning，Yang Qingzhi．Further results for perron－frobenius theorem for nonnegative ten－sors［J］．Society for Industrial and Applied Mathematrics，2010，31（5）：2517－2530．

［8］陸大金．隨機(jī)過程及其應(yīng)用［M］．北京：清華大學(xué)出版社，2012．

［9］Ng M，Qi Liqun，Zhou Guanglu．Finding the largest eigenvalue of a non－negative tensor［J］．SIAM J．Matrix Anal．Appl．，2009，31（3）：1090－1099．

［10］Chang K C，Qi Liqun，Zhou Guanglu．Singular values of a real rectangular tensor［J］．Math．Anal．Appl．，2010，370（1）：284－294．

［11］Yang Yuning，Yang Qingzhi．Singular values of nonnegative rectangular tensors［J］．Front．Math．China，2011，6（2）：363－378．

［12］Kolda T G，Bader B W．Tensor decompositions and applications［J］．SIAM Review，2009，51（3）：455－500．

［13］Chang K C，Pearson K，Zhang T．Some variational principles for Z eigenvalues of nonnegative tensors［J］．Linear Algebra and its Applications，2013，438（1）：4166－4182．

［14］Qi Liqun，Wang Fei，Wang Yiju．Z－eigenvalue methods for a global polynomialo ptimizationproblem［J］．Math．Program．Ser．A，2009，118（1）：301－316．

［15］Liu Yongjun，Zhou Guanglu，Nur F I．An always convergent algorithm for the largest eigenvalues of an irreducible nonegative tensor［J］．Journal of Computational and Applied Mathematics，2010，235（1）：286－292．

［16］Qi Liqun．Symmetric nonnegative tensors and copositive tensors［J］．Linear Algebra and its Applications，2013，439（1）：228－238．