溫莎日記 33

Discrete-Time Renewal Processes

Renewal processes provide a theoretical framework for investigating the occurrence of patterns in repeated independent trials. Roughly speaking, the reason for using the term “renewal” comes from the basic assumption that when the pattern of interest occurs for the first time, the process starts a new, in the sense that the initial situation is reestablished. This means that, starting from this “renewal instant,” the waiting time for the second occurrence of the pattern has the same distribution as the time needed for the first occurrence. The process continues like this indefinitely.

Springer Science+Business Media, LLC 2008

Renewal Chains

Let?(X_n)_{n\in N} ?be a sequence of extended positive integer-valued random variables,?X_n>0 a.s. for n ≥ 1 (we use the term “extended” in the sense that X_n can take the value ∞). Denote by (S_n)_{n∈N}?the associated sequence of partial sums:

S_n:=X_0+X_1+...+X_n.

An arrival time sequence (S_n)_{n∈N}, for the waiting times (X_n)_{n∈N^?} form an i.i.d. sequence and S_0 = X_0 = 0, is called a renewal chain, and every S_n is called a renewal time.?There are many real situations which could be modeled by renewal chains.

Example. Consider the following DNA sequence of HEV (hepatitis E virus):

Suppose that the bases {A, C, G, T } are independent of each other and have the same probability of appearing in a location, which is equal to 1/4. Thus the occurrences of one of them, say, C, form a renewal chain. The inter-arrival distribution is geometric with parameter equal to 1/4.

It is worth stressing here an important phenomenon which is specific to discrete-time renewal processes. As f_0 = P(X_1 = 0) = 0, the waiting time between two successive occurrences of a renewal is at least one unit of time. Consequently, in a finite interval of time, of length, say, n, we can have at most n renewals. As will be seen in the sequel, this is the reason why many variables of interest can be expressed as finite series of basic quantities, whereas in a continuous-time setting the corresponding series are infinite. This is one advantage of a renewal theory carried out in a discrete-time setting.

Let f, g : N → R. The discrete-time convolution product of f and g is the function f ? g : N → R:f*g(n):=\sum_{k=0}^n f(n-k)g(k),n\in N.?

For notational convenience, we use both f ? g(n) and (f ? g)_n for denoting the convolution. The generating functions of (f_n)_{n∈N} and (u_n)_{n∈N} are related by

\Phi (s)=\frac{U(s)-1}{U(s)} ,U(s)=\frac{1}{1-\Phi (s)} .

(solution of a discrete-time renewal equation). If?b_n \geq 0,n\in N?and?\sum\nolimits_{n=0}^∞ b_n<∞?then the discrete-time renewal equation has the unique solution?g_n=(u*b)_n ,n \in  N.

This example shows that there is a correspondence in both senses between renewal chains and Markov chains. For this reason, techniques and results developed for Markov chains can be applied to renewal chains and vice versa.?A function of great importance in renewal theory is the renewal function \Psi (n), n ∈ N, defined as the expected number of renewals up to time n:

\Psi (n):=E[N(n)+1]=\sum_{k=0}^n P(S_k \leq n) =\sum_{k=0}^n \sum_{l=0}^n f^{(k)}_l,n\in N.

As?N(0)=0, we get?\Psi (0)=1.

Some authors define the renewal function without taking into account the renewal that occurs at the origin; if this were the case, we would have Ψ(n) = E(N(n)). There is only a question of convenience for technical reasons, and we have chosen here to include the renewal at the origin.

The renewal function can be expressed in terms of?(u_n)_{n\in N}. Indeed,?

\Psi (n)=E(N(n)+1)=E(\sum_{k=0}^n Z_k)=\sum_{k=0}^n u_k,n\in  N.

(strong law of large numbers for N(n)).?For a recurrent renewal chain?(S_n)_{n\in N}?we have

\lim_{n\to ∞} \frac{N(n)}{n} =\frac{1}{\mu } ,a.s.

(central limit theorem for N(n)).?Consider a positive recurrent renewal chain?(S_n)_{n\in  N}, with?\mu =E(X_1) < ∞?and?0<\sigma ^2 :=Var(X_1) < ∞. Then?

\frac{N(n)-n/\mu }{\sqrt{n \sigma ^2 / \mu ^3} }  \rightarrow _{n\rightarrow ∞}^D N(0,1).

(elementary renewal theorem).?For a recurrent renewal chain?(S_n) _{n\in  N}?we have?

\lim_{n\to ∞} \frac{\Psi (n)}{n} =\frac{1}{\mu } .

The renewal theorem in a continuous-time setting states that for a continuous-time recurrent aperiodic renewal process, for any h > 0, we have

\lim_{n\to ∞} [\Psi (n+h)-\Psi (n)]=\frac{h}{\mu } .

The same result holds true for a continuous-time recurrent periodic renewal process of period d, provided that h is a multiple of d.

Delayed Renewal Chains

Delayed renewal chains are used for modeling the same type of phenomenon as renewal chains do, with the only difference that we do not consider the origin as the occurrence of the first order renewal, that is, S_0 = X_0 > 0. In other words, we want to observe a normal renewal chain, but we missed the beginning and we denote by S_0 the time when we observe the first renewal, which is not identically 0 but follows a certain distribution.

An arrival time sequence (S_n)_{n∈N} for the waiting times (X_n)_{n∈N^?} form an i.i.d. sequence and X_0 is independent of (X_n)_{n∈N^?} is called a delayed renewal chain and every S_n is called a renewal time. The chain (S_n ?S_0)_{n∈N} is an ordinary renewal chain, called the associated renewal chain. Note that (S_n)_{n∈N} is a renewal chain iff S_0 = 0 a.s.

It presents the counting process of the number of renewals in a delayed renewal chain.

Example. Consider a sequence of i.i.d. Bernoulli trials. We can prove that the times of occurrence of different finite patterns form renewal chains, generally delayed. For instance, suppose we have the following sequence issued from repeated i.i.d. Bernoulli trials

and suppose that we are interested in the occurrence of the pattern SFS in this sample. Two different counting procedures can be considered. First, suppose that the counting starts anew when the searched pattern occurs, that is, we do not allow overlapping. Note that SFS occurs in the 6th and 11th trials. Note also that SFS occurs in the 13th trial, but we do not count this occurrence, because we do not allow overlapping, so we have started anew the counting at the 12th trial (that is, after the occurrence of SFS in the 11th trial). Second, suppose that we allow overlapping. In this case, the pattern SFS occurs in the 6th, 11th and 13th trial. In both situations the occurrence times of the pattern SFS is a delayed renewal chain.

A delayed renewal chain is called aperiodic (resp. periodic of period d > 1) if the associated renewal chain is aperiodic (resp. periodic of period d > 1). Similarly, a delayed renewal chain is said to be transient or positive (null) recurrent if the associated renewal chain is a such.

The Stationary Renewal Chain

The objective is to construct a particular case of delayed renewal chain which has important stationary or time-invariant properties. The question we want to answer is the following: For what kind of delayed renewal chain is?v_n constant with respect to n ? Let us consider (S_n)_{n∈N} a delayed renewal chain such that P(S_0 < ∞) = 1, i.e., (b_n)_{n∈N} is a proper distribution. Suppose that v_n = Δ for all n ∈ N. Consequently, the generating function V (s) is given by

V(s)=\sum_{n=0}^∞ \Delta s^n = \frac{\Delta }{1-s} ?and by using the relation?V(s)=B(s)U(s)=\frac{B(s)}{1-\Phi (s)} , then we obtain

B(s)=\frac{\Delta }{1-s} (1-\Phi (s)),?\sum_{n=0}^∞ b_ns^n = \Delta (\sum_{n=0}^∞ s^n ) (1-\sum_{n=1}^∞ f_n s^n ).

Equalizing the coefficients of s^n in the left-hand and right-hand side, for n ∈ N, we get

b_0=\Delta ,

b_n=\Delta (1-\sum_{k=1}^n f_k)=\Delta P(X_1>n),n\in N^*.

Taking into account the fact that?\sum_{n=0}^∞ b_n=1 , and using?\sum_{n=0}^∞ P(X_1>n)=\mu , we obtain

\Delta =1/\mu ,

provided that the delayed renewal chain is positive recurrent. Thus, we have shown that if a positive recurrent delayed renewal chain satisfies?v_n = \Delta ?for all?n \in  N, then?\Delta =1/\mu ?and?b_n =P(X_1>n)/\mu .

A positive recurrent delayed renewal chain (S_n)_{n∈N} such that b_n = P(X_1 > n)/μ for all n ∈ N, we want to prove that v_n = 1/μ for all n ∈ N. For 0 ≤ s < 1, the generating function of the first occurrence of a renewal is

B(s)=\frac{1}{\mu } \sum_{n=0}^∞ P(X_1>n)s^n= \frac{1}{\mu } \sum_{n=0}^∞ \sum_{k=n+1}^∞P(X_1=k)s^n=\frac{1}{\mu } \sum_{k=1}^∞ \sum_{n=0}^{k-1}  s^n f_k

= \frac{1}{\mu } \frac{1}{1-s} (\sum_{k=1}^∞ f_k - \sum_{k=1}^∞ s^kf_k)=\frac{1}{\mu } \frac{1-\Phi (s)}{1-s} .

From above, we obtain

V(s)=\frac{1}{\mu }  \frac{1}{1-s} =\sum_{n=0}^∞ \frac{1}{\mu } s^n,

so?v_n=1/\mu ?for all?n \in  N.

This entire discussion can be summarized in the following result.

最后編輯于
?著作權歸作者所有,轉載或內容合作請聯系作者
  • 序言:七十年代末问词,一起剝皮案震驚了整個濱河市韩玩,隨后出現的幾起案子,更是在濱河造成了極大的恐慌芥牌,老刑警劉巖寸爆,帶你破解...
    沈念sama閱讀 219,490評論 6 508
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件替废,死亡現場離奇詭異,居然都是意外死亡绎晃,警方通過查閱死者的電腦和手機爹脾,發(fā)現死者居然都...
    沈念sama閱讀 93,581評論 3 395
  • 文/潘曉璐 我一進店門,熙熙樓的掌柜王于貴愁眉苦臉地迎上來箕昭,“玉大人灵妨,你說我怎么就攤上這事÷渲瘢” “怎么了泌霍?”我有些...
    開封第一講書人閱讀 165,830評論 0 356
  • 文/不壞的土叔 我叫張陵,是天一觀的道長述召。 經常有香客問我朱转,道長,這世上最難降的妖魔是什么积暖? 我笑而不...
    開封第一講書人閱讀 58,957評論 1 295
  • 正文 為了忘掉前任藤为,我火速辦了婚禮,結果婚禮上夺刑,老公的妹妹穿的比我還像新娘缅疟。我一直安慰自己,他們只是感情好遍愿,可當我...
    茶點故事閱讀 67,974評論 6 393
  • 文/花漫 我一把揭開白布存淫。 她就那樣靜靜地躺著,像睡著了一般沼填。 火紅的嫁衣襯著肌膚如雪桅咆。 梳的紋絲不亂的頭發(fā)上,一...
    開封第一講書人閱讀 51,754評論 1 307
  • 那天坞笙,我揣著相機與錄音岩饼,去河邊找鬼。 笑死薛夜,一個胖子當著我的面吹牛籍茧,可吹牛的內容都是我干的。 我是一名探鬼主播却邓,決...
    沈念sama閱讀 40,464評論 3 420
  • 文/蒼蘭香墨 我猛地睜開眼硕糊,長吁一口氣:“原來是場噩夢啊……” “哼院水!你這毒婦竟也來了腊徙?” 一聲冷哼從身側響起简十,我...
    開封第一講書人閱讀 39,357評論 0 276
  • 序言:老撾萬榮一對情侶失蹤,失蹤者是張志新(化名)和其女友劉穎撬腾,沒想到半個月后螟蝙,有當地人在樹林里發(fā)現了一具尸體,經...
    沈念sama閱讀 45,847評論 1 317
  • 正文 獨居荒郊野嶺守林人離奇死亡民傻,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內容為張勛視角 年9月15日...
    茶點故事閱讀 37,995評論 3 338
  • 正文 我和宋清朗相戀三年胰默,在試婚紗的時候發(fā)現自己被綠了。 大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片漓踢。...
    茶點故事閱讀 40,137評論 1 351
  • 序言:一個原本活蹦亂跳的男人離奇死亡牵署,死狀恐怖,靈堂內的尸體忽然破棺而出喧半,到底是詐尸還是另有隱情奴迅,我是刑警寧澤,帶...
    沈念sama閱讀 35,819評論 5 346
  • 正文 年R本政府宣布挺据,位于F島的核電站取具,受9級特大地震影響,放射性物質發(fā)生泄漏扁耐。R本人自食惡果不足惜暇检,卻給世界環(huán)境...
    茶點故事閱讀 41,482評論 3 331
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望婉称。 院中可真熱鬧块仆,春花似錦、人聲如沸王暗。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,023評論 0 22
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽瘫筐。三九已至蜜暑,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間策肝,已是汗流浹背肛捍。 一陣腳步聲響...
    開封第一講書人閱讀 33,149評論 1 272
  • 我被黑心中介騙來泰國打工, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留之众,地道東北人拙毫。 一個月前我還...
    沈念sama閱讀 48,409評論 3 373
  • 正文 我出身青樓,卻偏偏與公主長得像棺禾,于是被迫代替她去往敵國和親缀蹄。 傳聞我的和親對象是個殘疾皇子,可洞房花燭夜當晚...
    茶點故事閱讀 45,086評論 2 355

推薦閱讀更多精彩內容

  • 《閉上眼睛才能看清楚自己》這本書是香海禪寺主持賢宗法師的人生體悟,修行心得及講學錄缺前,此書從六個章節(jié)講述了禪修是什么...
    宜均閱讀 10,028評論 1 25
  • 前言 Google Play應用市場對于應用的targetSdkVersion有了更為嚴格的要求蛀醉。從 2018 年...
    申國駿閱讀 64,234評論 14 98
  • 《來拯刁,我們說說孤獨》 1·他們都在寫孤獨 一個詩人 如果 不說說 內心的孤獨 不將孤獨 寫進詩里 是不是很掉價呢 ...
    聽太陽升起閱讀 4,376評論 1 7
  • 自幼貧民窟長大的女子,僥幸多念了兩本書逝段,枉以為可以與人平起平坐垛玻。可是人生從來都是接力賽奶躯,我們卻天真的當成了百米沖刺...
    Leeanran閱讀 5,772評論 1 5
  • 云舒老師帚桩,姓甚名誰,男的女的嘹黔,多大歲數朗儒,這些我全然不知。之所以要寫寫云舒老師参淹,完全是因為他寫的文章醉锄,如一個巨大的磁...
    數豆者m閱讀 2,355評論 6 9