CH1 Flashcards

1
Q

Markov Property

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Homogeneous

A

Does not depend on n

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Distribution Requirements

A

lamda(i)>0

Sum of lamda=1

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Ext. Markov Property

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

p(ij)(m+n)=

Chapman-Kolmogorov

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Defn: i leads to j

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

If i leads to j and vv:

A

they communicate

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Defn: Irreducible

A

Only one communicating class

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Defn: Closed

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Defn: First Passage Time T(j)

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

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

A

Pi(T(j)=n)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Defn: Recurrent state

A

Pi(Ti

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Thm1: i recurrent iff:

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Defn: P(ij)(s)=

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Defn: F(ij)(s)=

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

P(ij)(s)=

A

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

for -1

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

Thm2: i is recurrent iff

A

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

18
Q

Thm: C comm class, then:

A

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

ii) if recur, C closed

19
Q

Random Walk Recurrent for which dimensions?

20
Q

Stirling’s Formula

A

sqrt(2pin)n^ne^-n

21
Q

Defn: Hitting Time

H^A of A in S

A

min{n>=0:Xn in A}

22
Q

h(i)^A=

23
Q

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

A

{1 if i inA

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

24
Q

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

A

{0 if i in A

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

25
Defn: Stopping Time T
If the event {T=n} is given in terms of Xo,...,Xn
26
Thm: Strong Markov Property
(X(T+k):k>=0) is a MC if | X is MC, T
27
Thm: IF Vi=mod({n>=1:Xn=i}) and | f(ii)=Pi(Ti
f(ii)^r(1-f(ii))
28
Defn: Mean Recurrence Time | mu(i)=Ei(Ti)=
{inf i trans | {SUM(n) nf(ii)(n) i recur
29
Defn: i null state if
i recurs and mu(i)=inf | otherwise i positive
30
Defn: Period d(i)=
gcd{n>=1:p(ii)(n)>0}
31
Defn: Aperiodic
if d(i)=1
32
Defn: Ergodic
if aperiodic and positive recurrent
33
Thm: If i coms j:
di=dj, (+ve) recurrence and ergodic for j iff for i
34
Prop: If X irred and j recur then:
P(Xn=j for some n)=1
35
Defn: Invariant Distrib.
piP=pi | pi(k)>=0, SUM(k) pi(k)=1
36
Thm: If X irred MC, then
There exist pi if some state +ve recurs | If pi exists, then all states +ve recur, and pi(i)=1/mu(i)
37
Thm: p(ik)(n) tends to:
pi(k) as n tends to inf
38
If X is +ve recur irred, and Xo=pi, then Yk= | has a trans matrix p'(i,j)
X(N-k) | pi(j)/pi(i))p(ji
39
Defn: irred MC X is reversible iff
pi(i)p(ij)=pi(j)p(ji) | the detailed balance eqn
40
Defn: (lamda,P) in detailed balance iff
lamda(i)p(ij)=lamda(j)p(ji)