Chapter 2 Flashcards
Renewal
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
Lengths of time between renewals
Clock times for renewals
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
f_n in renewal theory: what is it
- if this applies then it’s a Renewal process
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
N_t
Renewals occurred up to and including time t
Eg number of bulbs replaced
f_n distribution and f
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
Defective probability distribution
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
Recurrent process
Recurrent process if f=1
If a renewal process is recurrent then renewals continue forever
Non-defective distribution
Null recurrent or positive recurrent
Transient process
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
Null recurrent renewal process
Null recurrent if
The mean of random variables T_i is NOT FINITE
(Recurrent must have f=1 sum of f_ns)
Positive recurrent renewal process
Positive recurrent if
The mean of random variables T_i if finite
(Recurrent must have f=1 sum of f_ns)
Deriving f_n for a problem
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
Generating functions: general definition
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
Probability generating function of distribution of X
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
Lemma 3: for independent X Y and their generating function
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
If F(S) is the GF if a non-defective prob dist
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
Finding the mean of a distribution:
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
Possibly defective distributions GF implies that
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
Examples of generating functions :
Not a distribution
Probability distribution
Binomial
Geometric
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.
Theorem 4 F(s) and U(s)
Generating functions F(S) and U(S) satisfy
U(S)
= 1/(1-F(S))
For 0 ≤ S < 1.
Proof: a specific event u_n …
(u_n)
(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.
u_n
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
Probabilities f_n in terms of events E₀, E₁,E₂,…
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
E_n
The event that a renewal takes place at clock time n =0,1,2,…
u_n in terms of f_n
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₁²
U(s)
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
Bernouilli trials with blocking
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
What does F(1) tell us
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
Theorem 4 relationship between U(s) and F(s) tells us about recurrence: summary
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
A simple random walk on the integers
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.
Theorem 5: simple random walk on the integers, when is it recurrent or transient
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
Theorem 6: simple random walk, recurrence properties null postitve
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
Period of a renewal process
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
Aperiodic renewal process
d=1 aperiodic
Otherwise the process is
Periodic with period d
Delay and delayed process
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
B(S)
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.
The clock times for a delayed renewal process
Clock times for delayed renewal process delay D
D, D + T₁ , D +T₁ + T₂,…
Renewal times stay the same…
Delayed process and new defined u_n
- 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
Theorem 7: after defining V(S) B(S) and F(S) for a delayed renewal process
The generating functions V(a) B(a) and F(a) are related by
V(s) = ( B(s) )
/
( 1 - F(s) )
=B(s) • U(s)
Example 6 sided die: event E_n that after n rolls total numbers of 1,2,3,4,5 and 6 are equal.
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.
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:
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)
Recurrent patterns
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.
Example: coin toss sequence expected time until a sequence e is completed.
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
