Theory of Stochastic Processes Lecture 13: Review (partially solved ... sei/lec/ Theory of Stochastic Processes Lecture 13: Review (partially solved problems) Tomonari SEI July 13, 2017 Solutions to a part of recommended problems are given.

  • Published on
    07-Feb-2018

  • View
    214

  • Download
    0

Embed Size (px)

Transcript

  • 1

    Theory of Stochastic Processes

    Lecture 13: Review (partially solved problems)

    Tomonari SEI

    July 13, 2017

    Solutions to a part of recommended problems are given.

    Lecture 8: Markov chain Monte Carlo

    Problem 6.5.1 By induction, we obtain

    i =0 i11 i

    0.

    Thenipi,i+1 =

    0 i1 i

    0 = i+1pi+1,i, i = 0, . . . , b 1.

    For other pairs (i, j), i 6= j, ipij = 0 = jpji. Therefore the chain is reversible.

    Problem 6.5.8 Suppose P is reversible. Let be the stationary distribution and D be thediagonal matrix with diagonal entries . Then S = DP is a symmetric matrix by definition

    of reversibility. We obtain P = D1 S.

    Conversely, suppose P = DS = (diSij). Define i = (1/di)/

    k(1/dk). Then ipij =

    idiSij = Sij/

    k(1/dk) is symmetric. Therefore P is reversible.

    Next suppose P = DS. Let T = D1/2PD1/2. Then T has the same eigenvalues as P .

    Since T = D1/2SD1/2 is symmetric, the eigenvalues are real.

    Finally, consider a transition matrix

    P =

    13 13 + 13 13

    13

    13

    13

    13

    13 +

    , ( 13 , 13 ).The stationary distribution is = ( 13 ,

    13 ,

    13 ). The chain is not reversible unless = 0. On the

    other hand, P has the real eigenvalues 1, , 0.

  • Lecture 13: Review

    Lecture 9: Stationary processes

    Problem 2 The process is represented as

    Xn = g(L)Zn, g(z) = (1 1z pzp)1.

    Since all the roots of 1 1z pzp = 0 are outside of the unit circle, g(z) has theconvergence radius greater than 1. Then the spectral density is given by

    f() =12

    |g(ei)|2 = 12|1

    pj=1 ie

    ij|2.

    by Theorem 2 of the lecture note of Lecture 9.

    Problem 4 (i) Since A and B have the mean zero, the mean of Xn is

    E[Xn] = E[A cos(n) + B sin(n)] = 0.

    Since E[A2] = E[B2] = 1 and E[AB] = 0, the covariance of Xn and Xn+m is

    E[XnXn+m] = E[cos(n) cos((n + m))] + E[sin(n) sin((n + m))]

    =1

    0

    (cos(n) cos((n + m)) + sin(n) sin((n + m))) d

    =1

    0

    cos(m)d =

    {1 if m = 0,0 otherwise.

    Therefore Xn is the white noise. In particular, it is stationary.

    (ii) We have X0 = A, X1 + X1 = 2A cos(), and X1 X1 = 2B sin(). The first twoequations determine A and . If 6= 0 and 6= , then the third equation determines B andtherefore all Xn are determined. Even if = 0 or = , Xn = A cos(n) is determined.

    Problem 5 For real numbers v1, . . . , vN ,N

    j=1

    Nk=1

    vjvkc(j k) =N

    j=1

    Nk=1

    vjvkE[XjXk] = E[(N

    j=1 vjXj

    )2] 0.

    Hence the matrix C = {c(j k)} is non-negative definite*1. All the eigenvectors of C aregiven by vm = (N1/2e2imn/N )Nn=1 for m = 0, . . . , N 1. Indeed,

    (Cvm)k = N1/2N

    n=1

    c(k n)e2imn/N

    = N1/2e2imk/NN

    j=1

    c(j)e2imj/N , j = n k,

    = Nf(m)(vm)k,

    *1 The assumption c(n) = c(n N) is not necessary here.

    2

  • Lecture 13: Review

    where f(m) = N1N1

    n=0 c(n)e2imn/N . The spectral decomposition of C is C =N1

    m=0 Nf(m)vmvm and therefore

    c(j k) =N1m=0

    Nf(m)(vm)j(vm)k =N1m=0

    f(m)e2im(jk)/N .

    Problem 6 (i) It is easy to see that E[X] = N1

    n E[Xn] = . Furthermore,

    V [X] = E[(X )2] = N2N

    j=1

    Nk=1

    E[(Xj )(Xk )]

    = N2N

    j=1

    Nk=1

    2(j k)

    = N2N1

    n=(N1)

    (j,k):jk=n

    2(n)

    = 2N1N1

    n=(N1)

    (1 |n|/N)(n).

    (ii)

    E[2] = N1N

    n=1

    E[(Xn X)2] = N1N

    n=1

    E[((Xn ) (X ))2]

    = N1N

    n=1

    {E[(Xn )2] 2E[(Xn )(X )] + E[(X )2]

    }= N1

    {N2 2NE[(X )2] + NE[(X )2]

    }= 2 V [X].

    (iii) By (i) and Abels theorem (or monotone convergence theorem), we have

    limN

    NV [X] = limN

    N1n=(N1)

    (1 |n|/N)(n) =

    n=(n) = f(0).

    In particular, limN V [X] = 0. By (ii), we also have

    limN

    E[2] = limN

    (2 V [X]) = 2.

    3

  • Lecture 13: Review

    Lecture 10: Martingales

    Problem 12.1.3 E[Zn+1n1|Fn] = E[Zn+1|Zn]n1 = (Zn)n1 = Znn.E[Zn+1 |Fn] = E[Zn+1 |Zn] = G()Zn = Zn , where G is the generating function of Z1

    Problem 12.1.5 E[(Yk Yj)Yj ] = E[E[Yk Yj |Fj ]Yj ] = E[(Yj Yj)Yj ] = 0.E[(Yk Yj)2|Fi] = E[Y 2k |Fi] 2E[E[Yk|Fj ]Yj |Fi] + E[Y 2j |Fi] = E[Y 2k |Fi] E[Y 2j |Fi].Suppose that E[Y 2n ] K for all n. Since E[(Yn Ym)2] = E[Y 2n ] E[Y 2m] for m < n, E[Y 2n ]is non-decreasing. Therefore there exists limn E[Y 2n ] K. In particular, for any > 0,there exists n0 such that |E[Y 2n ] E[Y 2m]| < for all n,m n0. Then E[(Yn Ym)2] =E[Y 2n ] E[Y 2m] < . Therefore Yn is a Cauchy sequence and converges in mean square*2.

    Problem 12.1.6 By Jensens inequality, we have

    E[u(Yn+1)|Fn] u(E[Yn+1|Fn]) = u(Yn).

    This means u(Yn) is a submartingale. The processes |Yn|, Y 2n , Y +n are submartingales sincefunctions u(y) = |y|, y2, y+ = max(0, y) are convex, respectively.

    Problem 12.2.1 We apply McDiarmids inequality. Let f((v1, w1), . . . , (vn, wn)) be the max-imum worth when the volume and worth of the i-th object are vi and wi. If an object (vi, wi)

    is replaced with (vi, wi), then f changes at most M . Indeed, after the i-th object is removed if

    necessary, the total cost is reduced at most M while the packed objects are feasible. Therefore

    f((v1, w1), . . . , (vi, wi), . . . , (vn, wn)) M f((v1, w1), . . . , (vi, wi), . . . , (vn, wn))

    and

    f((v1, w1), . . . , (vi, wi), . . . , (vn, wn)) M f((v1, w1), . . . , (vi, wi), . . . , (vn, wn)).

    Now, McDiarmids inequality implies that

    P (|Z E[Z]| nM) 2 exp(n2/2), > 0.

    Let x = nM to obtain

    P (|Z E[Z]| x) 2 exp(x2/(2nM2)), x > 0.

    *2 Here we used the completeness property of L2. This was beyond the scope of this lecture..

    4

  • Lecture 13: Review

    Lecture 11: Queues

    Problem 8.4.1 (a) Let X1, X2, X3 be the service time of the two customers and you. Denotethe teller you chose by Z = 1, 2. Denote the exponential density function by f(x) = ex.

    Then the probability we want is

    p =12P (X1 + X3 > X2|Z = 1) +

    12P (X1 < X2 + X3|Z = 2)

    =12

    x1+x3>x2

    f(x1)f(x2)f(x3)dx1dx2dx3 +12

    x1 X2) + P (X1 > X2, X1 < X2 + X3)

    =

    ( + )2+

    ( + )2.

    In particular, p(a) > p(b) > p(c).

    Problem 11.2.3 The waiting time W of a customer arriving at time 0 is the sum of servicetime of the Q(0) people. Let X1, . . . , Xn be the service time of the Q(0) = n customers. Since

    Q(0) has the stationary distribution, we have

    P (W > x) =

    n=1

    (1 )nP (X1 + + Xn > x), x 0.

    Since Xi has the exponential distribution with parameter , the distribution of X1 + +Xnis the gamma distribution. Therefore

    P (X1 + + Xn > x) =

    x

    ntn1

    (n 1)!etdt.

    5

  • Lecture 13: Review

    and

    P (W > x) =

    x

    n=1

    (1 )n ntn1et

    (n 1)!dt

    =

    x

    (1 )

    ( n=1

    (t)n1

    (n 1)!

    )etdt, = ,

    = (1 )

    x

    e()tdt

    = (1 )e()x

    = e()x.

    We have P (W x) = 1 e()x. In particular, P (W = 0) = P (W 0) = 1 .

    Problem 11.3.1 The problem is to determine the mean of Q(D). By Theorem 13.3.5 ofPRP, the generating function of Q(D) is given by

    G(s) = (1 )(s 1) MS((s 1))s MS((s 1))

    ,

    where MS() is the moment generating function of a typical service time. In this problem,

    the service time is the constant d. Therefore MS() = ed, and

    G(s) = (1 )(s 1) e(s1)d

    s e(s1)d= (1 )(s 1) e

    (s1)

    s e(s1),

    where = d is used. The mean length of Q(D) is G(1). By Taylors expansion around

    s = 1, we obtain

    G(1 + r) = (1 )r 1 + r + O(r2)

    1 + r 1 r 122r2 + O(r3)

    = (1 ) 1 + r + O(r2)

    1 122r + O(r2)

    = 1 +(

    +12

    2

    1

    )r + O(r2)

    = 1 +12

    (2 )1

    r + O(r2).

    Hence G(1) = 12(2 )/(1 ).

    6

  • Lecture 13: Review

    Lecture 12

    Problem 2 Typo: the definition of Z should be Z =N

    i=1 bi1(Wti Wti1).Denote Z = ZN and Ft = {Ws}st. By induction,

    E[ZN ] = E[ZN1 + bN1(WtN WtN1)]= E[Zn1] + E[bN1E[WtN WtN1 |FtN1 ]]= E[Zn1]

    = E[Z0] = 0.

    Similarly,

    V [ZN ] = E[(ZN1 + bN1(WtN WtN1))2]= E[E[(ZN1 + bN1(WtN WtN1))2|FtN1 ]]= E[Z2N1 + b

    2N1(tN tN1)]

    =N

    i=1

    E[b2i1](ti ti1).

    Problem 4 The OU process is represented as

    Xt = et(

    X0 + t

    0

    esdWs

    ).

    Thus, given X0 = x, the mean is E[Xt] = etx 0 as t , and the variance is

    V [Xt] = E[(Xt etx)2]

    = 2e2tE

    [( t0

    esdWs

    )2]

    = 2e2t t

    0

    e2sds (Ito isometry)

    = 21 e2t

    2

    2

    2(t ).

    Thus N(0, 2/(2)) must be the stationary distribution. Indeed, if X0 N(0, 2/(2)),then Xt = et(X0 +

    t0

    esdWs) is the sum of independent random variables having

    N(0, e2t2/(2)) and N(0, 2(1 e2t)/(2)). Therefore Xt N(0, 2/(2)).

    Problem 5 (a) d(W 3t ) = 3W 2t dWt + 3Wtdt. Thus W 3t = 3 t0

    W 2s dWs + 3 t0

    Wsds.

    (b) dF (Wt) = f(Wt)dWt + (1/2)f (Wt)dt. Thus F (Wt) = t0

    f(Ws)dWs + (1/2) t0

    f (Ws)ds.

    7

  • Lecture 13: Review

    Problem 7 For any f : Rd R, we have

    E[df(Xt)] = E

    i

    (if)dXi(t) + (1/2)i,j

    (ijf)(dXi(t))(dXj(t))

    = E

    i

    (if)i + (1/2)i,j

    (ijf)

    a

    iaja

    dtBy using E[f(Xt)] =

    f(y)p(t, y)dy and the integral-by-parts formula, we have

    f(y)tpdy =

    f(y)

    i

    (ip) + (1/2)i,j

    ij{

    a

    iajap}

    dy.Since f is arbitrary, the result follows.

    Problem 9 The drift term is

    =12g

    (log

    g

    )+

    12

    g

    (1

    g

    )=

    12g

    (

    g

    2g

    ) g

    4g2=

    2g g

    2g2

    The diffusion term is = 1/

    g. Then the right hand side of the forward equation is

    () + 12(2) =

    (

    2g g

    2g2

    )+

    12

    (

    g

    )=

    (

    2g g

    2g2

    )+

    12

    (

    g g

    g2

    )= 0.

    8