關(guān)于圖值隨機(jī)元序列的強(qiáng)極限定理

汪忠志,李文喜

(安徽工業(yè)大學(xué)數(shù)理科學(xué)與工程學(xué)院,安徽馬鞍山243002)

關(guān)于圖值隨機(jī)元序列的強(qiáng)極限定理

汪忠志,李文喜

(安徽工業(yè)大學(xué)數(shù)理科學(xué)與工程學(xué)院,安徽馬鞍山243002)

本文研究在局部連通圖中取值的隨機(jī)元的r-階均值集、r-階廣義樣本均值集的基本性質(zhì)及其極限性質(zhì).利用關(guān)于隨機(jī)元的分離引理以及隨機(jī)游動(dòng)的常返性,得到了關(guān)于圖值隨機(jī)元序列廣義強(qiáng)大數(shù)定理.推廣了已有的結(jié)果.

強(qiáng)大數(shù)定律;圖;r-階權(quán)函數(shù);r-階均值集;r-階廣義樣本均值;隨機(jī)游動(dòng)

1 引言

概率極限理論是概率論的重要分支之一.經(jīng)典的極限理論曾經(jīng)是概率論研究的中心課題,近現(xiàn)代極限理論的研究至今方興未艾.自上世紀(jì)30年代以來,許多學(xué)者致力于將概率論推廣到各種數(shù)學(xué)結(jié)構(gòu)中.著名概率學(xué)家Love在闡述概率論的基本特征時(shí)曾指出“到今天,概率論在數(shù)學(xué)上已經(jīng)發(fā)展的充分成熟,于是就呈現(xiàn)出來這樣一種預(yù)兆,即要擺脫這些限制而考慮從測度空間到愈益抽象的空間的更一般的函數(shù)族······”.關(guān)于抽象空間上的概率理論的研究,可以上溯到1935年Kolmogorov[1]關(guān)于Banach空間上的概率分布的特征泛函以及1948年Frchet[2]關(guān)于Banach空間上的Gauss分布的工作.

關(guān)于抽象空間上的隨機(jī)元的定義,有多種不同的方式.在一般情況下,它們還確實(shí)是彼此不同的概念.不同的定義有各自的優(yōu)缺點(diǎn),分別適應(yīng)研究不同問題的需要.對取值于抽象空間上的隨機(jī)元的隨機(jī)過程的合理解釋與深刻的應(yīng)用激發(fā)了許多學(xué)者對一般拓?fù)淇臻g上的概率的研究,而研究的關(guān)鍵是給出隨機(jī)元“均值”(平均)的合理定義以及相應(yīng)的收斂性概念.

Banach空間上的隨機(jī)元x1,x2,···,xn的均值可以自然地定義為n-1(x1+x2+···+xn),利用Galfand-Pettis積分可以定義隨機(jī)元的均值(期望)(參見文[3]).與線性空間不同,在一般(非線性)拓?fù)淇臻g中,必須尋找合適的途徑來定義隨機(jī)元的“均值”以及相應(yīng)的收斂性概念.Frchet在文[2]中討論了一般度量空間上的概率,并且給出了完備度量空間(X,d)上關(guān)于概率測度μ的均值(亦稱Frchet均值)的定義.即設(shè)ξ:?→X是定義在概率空間(?,F,P),在(X,d)中取值的隨機(jī)元.令

稱Λ為隨機(jī)元ξ的均值集(Frechet均值).

可以看出這個(gè)定義顯然是包含了最小二乘法的基本思想.最早獲得度量空間上隨機(jī)元的極限定理的是Ziezold,他(她)在文[4]中討論了可分?jǐn)M度量空間上的隨機(jī)元的強(qiáng)大數(shù)定律,隨后Sverdrup–Yhygeson[5]討論了取值于連通緊空間上的隨機(jī)元的強(qiáng)大數(shù)定律, Bhattacharya和Patrangenaru[6]給出了有界子集均為緊子集的度量空間上的隨機(jī)元的極限定理,推廣了Ziezold[4]的結(jié)果.最近,Natalia Mosina[7,8]等給出了在圖與群上取值的隨機(jī)元的一個(gè)新的概率框架,討論了隨機(jī)元均值集(期望)的若干性質(zhì)及大數(shù)定律,并用在辮群(Braid group)上取值的隨機(jī)元的均值集和大數(shù)定律,破解了一個(gè)基于辮群上共軛元的難解問題的零知識證明協(xié)議,這在密碼學(xué)上具有十分重要的意義.

本文在文獻(xiàn)[7]的基礎(chǔ)上,提出了在局部有限圖上取值的隨機(jī)元的r-階權(quán)函數(shù)、r-階均值集以及r-階廣義樣本均值集等概念,討論了其基本性質(zhì),并且就隨機(jī)元的均值集是單點(diǎn)集和兩點(diǎn)集情形,獲得了關(guān)于圖值隨機(jī)元序列的廣義強(qiáng)大數(shù)定理.

2 預(yù)備知識

設(shè)(?,F,P)是固定的概率空間,Γ=(V(Γ),E(Γ))是局部有限圖.考慮定義在可測空間(?,F)上且在Γ的頂點(diǎn)集中取值的隨機(jī)元ξ:?→V(Γ).

假設(shè)μ是由隨機(jī)元ξ在V(Γ)的原子上誘導(dǎo)出的概率測度

記為μξ(·).

現(xiàn)在在新的概率空間(V(Γ),S,μ)上來研究隨機(jī)元ξ:?→V(Γ).

定義2.1設(shè)?v∈V(Γ).令

稱之為v關(guān)于測度μ的r-階權(quán)函數(shù),其中d(v,i)表示v與i在Γ中的距離.

注一般來說,權(quán)函數(shù)并不總是有限的.本文中如無特別說明,總假設(shè)M(r)(·)＜∞(r＞0),即M(r)(·)在V(Γ)的每一點(diǎn)都有定義.

定義2.2設(shè)(V(Γ),S,μ)為所考慮的概率空間,ξ:?→V(Γ)是隨機(jī)元,r＞0.令

并稱之為隨機(jī)元ξ的r-階均值集.

注值得注意的是,如果在(2.3)式中分別令r=2,r=1,r→0以及r→∞,上述定義的均值集(期望)可以導(dǎo)出對應(yīng)于Euclidean空間中隨機(jī)變量的均值、中位數(shù)、眾數(shù)以及中列數(shù).

令

定義2.3集

為了以下證明的需要,給出幾個(gè)基本引理.

引理2.1設(shè)Γ是連通圖,u,v∈V(Γ).如果M(r)(u)＜∞,則M(r)(v)＜∞.

證令d(u,v)=d,由三角形不等式

有

推論2.1設(shè)(V(Γ),S,μ)是所考慮的概率空間,Γ是連通圖,ξ:?→V(Γ)是Γ上的隨機(jī)元,則

或domain(M)=φ.

引理2.2設(shè)ξ:?→V(Γ)是Γ-值隨機(jī)元,其中Γ是局部有限的連通圖且r-階權(quán)函數(shù)＜∞,則均值集E(ξ)非空且有限.

證對任意固定的頂點(diǎn)v∈Γ,其權(quán)函數(shù)

選取R∈N,使得

其中

是Γ中以v為中心R為半徑的球.

選取u∈V(Γ),使得d(u,v)≥3R.利用三角形不等式及(2.7)式,有

引理2.3[9]設(shè)是i.i.d.隨機(jī)序列,且E(ξ1)＜∞,是一列正整數(shù),則

引理2.4設(shè)Γ是局部有限的連通圖,v∈V(Γ),是一列i.i.d.Γ值隨機(jī)元,即 ξi:?→V(Γ),i=1,2,···,并且＜∞.則

證對?v∈V(Γ),M(r)(v)==Edr(v,ξ1).注意到由引理2.3即得結(jié)論成立.

值得注意的是引理2.4中的收斂并不是一致地成立,即對局部有限(或無限)圖上的分布μ,及某些ε＞0,可能有

引理2.5[10,11]設(shè)是一列i.i.d.隨機(jī)變量,且Eξ1=0,E|ξ1|＜∞.令R(n)=n=1,2,···,則隨機(jī)游動(dòng)是常返的.

引理2.6(分離引理)設(shè)Γ是局部有限的連通圖,v∈V(Γ),是一列i.i.d.Γ值隨機(jī)元,即ξi:?→V(Γ),i=1,2,···.如果＜∞,則

證欲證(2.11)式,只須證存在δ＞0,使得

成立即可.

本文分兩步來完成.首先證對固定的v0∈E(ξ1)以及充分大的m＞0,有

成立.其次證明

由測度的σ-可加性即得(2.11)式成立.

設(shè)v0∈E(ξ1).因M(r)(v0)＜∞,如引理2.2中的做法選取R∈R,使得令m=3R.由引理2.2的證明過程可知,如果u滿足d(u,v0)≥3R,則

由此可知E(ξ1)?Bv0(3R).

因?yàn)棣Ｊ蔷植坑邢薜?所以Bv0(R)是有限的.?ε＞0,令

由關(guān)于隨機(jī)變量μan,n(u)=的強(qiáng)極限定理可知,當(dāng)n→∞時(shí),μan,n(u)→ μ(u)a.s.,因而P(Cε)=1.特別的,取

而且事件Cε?是集

的子集.事實(shí)上,在(2.16)式定義的集合Cε?上有利用上述結(jié)論以及(2.15)式,有

于是

由引理2.4,?v∈V(Γ)以及?ε＞0,有

因?yàn)锽v0(3R)是有限集,可知上述收斂在Bv0(3R)上一致成立,即

特別地,注意到E(ξ1)?Bv0(3R),取

最后,在(2.18)和(2.20)式給出的集合的交集上,由M(r)(v0)=M(r)(v)(因v0,v∈E(ξ1))以及(2.13)式,對滿足條件的δ有

第二步,利用(2.15)式,取

即以概率1,存在N=N(ε′)使得對?n＞N和u∈Bv0(3R),有ε′.由于E(ξ1)?Bv0(3R),因此,當(dāng)v∈E(ξ1)時(shí),有注意到M(r)(u)-M(r)(v0)＞0,知存在N=N(ε′),使得當(dāng)n＞N時(shí),?u∈Bv0(3R)E(ξ1),有

且有

即

因此(2.14)式對δ≤2ε′成立.取δ=即可得引理成立.

3 強(qiáng)極限定理

經(jīng)典的強(qiáng)大數(shù)定律表明,如果獨(dú)立同分布隨機(jī)變量的期望存在,則樣本均值幾乎處處收斂到隨機(jī)變量的數(shù)學(xué)期望.然而,下面的例子可以看出,對在圖上取值的隨機(jī)元的廣義樣本均值在普通意義下并不一定收斂.

例3.1考慮圖Γ=(V,E),其中V={v1,v2},E={(v1,v2)}.μ是由隨機(jī)元ξ1:?→V誘導(dǎo)的V(Γ)上的概率測度,且此時(shí)有M(r)(v1)=M(r)(v2)=1/2, E(ξ)={v1,v2}.

由定義2.3,有

同理

令

和

于是有

及

顯然,W(n)與R(n)同分布.由于Z上的對稱隨機(jī)游動(dòng)是常返的,從而有P{vi∈San,n,i.o.}= 1,i=1,2.因此

定理3.1設(shè)Γ是局部有限圖,是定義在概率空間(?,F,P)上在V(Γ)中取值的一列i.i.d.隨機(jī)元,μ是定義在Γ上由ξ1誘導(dǎo)出的概率測度.假設(shè)M(r)(u)＜∞,?u∈V(Γ).則

證由引理2.6,有

由測度的σ-可加性,有

前面分別就Eξ1是單點(diǎn)與兩點(diǎn)集這兩種情況來證明強(qiáng)大數(shù)定理,關(guān)于Eξ1是多點(diǎn)集的情形的證明比較復(fù)雜,將在另文中討論.

1.Eξ1是單點(diǎn)集情形.

定理3.2設(shè)Γ是局部有限連通圖,是一列i.i.d.Γ-值隨機(jī)元序列,ξi:?→V(Γ).如果＜∞且E(ξ1)={v},v∈V(Γ),即E(ξ1)是單點(diǎn)集,則

證(3.2)式可以表述為

或等價(jià)地

由引理2.6,有

于是

2.Eξ1是兩點(diǎn)集的情形.

定理3.3設(shè)Γ是局部有限連通圖,是一列i.i.d.Γ-值隨機(jī)元,ξi:?→V(Γ).如果＜∞且E(ξ1)={v1,v2},vi∈V(Γ),i=1,2,即#E(ξ1)=2,則

證由定理3.1知?E(ξ1).欲證(3.4)式,只須證明相反的包含關(guān)系.注意到E(ξ1)={v1,v2},即只在點(diǎn)v1和v2上取到最小值,即

由權(quán)函數(shù)的定義,有

由引理2.4,有

由引理2.6知,存在數(shù)N∈N,當(dāng)n＞N,幾乎處處有

因此當(dāng)n＞N,

當(dāng)且僅當(dāng)

同理

當(dāng)且僅當(dāng)

欲證{v1,v2}?只須證明無窮多次取正值和負(fù)值.令

和

注意到,W(n)=R(an+n)-R(an)且W(n)與R(n)同分布,

因?yàn)?/p>

且

故

[1]Kolmogorov A N.La transformation de Laplace dans les espaces lineaires[J].CD.Acad.Sci.Paris, 1935,200:1717–1718.

[3]吳智泉,王向忱.巴氏空間上的概率論[M].吉林:吉林大學(xué)出版社,1990.

[4]Ziezold H.Expected figures and a strong law of large numbers for random elements in quasi-metric spaces[J].Trans.7th Prague Conf.Inf.Theory,Stat.Dec.Func.,Random Processes A,1977,591–602.

[5]Sverdrup H,Thygeson.Strong law of large numbers for measures of central tendency and dispersion of random variables in compact metric spaces[J].Ann.Stat.,1981,9:141–145.

[6]Bhattacharya R N,Patrangenaru V.Large sample theory of intrinsic and extrinsic sample means on manifolds-I[J].Ann.Stat.,2003,31:1–29.

[7]Mosina N,Ushakov A.Strong law of large numbers on graphs and groups[J].arXiv:0904.1005v2 [Math.PR]29 Jun 2010.

[8]Mosina N,Ushakov A.Mean set attack:cryptanalysis of Sibert et al.authentication protocol[J].J. Math.Crypt.,2010:4(2):149–174.

[9]Gaposhkin V F.The law of large numbers for moving averags of independent random variabls[J]. Math.Zametki,1987,42(1):124–131.

[10]Spitzer F.Priciples of random walk(2nd ed.)[M].New York,Berlin,Heidelberg:Springer-Verlag, 2001.

[11]Feller W.An Introduction to probability theory and its applications,Vol.II(2nd ed.)[M].New York: John Wiley,1971.

[12]張麗娜.任意B值隨機(jī)變量的強(qiáng)收斂性[J].數(shù)學(xué)雜志,2002,22(3):297–300.

ON SOME LIMIT THEOREMS FOR GRAPH-VALUED RANDOM ELEMENTS

WANG Zhong-zhi,LI Wen-xi
(School of Mathematics&Physics Science and Engineering,Anhui University of Technology, Maanshan 243002,China)

In this paper,the authors discuss the basic properties of the general rth order mean set and rth order sample mean set of random elements,which take values on a locally connected graph,and the limit properties of them.By applying the separation lemma of random elements and the recurrence of random walk,we obtain the general strong law of large numbers for graph-valued random elements.Moreover,we generalize the existing results.

general strong law of large numbers;graph;r-th order weight function;r-th order mean set;r-th order sample mean set;random walk

tion:60F15

O211.4

A

0255-7797(2017)01-0118-11

2014-08-22接收日期:2015-03-19

國家自然科學(xué)基金(11071104);國家社會(huì)科學(xué)基金(13BJY011);安徽省自然科學(xué)基金(1308085QF113;1408085MA04);安徽工業(yè)大學(xué)研究生創(chuàng)新基金(2012090)資助.

汪忠志,男,安徽安慶,教授,主要研究方向:概率論及其應(yīng)用.