Consider a sequence X1, X2, ... of IID binary rv s with Pr{Xn = 1} = p1 and Pr{Xn = 0} = p0 = 1 - p1. A renewal is said to occur at time n ≥ 2 if Xn-1 = 0 and Xn  = 1.

(a) Show that {N(n); n > 0} is a renewal counting process where N(n) is the number of renewals up to and including time n.

(b) What is the probability that a renewal occurs at time n, n ≥ 2?

(c) Find the expected inter-renewal interval; use Blackwell's theorem.

(d) Now change the definition of renewal so that a renewal occurs at time n if Xn-1 = 1 and Xn  = 1. Show that {N∗(n); n≥ 0} is a delayed renewal counting process where n is the number of renewals up to and including n for this new definition of renewal.

(e) Find E [Yi] for i ≥ 2 for the case in (d).

(f) Find E [Y1] for the case in (d). Hint: Show that E [Y1|X1 = 1] = 1 + E [Y2] and

E [Y1|X1 = 0] = 1 + E [Y1].

(g) Looking at your results above for the strings (0,1) and (1,1), show that for an arbitrary string a = (a1, ... , ak), the arrival process of successive occurrences of the string is a renewal process if no proper suffix of a is a prefix of a. Otherwise it is a delayed renewal process.

(h) Suppose a string a = (a1, ... , ak) of length k has no proper suffixes equal to a prefix. Show that the time to the first renewal satisfies

E [Y1] = nk.

£=1 pa£

(i) Suppose the string a = (a1, ... , ak) has at least one proper suffix equal to a prefix, and suppose i is the length of the longest such suffix. Show that the expected time until the first occurrence of a is given by

E [Y1] = nk

+ E [Ui] ,

£=1 pa£

where E [Ui] is the expected time until the first occurrence of the string (a1, ... , ai).

(j)  Show that the expected time until the first occurrence of a = (a1, ... , ak) is given by k Ii E [Y ], ni i=1 £=1 pa£

where, for 1 ≤ i ≤ k, Ii is 1 if the prefix of a of length i is equal to the suffix of length i. Hint: Use (h) recursively. Also show that if a has a suffix of length i equal to the prefix of length i and also a suffix of length j equal to a prefix of length j where j i, then the suffix of (a1, ... , ai) of length j is also equal to the prefix of both a and (a1, ... , ai) of lengthj.

(k) Use (i) to find, first, the expected time until the first occurrence of (1,1,1,1,1,1,0) and, second, that of (1,1,1,1,1,1). Use (4.31) to check the relationship between these answers.

Text Book: Stochastic Processes: Theory for Applications By Robert G. Gallager.