Chapter 2 Flashcards

Question

U(s)

Answer 1

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

Answer 2

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

Answer 3

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

Answer 4

``` 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

Answer 5

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.

Answer 6

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

Answer 7

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

Answer 8

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

Answer 9

d=1 aperiodic Otherwise the process is Periodic with period d

Answer 10

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

Answer 11

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.

Answer 12

Clock times for delayed renewal process delay D D, D + T₁ , D +T₁ + T₂,... Renewal times stay the same...

Answer 13

* 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

Answer 14

The generating functions V(a) B(a) and F(a) are related by V(s) = ( B(s) ) / ( 1 - F(s) ) =B(s) • U(s)

Answer 15

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.

Answer 16

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)

Answer 17

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.

Answer 18

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

Chapter 2 Flashcards

(42 cards)