To login with Google, please enable popups

or

Don’t have an account? Sign up

To signup with Google, please enable popups

or

Sign up with Google or Facebook

or

By signing up I agree to StudyBlue's

Terms of Use and Privacy Policy

Already have an account? Log in

Reminder

Edit a Copy

Study these flashcards

- United-kingdom
- University of Bristol
- Mathematics
- Mathematics 20008
- Yu
- Ch3: Markov Chains In Discrete Time

Harry W.

• 12

cards
Markov Chain

Let X = {X}_{n∈N} be a discrete time, discrete space stochastic process.

1. X is a **Markov chain** if for each fixed n and each i_{0}, ..., i_{n+1}∈S

P(X_{n+1}= i_{n+1} | X_{n}= i_{n}, ..., X_{0}= i_{0}) = P(X_{n+1}= i_{n+1} | X_{n}= i_{n})

Conditional on the present, the future is independent of the past.

2. Furthermore, X is **time-homogenous** i,j∈S, P(X_{n+1}= j | X_{n}= i) depends only on i and j (not on n).

In this case, we define: p_{ij} = P(X_{n+1}= j | X_{n}= i).

Transition Matrix

The **transition matrix** of a Markov Chain is the matrix P with ijth entry p_{ij}. If S = {0, 1, 2, ..., M}:

P = ( p_{00} p_{01} ... p_{0M} )

( p_{10} p_{01} ... p_{0M} )

( ... ... ... ... )

( p_{M0} p_{M1} ... p_{MM} )

Since the p_{ij} are probabilities, and since the process must be in some state at time 1, P is a transition matrix if:

1. p_{ij} > 0, ∀i,j∈S, and

2. Σ_{j∈S}p_{ij} = 1, ∀i∈S (rows sum to 1)

These conditions are the defining conditions for P to be a stochastic process.

Chapman-Kolmogorov Equations

For any i,j∈S, and n∈N and any r = {0, ..., n}:

p_{ij}(n) = Σ_{k∈S }p_{ik}(r)p_{kj}(n-r).

Communicators and Intercommunicators

Let i,j∈S:

1. We say i communicates with j written i → j, if ∃n≥0 s.t p_{ij}(n) > 0.

2. We say i intercommunicates with j written i ↔ j,if i → j and j → i.

Equivalence Relation

↔ is an equivalence relation.

Intercommunication implies Recurrance

Suppose i ↔ j. Then i is recurrent iff j is recurrent.

Closed, Irreducible and Absorbing States

Unique Partitioning of State Spaces

Stationary Distributions

Computational complexity of dynamic programming

Aperiodic Chains

Stationary Distribution and the Limiting behaviour of p_{ij}(n) as n→∞

Sign up for free and study better.

Anytime, anywhere.

Get started today!

Find materials for your class:

Download our app to study better. Anytime, anywhere.