Esercizi di Processi Stocastici

Formattazione del testo

X X2 −= k p kpk kk=0 k=02 2 ′− −= EX EX = EX ϕ (1),2 ′ ′′from which we get that EX = ϕ (1) + ϕ (1). But this is enough for var X, since 22 2 ′ ′′ ′− − .var X = EX (EX) = ϕ (1) + ϕ (1) ϕ (1)45. {1, } ∪ {∞}A random variable X with values in 2, . . . , has generating functionp 2− −1 1 4pqz ,ϕ(z) = 2qz43≥where p, q 0 and p + q = 1.∞).(i) Compute P (X = (Consider all possible values of p).∞)(ii) For those values of p for which P (X = = 0 compute EX.Solution. ∞) −(i) As it was found above, P (X = = 1 ϕ(1), and particularly√ pq−− − |p −− , p < q11 1 q|1 4pq∞) − − −P (X = = 1 ϕ(1) = 1 =1 = ≥0, p q2q 2q1∞) ≥ . The expected value of X is given by(ii) It follows that P (X = = 0 for p 2 1 12, p >′ p−qEX = ϕ (1) = 1∞, p = 2and we are done.46. You can go up the stair

by climbing 1 or 2 steps at a time. There are n steps in total. In how many ways can you climb all steps?

Hint 1: If n = 3, you can reach the 3rd step by climbing 1 at a time, or 2 first and 1 next, or 1 first and 2 next, i.e. there are 3 ways.

Hint 2: if w is the number of ways to climb m steps, how is w related to w_m-1 and w_m-2?
Hint 3: Consider the generating function Σw_ms^m.

Solution:
Hence, w_m = w_m-1 + w_m-2, m ≥ 2. (1)
Here, step 0 means being at the bottom of the stairs. So w₀ = 1, w₁ = 1.
So w₂ = w₁ + w₀ = 2, w₃ = w₂ + w₁ = 3, w₄ = w₃ + w₂ = 5, w₅ = w₄ + w₃ = 8, w₆ = w₅ + w₄ = 13, ...

How do we find a formula for w_n? Here is where generating functions come to the rescue.

Let X(s) = Σw_ms^m, m ≥ 0 be the generating function of (w_m, m ≥ 0). Then the generating function equation (1) becomes:

function of (w , m 0) ism m+1X m −1 −w s = s (W (s) w )m+1 0m≥0 44 ≥and the generating function of (w , m 0) ism+2X m −2 − −w s = s (W (s) w sw ).m+2 0 1m≥0From the recursion ≥w = w + w , m 0m+2 m+1 m(obtained from (10) by replacing m by m + 2) we have (and this is were linearity is≥used) that the generating function of (w , m 0) equals the sum of the generatingm+2≥ ≥functions of (w , m 0) and (w , m 0), namely,m+1 m−2 −1− − −s (W (s) w sw ) = s (W (s) w ) + W (s). (11)0 1 0Since w = w = 1, we can solve for W (s) and find0 1 −1 .W (s) = 2 −s + s 1Essentially, what generating functions have done for us is to transform the LIN-(10) (11).EAR recursion into the ALGEBRAIC equation This is something youhave learnt in your introductory Mathematics courses. The tools and recipesassociated with LINEARITY are indispensable for anyone who does anythingof value. Thus, keep them always in your bag of

tricks.The question we ask is: ≥Which sequence (w , n 0) has generating function W (s)?n 2 −We start by noting that the polynomial s + s 1 has two roots:√√ − −5 1)/2, b = (−1 5)/2.a = (2 − − Hence s + s 1 = (s a)(s b), and so, by simple algebra, 1 11 −W (s) = .− − −b a s a s bWrite this as b a1 − .W (s) = − − −b a bs ab as ab−1,Noting that ab = we further have 1 1ab − .W (s) = − −b a 1 + bs b a 1 + asP P∞ ∞1 1n nBut = (−bs) , = (−as) , and so W (s) is the generating functionn=0 n=01+bs 1+asof b an n− ≥w = (−b) (−a) , n 0.n − −b a b aThis can be written also as √√ n+1 n+1− −5) 5)(1(1 + √w =n n+1 52which is always an integer (why?) 4547. Consider a branching process starting with Z = 1 and branching mechanism0−p = 1 p, p = p.1 2(Each individual gives birth to 1 or 2

children with probability 1−p or p, respectively.)

Let Z be the size of the n-th generation. Compute the probabilities P (Z = k) forn nZ , and the mean size ofall possible values of k, the generating function ϕ (z) = Ez nnthe n-th generation m = EZ . Do the computations in whichever order is convenientn nfor you. The mean number of offspring of a typical individual is

Solution. −m := (1 p) + 2p = 1 + p.

Therefore n nEZ = m = (1 + p) .n−

Let q = 1 p. To compute P (Z = 4), we consider all possibilities to have 4 children2in the second generation. There is only one possibility:2Therefore P (Z = 4) = p .2To compute P (Z = 3) we have2and so P (Z = 3) = pqp + ppq.2For P (Z = 2) we have2 2and so P (Z = 2) = qp + pq2And for P (Z = 1) there is only one possibility,2 2and so P (Z = 2) = q .2You can continue in this manner to compute P (Z = k), etc.3The generating function of the branching mechanism is2 2ϕ(z) = p z + p z = qz + pz .1 146ZSo ϕ (z) = Ez = ϕ(z). Next, we have ϕ

1. The probability of ultimate extinction is ε = 1/2.
2. The mean size of the n-th generation is given by the derivative of the generating function at z=1, i.e. &phi'(1).
3. The standard deviation of the size of the n-th generation is given by the square root of the second derivative of the generating function at z=1, i.e. sqrt(&phi''(1)).

k=n−1′′We here have m = 11/10, ϕ (1) = 4/10. But then 2n−2X k n 2n2 2′′ ′′ −− m + m mσ = var Z = ϕ (1) + EZ (EZ ) = ϕ (1)n n nn n k=n−1 n −m 1n−1 n 2n′′ −= ϕ (1)m + m m−m 1n −4 1mn−1 n n− −= m m (m 1)10 1/10n−1 n n n− − −= 4m (m 1) m (m 1)n−1 n− −= (4 m)m (m 1) n−1 n11 1129 − 1= 10 10 10Of course, the standard deviation is the square root of this number.

49. Consider the same branching process as above, but now start with Z = m, an arbi-0trary positive integer. Answer the same questions.

(i) The process behaves as the superposition of N i.i.d. copies of theSolution.previous process. This becomes extinct if and only if each of the N copies becomesextinct and so, by independence, the extinction probability isN Nε = (1/2) .

(ii) The n-th generation of the new process is the sum of the

populations of the n-th generations of each of the N constituent processes. Therefore the mean size of the n-th generation is n nN m = N (11/10) .

(iii) For the same reason, the standard deviation of the size of the n-th generation is √N σ.n50. Show that a branching process cannot have a stationary distribution π with π(i) > 0 for some i > 0. 48 ≤

If the mean number m of offspring is 1 then we know that the process will

Solution.

become extinct for sure, i.e. it will be absorbed by state 0. Hence the only stationary distribution satisfies ≥π(0) = 1, π(i) = 0, i 1.

If the mean number m of offspring is > 1 then we know that the probability that it∞) −

will become extinct is ε < 1, i.e. P (τ = = 1 ε > 0. But we showed in Part1 0 i∞) −(i) of Problem 8 above that P (τ = = 1 ε > 0 for all i. Hence the process is i 0

transient. And so there is NO stationary distribution at all.

51. Consider the

We showed in another problem that the chain is irreducible and recurrent.

Let us now see if it is positive recurrent. In other words, let us see if E[T] < ∞ for some (and thus all) i.