Construct a Markov Chain: How to Generate Xn's Using the Sequence U0, U1, ...?

In summary: U is generated. Depending on U's value, you may remain at 1, or switch to 2, or switch to s. That is what your Step 2 needs to say. It needs to say what the conditional probabilities are. It is not clear that you have thought about that, let alone how to express them.I think you are trying to say something like this:Step 2:If Xn-1 = 1 Let Xn = 1 with probability ν1P11 Let Xn = k with probability ν1P1k for 2 ≤ k ≤ sElse if Xn-1 = k for 2 ≤ k ≤ s Let X
  • #1
fignewtons
28
0

Homework Statement


Describe the construction of a Markov chain X0, X1, ... on Ω ∈ (0, 1) with state space S = {1, 2, ..., s} and S X S PTM P and initial state X0 ~ ν (probabilities distributed like vector ν). Use the sequence U0, U1, ... to generate the Xn's

Homework Equations


U0, U1 is a sequence of iid random variables (numbers between 0 and 1)
ν = (ν1, ν2, ..., νs)

The Attempt at a Solution


Step 1:
let X0 = 1 if U0 ≤ v1
let X0 = 2 if ν1< U0 ≤ v2...
more generally let X0 = s if νs-1< U0 ≤ vs
Set n = 1
Step 2:
If Xn-1 = 1 let Xn=1 if Un ≤ νP11...
let Xn=s if νP1(s-1) < Un ≤ νP1s
... more generally
If Xn-1 = s let Xn=1 if Un ≤ νPs1...
let Xn=s if νPs(s-1) < Un ≤ νPss
Step 3:
Increase n by 1 and repeat 2)
Please let me know if this makes sense.
 
Physics news on Phys.org
  • #2
figNewtons said:

Homework Statement


Describe the construction of a Markov chain X0, X1, ... on Ω ∈ (0, 1) with state space S = {1, 2, ..., s} and S X S PTM P and initial state X0 ~ ν (probabilities distributed like vector ν). Use the sequence U0, U1, ... to generate the Xn's

Homework Equations


U0, U1 is a sequence of iid random variables (numbers between 0 and 1)
ν = (ν1, ν2, ..., νs)

The Attempt at a Solution


Step 1:
let X0 = 1 if U0 ≤ v1
let X0 = 2 if ν1< U0 ≤ v2...
more generally let X0 = s if νs-1< U0 ≤ vs
Set n = 1
Step 2:
If Xn-1 = 1 let Xn=1 if Un ≤ νP11...
let Xn=s if νP1(s-1) < Un ≤ νP1s
... more generally
If Xn-1 = s let Xn=1 if Un ≤ νPs1...
let Xn=s if νPs(s-1) < Un ≤ νPss
Step 3:
Increase n by 1 and repeat 2)
Please let me know if this makes sense.

Please clarify. You seem to be using the symbol ##v## in two distinct ways: (1) as a vector ##v = (v_1, v_2, \ldots, v_s)##; and (ii) as some mysterious, undefiined parameter in the conditions ##X_n = 1## if ##U_n \leq v P_{11}##, etc.
 
  • #3
Ray Vickson said:
Please clarify. You seem to be using the symbol ##v## in two distinct ways: (1) as a vector ##v = (v_1, v_2, \ldots, v_s)##; and (ii) as some mysterious, undefiined parameter in the conditions ##X_n = 1## if ##U_n \leq v P_{11}##, etc.

The vector is meant to symbolise the initial state distribution (the probability of being in any state s in the beginning is is vi...vs). I am using the fact that any state in the future is the product of the initial state and a power of the PTM νP
 
  • #4
figNewtons said:
The vector is meant to symbolise the initial state distribution (the probability of being in any state s in the beginning is is vi...vs). I am using the fact that any state in the future is the product of the initial state and a power of the PTM νP

Yes, I understand that ##vP## is a row-vector with components ##(vP)_j = \sum_i v_i P_{ij}, j=1,2,\ldots, s##. However, ##vP_{11}## is the row-vector ##(v_1 P_{11}, v_2 P_{11}, \ldots, v_s P_{11})##, and saying that the scalar ##U_n## be ##\leq## that vector makes no sense.
 
  • #5
Ray Vickson said:
Yes, I understand that ##vP## is a row-vector with components ##(vP)_j = \sum_i v_i P_{ij}, j=1,2,\ldots, s##. However, ##vP_{11}## is the row-vector ##(v_1 P_{11}, v_2 P_{11}, \ldots, v_s P_{11})##, and saying that the scalar ##U_n## be ##\leq## that vector makes no sense.
How would it be better written? How would you have written the steps?
 
  • #6
figNewtons said:
How would it be better written? How would you have written the steps?

I don't know, since I have no idea what you are actually trying to say in those steps.

Step 1 is OK, and is written in more-or-less standard form; it is the later steps that are mysterious.

Suppose ##X_t=1## and we generate a uniform U(0,1) random number ##U##. In plain, understandable terms, how do we use ##U## to decide whether ##X_{t+1} = 1## or ##X_{t+1} = 2## ##\ldots## or ##X_{t+1} = s##?

After figuring out what is needed, then worry about how to represent it in appropriate notation.
 
  • #7
Ok trying to modify step 2:
figNewtons said:
Step 2:
If Xn-1 = 1 let Xn=1 if Un ≤ νP11...
let Xn=s if νP1(s-1) < Un ≤ νP1s
... more generally
If Xn-1 = s let Xn=1 if Un ≤ νPs1...
let Xn=s if νPs(s-1) < Un ≤ νPss

Step 2:
If Xn-1 = 1 let Xn = 1 if Un ≤ ν1P111
...more generally
If Xn-1 = s let Xn = 1 if Un ≤ νsPsss
 
  • #8
Ok trying to modify step 2:
figNewtons said:
Step 2:
If Xn-1 = 1 let Xn=1 if Un ≤ νP11...
let Xn=s if νP1(s-1) < Un ≤ νP1s
... more generally
If Xn-1 = s let Xn=1 if Un ≤ νPs1...
let Xn=s if νPs(s-1) < Un ≤ νPss

Step 2:
If Xn-1 = 1 let Xn = 1 if Un ≤ ν1P111
let Xn=s if ν1P1(s-1) < Un ≤ ν1P1s
...more generally
If Xn-1 = s let Xn = 1 if Un ≤ νsPss1
let Xn = s if νsPs(s-1) < Un ≤ νsPsss
 
  • #9
figNewtons said:
Ok trying to modify step 2:Step 2:
If Xn-1 = 1 let Xn = 1 if Un ≤ ν1P111
let Xn=s if ν1P1(s-1) < Un ≤ ν1P1s
...more generally
If Xn-1 = s let Xn = 1 if Un ≤ νsPss1
let Xn = s if νsPs(s-1) < Un ≤ νsPsss

Your construction fails to simulate a Markov chain. The fundamental property of a Markov process is that P{future | present & past} = P{future | present}.

That is the "memoryless" property: given the present condition of the system, the past is irrelevant from now on. So at time t = 1 the past is wiped out: if you are at ##X_1 = 1## it does not matter how you arrived there, or how probable it was to arrive. You have arrived; you are there. So, the location of next state ##X_2## is governed by the probability mass function ##\{ P_{11}, P_{12}, \ldots P_{1s} \}##. Note that I am assuming you are using the common convention of having the rows of ##P## summing to 1 (rather than the columns, which is a much less common convention that I have also seen from some writers). So, you have a legitimate probability distribution, because ##P_{11} + P_{12} + \cdots + P_{1s} = 1##. At this point the values of ##v_1, v_2, \ldots, v_s## are no longer relevant; they just govern how likely it will be that you start off in some state. They have no relevance to what happens once you are, indeed, at some one of the states.
 
  • #10
Ray Vickson said:
Your construction fails to simulate a Markov chain. The fundamental property of a Markov process is that P{future | present & past} = P{future | present}.

That is the "memoryless" property: given the present condition of the system, the past is irrelevant from now on. So at time t = 1 the past is wiped out: if you are at ##X_1 = 1## it does not matter how you arrived there, or how probable it was to arrive. You have arrived; you are there. So, the location of next state ##X_2## is governed by the probability mass function ##\{ P_{11}, P_{12}, \ldots P_{1s} \}##. Note that I am assuming you are using the common convention of having the rows of ##P## summing to 1 (rather than the columns, which is a much less common convention that I have also seen from some writers). So, you have a legitimate probability distribution, because ##P_{11} + P_{12} + \cdots + P_{1s} = 1##. At this point the values of ##v_1, v_2, \ldots, v_s## are no longer relevant; they just govern how likely it will be that you start off in some state. They have no relevance to what happens once you are, indeed, at some one of the states.

Ok I think I see what you're saying. So a revised version would be:

Step 2:
If Xn-1 = 1 let Xn = 1 if Un ≤ P11...
let Xn=s if P1(s-1) < Un ≤ P1s
...more generally
If Xn-1 = s let Xn = 1 if Un ≤ Ps1
...let Xn = s if Ps(s-1) < Un ≤ Pss

Please let me know if this takes into account the memoryless property or if it can be expressed in better notation
 
  • #11
figNewtons said:
Ok I think I see what you're saying. So a revised version would be:

Step 2:
If Xn-1 = 1 let Xn = 1 if Un ≤ P11...
let Xn=s if P1(s-1) < Un ≤ P1s
...more generally
If Xn-1 = s let Xn = 1 if Un ≤ Ps1
...let Xn = s if Ps(s-1) < Un ≤ Pss

Please let me know if this takes into account the memoryless property or if it can be expressed in better notation

The notation is OK now, but you still leave too much to the imagination. You need to expand a bit on your statement that, when ##X_{n-1}=1## you have ##X_n = 1 ## if ##U_n \leq P_{11} \; \ldots##. What are a couple of additional conditions? I mean, suppose ##U_n > P_{11}##; what then? When can you get ##X_n = 2## or ##X_n = 3##, etc.?
 
  • #12
Ray Vickson said:
The notation is OK now, but you still leave too much to the imagination. You need to expand a bit on your statement that, when ##X_{n-1}=1## you have ##X_n = 1 ## if ##U_n \leq P_{11} \; \ldots##. What are a couple of additional conditions? I mean, suppose ##U_n > P_{11}##; what then? When can you get ##X_n = 2## or ##X_n = 3##, etc.?

I thought I generalised them after the "..." but I can be more specific. So a revised version would be:

Step 2:
If Xn-1 = 1 let Xn = 1 if Un ≤ P11
let Xn=2 if P11 < Un ≤ P12
let Xn=3 if P12 < Un ≤ P13
...
let Xn=s if P1(s-1) < Un ≤ P1s
...more generally
If Xn-1 = s let Xn = 1 if Un ≤ Ps1
let Xn = 2 if Ps1 < Un ≤ Ps2
let Xn = 3 if Ps2 < Un ≤ Ps3
...let Xn = s if Ps(s-1) < Un ≤ Pss

Please let me know if this is what you mean by more specific conditions.
 
  • #13
figNewtons said:
I thought I generalised them after the "..." but I can be more specific. So a revised version would be:

Step 2:
If Xn-1 = 1 let Xn = 1 if Un ≤ P11
let Xn=2 if P11 < Un ≤ P12
let Xn=3 if P12 < Un ≤ P13
...
let Xn=s if P1(s-1) < Un ≤ P1s
...more generally
If Xn-1 = s let Xn = 1 if Un ≤ Ps1
let Xn = 2 if Ps1 < Un ≤ Ps2
let Xn = 3 if Ps2 < Un ≤ Ps3
...let Xn = s if Ps(s-1) < Un ≤ Pss

Please let me know if this is what you mean by more specific conditions.

Yes, but the more specific conditions are incorrect. Google "generating discrete random variables" or something similar, to see what you must do.
 
  • #14
Ok after some more research I tried.

Step 2:
If Xn-1 = 1 let Xn = 1 if Un ≤ P11
let Xn=2 if P11 < Un ≤ P11 + P12
let Xn=3 if P11 + P12 < Un ≤ P11 + P12 + P13
...
let Xn=s if P11 + P12 + ... + P1(s-1) < Un ≤ 1
...more generally
If Xn-1 = s let Xn = 1 if Un ≤ Ps1
let Xn = 2 if Ps1 < Un ≤ Ps1 + Ps2
let Xn = 3 if Ps1 + Ps2 < Un ≤ Ps1 + Ps2 + Ps3
...
let Xn = s if Ps1 + Ps2 + ... + Ps(s-1) < Un ≤ 1

I think earlier my intervals didn't make sense since I didn't add up the probabilities. Does this make more sense now?
 
  • #15
figNewtons said:
Ok after some more research I tried.

Step 2:
If Xn-1 = 1 let Xn = 1 if Un ≤ P11
let Xn=2 if P11 < Un ≤ P11 + P12
let Xn=3 if P11 + P12 < Un ≤ P11 + P12 + P13
...
let Xn=s if P11 + P12 + ... + P1(s-1) < Un ≤ 1
...more generally
If Xn-1 = s let Xn = 1 if Un ≤ Ps1
let Xn = 2 if Ps1 < Un ≤ Ps1 + Ps2
let Xn = 3 if Ps1 + Ps2 < Un ≤ Ps1 + Ps2 + Ps3
...
let Xn = s if Ps1 + Ps2 + ... + Ps(s-1) < Un ≤ 1

I think earlier my intervals didn't make sense since I didn't add up the probabilities. Does this make more sense now?

Yes, it is OK now. But, looking back I see you made the same error in Step 1, so that needs fixing as well.
 
  • #16
Ok fixed it.

Step 1:
let X0 = 1 if U0 ≤ ν1
let X0 = 2 if ν1 < U0 ≤ ν1 + ν2
...
more generally let X0 = s if ν1 + ν2 + ... + νs-1 < U0 ≤ ν1 + ν2 + ... + νs-1 + νs
set n = 1

Step 2:
If Xn-1 = 1 let Xn = 1 if Un ≤ P11
let Xn=2 if P11 < Un ≤ P11 + P12
let Xn=3 if P11 + P12 < Un ≤ P11 + P12 + P13
...
let Xn=s if P11 + P12 + ... + P1(s-1) < Un ≤ P11 + P12 + ... + P1(s-1) + P1s
...more generally
If Xn-1 = s let Xn = 1 if Un ≤ Ps1
let Xn = 2 if Ps1 < Un ≤ Ps1 + Ps2
let Xn = 3 if Ps1 + Ps2 < Un ≤ Ps1 + Ps2 + Ps3
...
let Xn = s if Ps1 + Ps2 + ... + Ps(s-1) < Un ≤ Ps1 + Ps2 + ... + Ps(s-1) + Pss

Step 3:
increase n by 1 and return to 2)
 
  • #17
figNewtons said:
Ok fixed it.

Step 1:
let X0 = 1 if U0 ≤ ν1
let X0 = 2 if ν1 < U0 ≤ ν1 + ν2
...
more generally let X0 = s if ν1 + ν2 + ... + νs-1 < U0 ≤ ν1 + ν2 + ... + νs-1 + νs
set n = 1

Step 2:
If Xn-1 = 1 let Xn = 1 if Un ≤ P11
let Xn=2 if P11 < Un ≤ P11 + P12
let Xn=3 if P11 + P12 < Un ≤ P11 + P12 + P13
...
let Xn=s if P11 + P12 + ... + P1(s-1) < Un ≤ P11 + P12 + ... + P1(s-1) + P1s
...more generally
If Xn-1 = s let Xn = 1 if Un ≤ Ps1
let Xn = 2 if Ps1 < Un ≤ Ps1 + Ps2
let Xn = 3 if Ps1 + Ps2 < Un ≤ Ps1 + Ps2 + Ps3
...
let Xn = s if Ps1 + Ps2 + ... + Ps(s-1) < Un ≤ Ps1 + Ps2 + ... + Ps(s-1) + Pss

Step 3:
increase n by 1 and return to 2)

Looks good now.
 

1. What is a Markov chain?

A Markov chain is a mathematical model that describes a system that transitions from one state to another based on a set of probabilities. It is used to analyze and predict the behavior of systems that have a random or unpredictable nature, such as stock prices, weather patterns, and human behavior.

2. How do you construct a Markov chain?

To construct a Markov chain, you first need to define the states of the system and determine the probabilities of transitioning from one state to another. These probabilities can be estimated from historical data or determined using mathematical methods. Once the probabilities are determined, they are organized into a transition matrix, which represents the Markov chain.

3. What are some applications of Markov chains?

Markov chains have numerous applications in various fields, including finance, economics, biology, and physics. Some common applications include stock market analysis, weather forecasting, speech recognition, and predictive text algorithms. They are also used in machine learning and artificial intelligence for pattern recognition and decision-making processes.

4. What are the limitations of Markov chains?

One of the limitations of Markov chains is that they assume the system being modeled is memoryless, meaning the future state only depends on the current state and not on the past states. This may not always hold true in real-world scenarios. Additionally, the accuracy of the predictions made by a Markov chain heavily depends on the quality and quantity of the data used to construct it.

5. Can a Markov chain have an infinite number of states?

Yes, a Markov chain can have an infinite number of states, although in practice, it is often limited to a finite number of states for easier analysis. In some cases, a continuous-time Markov chain may also be used, where the states are represented by a continuous variable rather than a discrete one.

Similar threads

Markov Chain - Time Reversibility proof
    • Calculus and Beyond Homework Help
Replies
3
Views
1K
Limit of a continuous time Markov chain
    • Calculus and Beyond Homework Help
Replies
8
Views
2K
Finding conditional and joint probabilities from a table of data
    • Programming and Computer Science
Replies
1
Views
1K
A Martingale, calculation of probability - Markov chain needed?
    • Set Theory, Logic, Probability, Statistics
Replies
3
Views
1K
Solving Markov Chain Problem: Probability of Infection
    • Calculus and Beyond Homework Help
Replies
2
Views
2K
B How can hyperreal numbers make infinitesimals logically sound in calculus?
    • Calculus
Replies
24
Views
3K
Markov processes (Weight Suspended equally by n Cables)
    • Precalculus Mathematics Homework Help
Replies
4
Views
750
Is X(n) a Markov Sequence?
    • Calculus and Beyond Homework Help
Replies
2
Views
1K
I A seemingly simple problem about probability
    • Set Theory, Logic, Probability, Statistics
Replies
13
Views
1K
Markov Chain Homework: Expressing Transition Matrix P in Terms of G
    • Calculus and Beyond Homework Help
Replies
1
Views
3K

Hot Threads

Recent Insights

Back
Top