Chapter 2

Question 1

Renewal

Answer 1

On discrete scale and is occurrence. Between renewals nothing happens

Eg light bulb is inspected each time point/ step but renewal happens when needs I be replaced

Question 2

Lengths of time between renewals

Clock times for renewals

Answer 2

Between renewals time modelled as random variables.
ASSUME length of time are INDEPENDENT and IDENTICALLY DISTRIBUTED Random vars.
Discrete values.
Times between renewals are T₁,T₂, T₃,…

Clock times: 
0, *
T₁, 
T₁+ T₂, 
T₁+T₂+ T₃,...

*We assume the process has initial renewal at t=0
•independent so length of one doesn’t affect the other

Question 3

f_n in renewal theory: what is it

• if this applies then it’s a Renewal process

Answer 3

f_n = CONDITIONAL probability that the NEXT!!! RENEWAL occurs at time t+n, given that there was a renewal at t
Probability that a given inter renewal time takes the value k

f_i = P(T_i =n ) for n=1,2,3,…

Eg probability that the first renewal after renewal at time 2 occurs at time 3 f_1= P( T_3 = 1) CLEARLY MC PROPERTY APPLIES
These form the COMMON DISTRIBUTION for the renewal times T₁,T₂, T₃,….

•two renewals can’t occur at the same time so f₀ =0 always. And T_i can’t be 0

Question 4

N_t

Answer 4

Renewals occurred up to and including time t

Eg number of bulbs replaced

Question 5

f_n distribution and f

Answer 5

f = sum of f_n from 1 to infinity

In light bulb f =1 and non neg f_n ‘s

However....
We use f to see if 
Defective probability distribution
Recurrent process : null or positive
Or transient process

Question 6

Defective probability distribution

Answer 6

When f

( Σ from 1 to infinity
Of
f_n )

Is LESS THAN 1

• 1-f is the defect of the distribution.
• with probability 1-f the random variable T_i will take the value infinity
• the ith light bulb is immortal and the first infinite T_i is the event where the ith INTER-RENEWAL interval never ends

Question 7

Recurrent process

Answer 7

Recurrent process if f=1

If a renewal process is recurrent then renewals continue forever

Non-defective distribution

Null recurrent or positive recurrent

Question 8

Transient process

Answer 8

If f is LESS THAN 1

If a renewal process is transient then with probability 1 there will be an infinite T_i for some i

So renewals stop.

Related to defective: defective if transient

Question 9

Null recurrent renewal process

Answer 9

Null recurrent if

The mean of random variables T_i is NOT FINITE

(Recurrent must have f=1 sum of f_ns)

Question 10

Positive recurrent renewal process

Answer 10

Positive recurrent if

The mean of random variables T_i if finite

(Recurrent must have f=1 sum of f_ns)

Question 11

Deriving f_n for a problem

Answer 11

The f_n’s form the distribution for the next n steps: with no renewals until the nth step (MP, starting at 0 or any t to t+N time)

Hence eg if each trial has bernouilli dist

f_n = P(T_i =n) = q^(n-1) p
n-1 failures don’t forget.

Sum of these gives properties of recurrent and transient etc

Question 12

Generating functions: general definition

Answer 12

d^n / ds^n of A(s)

GF if a given sequence (a_n) = a₀, a₁, a₂,…,
Is the power series

A(s) = Σ a_k S^K. ( from k=0 to infinity)
By geometric series converges only if |s| is less than 1.

•we can recover the sequence from GF, by differentiating and dividing by COEFFICIENT at s=0

Σ from k=n to infinity

[(k!)/(k-n)!] • a_k • s^ (k-n)

Evaluating and dividing

a_n = ( (d^n/ds^n) •A(s)) / (n!) |s=0

Question 13

Probability generating function of distribution of X

Answer 13

F_X (S)
=
Σ f_k S^K. ( from k=0 to infinity) 
= Σ P(X =n) S^K
= E(S^k)

Within the radius of convergence certain properties..
Fx(S) is therefore the GF of sequence f_0, f_1,…

As long as non neg values

Question 14

Lemma 3: for independent X Y and their generating function

Answer 14

For two independent random variables X and Y the generating function of the distribution of their sum X+Y is the product of the generating functions of the distributions of X and Y.

F_{X+Y} (S) = E( S^{X+Y}) = E(S^X) •E(S^Y)
=F_X(s)•F_Y(s)

Extend by induction to more variables

Question 15

If F(S) is the GF if a non-defective prob dist

Answer 15

If F(s) is the GF of a NON- DEFECTIVE probability distribution on the bin negative integers then within the radius of convergence

F’(S) =
Σ f_n• n• S^(n-1) . ( from n=1 to infinity)

•if F(s) is differentiable at S=1
F’(1) = μ = E[X] where μ is the expected value of a RV X with the given distribution.
•probability generating function entirely encodes distribution of f_n ‘s

Question 16

Finding the mean of a distribution:

Answer 16

If NOT DEFECTIVE f=1
Expected value found by differentiating GF and evaluating at S=1

If F(s)’s GF is possibly defective distribution of RVs taking non-beg integers then because the sum of a_ks from 0 to infinity is less than or equal to 0

Question 17

Possibly defective distributions GF implies that

Answer 17

If F(s)’s GF is possibly defective distribution of RVs taking non-beg integers then because the sum of a_ks from 0 to infinity is less than or equal to 0
We have that
For S In [0,1)
F(S) = sum of a_k• S^k ≤ sum of a_k ≤ 1

Question 18

Examples of generating functions :

Not a distribution
Probability distribution
Binomial
Geometric

Answer 18

1) not a distribution.

Let a_i = 1 for i =0,1,2,…

GF A(S) of this sequence:

A(S) = sum of a_k • S^k from 0 to infinity
= sum of S^k from 0 to infinity
This is a geometric series if s less than 1

2) probability GF where a_is are probabilities.
Fx(S)= sum from of P(X=k)S^k from 0 to infinity
Eg bernouilli = probability GF = (1-p)s^0 +ps = ps+1-p
3) binomial: by lemma 3 this I the multiple of the GFs for n bernouilli trials so =[ps +1 -p]^n
By binomial theorem
= sum of nCk p^k she (1-p)^ (n-k) from k=0 to n.
We can recover
f_k =P(X=k) = (nCk p^n (1-p)^(n-k)

4) geometric Fx(S) = sum from n=1 to infinity of
(q^(n-1) p) S^n
= pS (sum from n=0 to infinity) of (qS)^n = ps/ (1-qs) by geometric if |qs| less than 1

We can differentiate these and evaluate at 1 for the expected value.

Question 19

Theorem 4 F(s) and U(s)

Answer 19

Generating functions F(S) and U(S) satisfy
U(S)
= 1/(1-F(S))

For 0 ≤ S < 1.

Proof: a specific event u_n …

Question 20

(u_n)

Answer 20

(u_n) is a sequence of probabilities NOT a probability distribution as renewals at different clock times not mutually exclusive. Doesn’t sum to 1.

Question 21

u_n

Answer 21

The probability that a renewal ( not necessarily next one) occurs at time t+n.

For each n=0,1,2,…

Let E_n be the event that a renewal takes place at clock time n. Let u_n =P(E_n)
-------------
The process resets after renewal so
u_n = P( E_{t+n} |E_t)
Which doesn't depend on t.
u_0 =1 consistent with renewal at time 0

Question 22

Probabilities f_n in terms of events E₀, E₁,E₂,…

Answer 22

f_n = P(E₁^c,E₂^c ,…E_{n+1}^c,E_n)

No renewals for any times 1,2,… until n where there is a renewal
And as process resets after renewal

f_n = P(E{t+1}^c,E{t+2}^c ,…E_{t+n-1}^c,E_n)
^c ,E_{t+n} | E_t)

Ie no renewal at times t+1 to t+n-1 and renewal at time t+n given that there was a renewal at t

Question 23

E_n

Answer 23

The event that a renewal takes place at clock time n =0,1,2,…

Question 24

u_n in terms of f_n

Answer 24

u_ns are for final events, f_ns can be used to show multiple paths to that outcome

u₁ = f₁
u₂ = f₂ + f₁²
u₃ = f₃ + 2f₁f₂ + f₁²

Question 25

U(s)

Answer 25

Generating function of sequence u_n

U(S) = Σ u_k •S^k From k=0 to infinity

F(S) = Σ f_k •S^k From k=0 to infinity

Question 26

Bernouilli trials with blocking

Answer 26

Sequence of bern(p) trials however a renewal is blocked if a previous trial was a renewal.

No renewals on consecutive trial so 
f_1=0
For n bigger than or equal to 2
f_n = q^(n-2) •p
BECAUSE: 

To get a renewal on the nth trial it doesn’t matter whether first trial is a success or failure (because that’s blocked too), the next n-2 trials must be failures, and the nth trial must be a success.
GF
F(S) = sum from n=2 to infinity
If q^(n-2) •p•S^n

= (ps^2) /(1-qs)

• differentiate and evaluate at 1 gives expected time till first renewal
• finding U(s) (using partial fractions and series) allows us to find coefficients of s^n, u_n. As n tends to infinity we can see that u_n tends to p/1-p = 1/mean

Question 27

What does F(1) tell us

Answer 27

Evaluating the GF F(S) at 1 gives us the
Sum from k=1 to infinity
(Of f_k •S^1 = f_k)

= f
So as S approaches 1 F(S) approaches f
Remember f tells us whether process is recurrent or transient.
Also relationship between U(s) and F(s) tells us more…. we can deduce recurrence properties by series of u_n

Question 28

Theorem 4 relationship between U(s) and F(s) tells us about recurrence: summary

Answer 28

If U(1) =
Σ from n=0 to infinity
Of u_n 
= infinity then the process is RECURRENT
If U(1) = Σ from n =0 to infinity
Of u_n is LESS THAN infinity then the process is transient

Alternative criterion for recurrence from taking limits of theorem 4 as F(S) tends to f as S tends to 1

Question 29

A simple random walk on the integers

Answer 29

A markov chain with state space the integers and with transition probabilities:

p_i,j =
{p j=I+1
{1-p j=i -1
{0 o/w

Assume walk starts at 0
Let E_n be the event that after n steps we return to 0. As every time it returns it starts again, this forms a renewal process.

Question 30

Theorem 5: simple random walk on the integers, when is it recurrent or transient

Answer 30

Returns to 0 in the simple random walk, started from 0 are recurrent if p=1/2 and transient otherwise.

• as steps must be even we require for 2m steps m to be down
• we can analyse recurrence properties by looking at either F(s) or U(s) so we form U(s) from u_ns and as s tends to 1 U(S) = infinity only if p =1/2

Question 31

Theorem 6: simple random walk, recurrence properties null postitve

Answer 31

In a simple random walk started from 0 with p=1/2 returns to 0 are null recurrent.

• previously found U(S) and subbing in p can find F(S)
• differentiating and evaluating at 1 we have that F’(1) tends to infinity hence null recurrent

Question 32

Period of a renewal process

Answer 32

d = h.c.f{ n: f_n >0}

d is the largest positive integer such that a renewal can only occur at time n if n is a multiple of d.

•d isn’t necessarily the smallest n st f_n>0 : d can be the period but there doesn’t have to be a renewal at d

Eg f_1=0 but f_2,f_3,f_4,…>0
d=1 but f_d =0

(1 is always a multiple so this is possible) aperiodic

Question 33

Aperiodic renewal process

Answer 33

d=1 aperiodic

Otherwise the process is
Periodic with period d

Question 34

Delay and delayed process

Answer 34

Instead of assuming renewal at time 0 allow a random length of time D ( delay) to elapse until the first renewal occurs.

After which carries on as before, independently from the length of the delay.

Delay has its own (possibly defective: doesn’t sum to 1) distribution

Clock times also change

Question 35

B(S)

Answer 35

Generating function for a random var delay D of a delayed process.

B(S) =

Σ from n=0 to infinity
Of b_n•S^n

Where b_n = P(D=n) Is the probability that the delay is of length n, n ≥ 0.

Question 36

The clock times for a delayed renewal process

Answer 36

Clock times for delayed renewal process delay D

D, D + T₁ , D +T₁ + T₂,…

Renewal times stay the same…

Question 37

Delayed process and new defined u_n

Answer 37

• before we had u_n = P(E_n) and = P(E_{t+n} | E_t ) but now we distinguish them
• CHANGED: Define v_n as the probability of a renewal happening at time n (delayed version of u_n)

v_n =P(D=n)
With corresponding GF
V(S) =

Σ from n=0 to infinity
Of v_n•S^n
:

•Retain that u_n = P( E_{t+n} | E_t } with GF U(S). u_n is the probability that given at time t there’s a renewal, that there’s A!!! Renewal at time n steps later

•Define f_: (This is the same for the non-delayed case)
define f_n = P( T_i = n )
= P(E{t+1}^c,E{t+2}^c ,…E_{t+n-1}^c,E_n)
^c ,E_{t+n} | E_t) SAME AS BEFORE
The probability given that there is a renewal at time t that there will be another n steps later

Question 38

Theorem 7: after defining V(S) B(S) and F(S) for a delayed renewal process

Answer 38

The generating functions V(a) B(a) and F(a) are related by

V(s) = ( B(s) )
/
( 1 - F(s) )

=B(s) • U(s)

Question 39

Example 6 sided die: event E_n that after n rolls total numbers of 1,2,3,4,5 and 6 are equal.

Answer 39

This occurs if and only if n is a multiple of 6

So a renewal process is constructed and renewal occurs if and only if E _n occurs.

Then {n: f_n >0} = {0, 6, 12, 18, 24}

And so renewal process is periodic with period 6.

Question 40

Bernouilli trials with blocking and delay

Consider bernouilli trials with blocking (previous considered, no consecutive renewals) and assume process doesn’t behave if renewal at time 0 so renewal at time 1 isn’t blocked. Delay, renewal GF:

Answer 40

The delay D until the first renewal has a geometric distribution

b_n = q^(n-1)p for n≥1

So GF is B(S) = ps /(1-qs)

Once first renewal has occurred the distribution of T₁, T₂ are as previous so

F(s) = ps² / (1-qs)
By theorem 7
V(s) = (p/(1+p)) [ 1+s + s² + …] - [ 1-ps +p²s² -p³s³ +…]

SO WE CAN ALREADY FIND v(n):
By looking at coefficients of s^n
v_n = [P( a renewal at step n)]
= (p/(1-p) ( 1- (-p)^n )

I.e. v₀ = 0, v₁ = p, v₂ = (p/(1+p))(1-p²)

As before n tends to infinity v_n tends to p/(1+p)

Question 41

Recurrent patterns

Answer 41

Eg looking for a sequence in a coin toss, assuming indep tosses etc

The index numbers for which a sequence is completed form a renewal process

Or the first in the sequence

If we allow overlaps: eg THT occurs overlap THTHT. Hence given THT HT or THT must occur, disjoint from previous. Therefore the number of tosses between occurrences will be iid but the number of tosses until first renewal a different dist as we don’t already have T. THESE FORM A DELAYED RENEWAL PROCESS.

Question 42

Example: coin toss sequence expected time until a sequence e is completed.

Answer 42

Assuming a fair coin. Find expected number of tosses up to and including first occurrence of

THT(HT)

This is a delayed renewal process requiring mean time to first renewal ie B’(1).

1) work out v_n =P( renewal at time n)

v₀ = v₁ = v₂ = 0
v_n = 1/8
n is bigger or equal to 3

v(s) = Σ from n=3 to infinity
Of v_n•S^n = (1/8)(s³/(1-s))

2) work out u_n=P( renewal at time t+n | renewal at time t)
u₀ =1 convention

u₁ =0, u₂=1/14
Since after a renewal another if next two HT: u_n =1/8 for n bigger than or equal to 3.

U(s) = Σ u_n•s^n = 1+ (1/4)s² + (1/8)s³/(1-s)

Using V(s) =B(S)U(s)
B(s) = (s²)/( 8-8s+ 2s^2 -s³)

Expected time until first renewal differentiate with respect to a and a=1

B’(1) = 10