CH1

Question 1

Markov Property

Answer 1

P(X(n+1)=i((n+1)I(X(0)=i(0),……))=P(X(n+1)=i(n+1)IX(n)=i(n)))

Question 2

Homogeneous

Answer 2

Does not depend on n

Question 3

Distribution Requirements

Answer 3

lamda(i)>0

Sum of lamda=1

Question 4

Ext. Markov Property

Answer 4

P(F I Xn=i,H)=P(F I Xn=i)

Question 5

p(ij)(m+n)=

Chapman-Kolmogorov

Answer 5

SUM(k) of p(ik)(m)p(kj)(n)

Question 6

Defn: i leads to j

Answer 6

there exist n st p(ij)(n)>0

Question 7

If i leads to j and vv:

Answer 7

they communicate

Question 8

Defn: Irreducible

Answer 8

Only one communicating class

Question 9

Defn: Closed

Answer 9

p(ij)=0 i in C, j not in C

Question 10

Defn: First Passage Time T(j)

Answer 10

min{n>=1:X(n)=j}

Question 11

Defn: First Passage Probability f(ij)(n)

Answer 11

Pi(T(j)=n)

Question 12

Defn: Recurrent state

Answer 12

Pi(Ti

Question 13

Thm1: i recurrent iff:

Answer 13

SUM(n) of p(ii)(n)=inf

Question 14

Defn: P(ij)(s)=

Answer 14

SUM(n) of p(ij)(n)s^n

Question 15

Defn: F(ij)(s)=

Answer 15

SUM(n) of f(ij)(n)s^n

Question 16

P(ij)(s)=

Answer 16

d(ij)+F(ij)(s)P(jj)(s)

for -1

Question 17

Thm2: i is recurrent iff

Answer 17

SUM(n) p(ii)(n)=inf

Question 18

Thm: C comm class, then:

Answer 18

i) all states trans, or all states recur. and

ii) if recur, C closed

Question 19

Random Walk Recurrent for which dimensions?

Answer 19

1,2 only

Question 20

Stirling’s Formula

Answer 20

sqrt(2pin)n^ne^-n

Question 21

Defn: Hitting Time

H^A of A in S

Answer 21

min{n>=0:Xn in A}

Question 22

h(i)^A=

Answer 22

Pi(H^A

Question 23

Thm: vect {h(i)^A:i in S} satis:

Answer 23

{1 if i inA

{SUM(j) p(ij)h(j)^A if i not in A

Question 24

Thm: vect{k(i)^A:i in S} satis:

Answer 24

{0 if i in A

{1+SUM(j)p(ik)k(j)^A

Question 25

Defn: Stopping Time T

Answer 25

If the event {T=n} is given in terms of Xo,…,Xn

Question 26

Thm: Strong Markov Property

Answer 26

(X(T+k):k>=0) is a MC if

X is MC, T

Question 27

Thm: IF Vi=mod({n>=1:Xn=i}) and

f(ii)=Pi(Ti

Answer 27

f(ii)^r(1-f(ii))

Question 28

Defn: Mean Recurrence Time

mu(i)=Ei(Ti)=

Answer 28

{inf i trans

{SUM(n) nf(ii)(n) i recur

Question 29

Defn: i null state if

Answer 29

i recurs and mu(i)=inf

otherwise i positive

Question 30

Defn: Period d(i)=

Answer 30

gcd{n>=1:p(ii)(n)>0}

Question 31

Defn: Aperiodic

Answer 31

if d(i)=1

Question 32

Defn: Ergodic

Answer 32

if aperiodic and positive recurrent

Question 33

Thm: If i coms j:

Answer 33

di=dj, (+ve) recurrence and ergodic for j iff for i

Question 34

Prop: If X irred and j recur then:

Answer 34

P(Xn=j for some n)=1

Question 35

Defn: Invariant Distrib.

Answer 35

piP=pi

pi(k)>=0, SUM(k) pi(k)=1

Question 36

Thm: If X irred MC, then

Answer 36

There exist pi if some state +ve recurs

If pi exists, then all states +ve recur, and pi(i)=1/mu(i)

Question 37

Thm: p(ik)(n) tends to:

Answer 37

pi(k) as n tends to inf

Question 38

If X is +ve recur irred, and Xo=pi, then Yk=

has a trans matrix p’(i,j)

Answer 38

X(N-k)

pi(j)/pi(i))p(ji

Question 39

Defn: irred MC X is reversible iff

Answer 39

pi(i)p(ij)=pi(j)p(ji)

the detailed balance eqn

Question 40

Defn: (lamda,P) in detailed balance iff

Answer 40

lamda(i)p(ij)=lamda(j)p(ji)