CH1 Flashcards
Markov Property
P(X(n+1)=i((n+1)I(X(0)=i(0),……))=P(X(n+1)=i(n+1)IX(n)=i(n)))
Homogeneous
Does not depend on n
Distribution Requirements
lamda(i)>0
Sum of lamda=1
Ext. Markov Property
P(F I Xn=i,H)=P(F I Xn=i)
p(ij)(m+n)=
Chapman-Kolmogorov
SUM(k) of p(ik)(m)p(kj)(n)
Defn: i leads to j
there exist n st p(ij)(n)>0
If i leads to j and vv:
they communicate
Defn: Irreducible
Only one communicating class
Defn: Closed
p(ij)=0 i in C, j not in C
Defn: First Passage Time T(j)
min{n>=1:X(n)=j}
Defn: First Passage Probability f(ij)(n)
Pi(T(j)=n)
Defn: Recurrent state
Pi(Ti
Thm1: i recurrent iff:
SUM(n) of p(ii)(n)=inf
Defn: P(ij)(s)=
SUM(n) of p(ij)(n)s^n
Defn: F(ij)(s)=
SUM(n) of f(ij)(n)s^n
P(ij)(s)=
d(ij)+F(ij)(s)P(jj)(s)
for -1
Thm2: i is recurrent iff
SUM(n) p(ii)(n)=inf
Thm: C comm class, then:
i) all states trans, or all states recur. and
ii) if recur, C closed
Random Walk Recurrent for which dimensions?
1,2 only
Stirling’s Formula
sqrt(2pin)n^ne^-n
Defn: Hitting Time
H^A of A in S
min{n>=0:Xn in A}
h(i)^A=
Pi(H^A
Thm: vect {h(i)^A:i in S} satis:
{1 if i inA
{SUM(j) p(ij)h(j)^A if i not in A
Thm: vect{k(i)^A:i in S} satis:
{0 if i in A
{1+SUM(j)p(ik)k(j)^A