Markov Chain Watch

NotNotBatman
  • Community Assistant
Badges: 20
Rep:
?
#1
Report Thread starter 4 weeks ago
#1
 c_n is the cumulative number of rolls of a die up to time n, with state space {0,1,2,...}.
 c_0 = 0.

I need to find out the probability that 9 or 10 get mentioned (in all the different paths).

So I started thinking about the no. of ways 9 can get mentioned for up to 9 rolls. I.e. number of ways in 9 rolls is 9, in 8 rolls is 8, I'm not sure how to carry this process on and find a succinct way of working it out.
0
reply
ghostwalker
  • Study Helper
Badges: 15
#2
Report 4 weeks ago
#2
(Original post by NotNotBatman)
 c_n is the cumulative number of rolls of a die up to time n, with state space {0,1,2,...}.
 c_0 = 0.

I need to find out the probability that 9 or 10 get mentioned (in all the different paths).

So I started thinking about the no. of ways 9 can get mentioned for up to 9 rolls. I.e. number of ways in 9 rolls is 9, in 8 rolls is 8, I'm not sure how to carry this process on and find a succinct way of working it out.
As no one else has responded:

May not be able to help, but as it stands I can't even follow your question.

It reads to me as if you roll a die (presumably standard 6-sided), and the cumulative number of rolls up to time n, is simply n rolls. I doubt that's what you intend, but it's the only way I can interpret what you'lve written.

Then you talk about number of ways 9 can get mentioned. What does "9 gets mentioned" mean?
reply
NotNotBatman
  • Community Assistant
Badges: 20
Rep:
?
#3
Report Thread starter 4 weeks ago
#3
(Original post by ghostwalker)
As no one else has responded:

May not be able to help, but as it stands I can't even follow your question.

It reads to me as if you roll a die (presumably standard 6-sided), and the cumulative number of rolls up to time n, is simply n rolls. I doubt that's what you intend, but it's the only way I can interpret what you'lve written.

Then you talk about number of ways 9 can get mentioned. What does "9 gets mentioned" mean?
 c_n is the cumulative score, of rolls up to time n.

So if we have paths of cumulative scores c_n(\omega_i), for instance I've considered, the path
 c_1(\omega_1) =1, c_2(\omega_1) =2, c_3(\omega_1) =3, \cdots c_9(\omega_1)=9, \cdots that is, getting a score of 1, for the first 9 rolls, then after that it doesn't matter. I'm trying to work out the probability of 9 or 10 appears in any path  \omega_i (the different ways the scores can appear)
I know that at least two rolls are required. that is  c_1(\omega_i) = 6 followed by c_1(\omega_i) = 3 or the other way around, for some path  \omega_i
0
reply
ghostwalker
  • Study Helper
Badges: 15
#4
Report 4 weeks ago
#4
(Original post by NotNotBatman)
 c_n is the cumulative score, of rolls up to time n.

So if we have paths of cumulative scores c_n(\omega_i), for instance I've considered, the path
 c_1(\omega_1) =1, c_2(\omega_1) =2, c_3(\omega_1) =3, \cdots c_9(\omega_1)=9, \cdots that is, getting a score of 1, for the first 9 rolls, then after that it doesn't matter. I'm trying to work out the probability of 9 or 10 appears in any path  \omega_i (the different ways the scores can appear)
I know that at least two rolls are required. that is  c_1(\omega_i) = 6 followed by c_1(\omega_i) = 3 or the other way around, for some path  \omega_i
Can't see a particularly easy way to do it. Matlab would help.

If you're going to do it via transition matrices, then:

Since you're not interested in anything greater than 10, your states could be {0,1,...,9,10,>10}

Then the probability would be the sum of the third & second to last two elements of the state vector, from:

(T^9+T^8+... T)(1,0,...0)^T or the other way around - vaguely recall there was something different about Markov transition matrices

But you'll need to adjust for getting 9 at stage n and 10 at stage n+1, as these would be double counted.

Don't know if that's any use to use,...
Last edited by ghostwalker; 4 weeks ago
reply
DFranklin
Badges: 18
Rep:
?
#5
Report 4 weeks ago
#5
(Original post by ghostwalker)
Can't see a particularly easy way to do it. Matlab would help.

If you're going to do it via transition matrices, then:

Since you're not interested in anything greater than 10, your states could be {0,1,...,9,10,>10}

Then the probability would be the sum of the third & second to last two elements of the state vector, from:

(T^9+T^8+... T)(1,0,...0)^T or the other way around - vaguely recall there was something different about Markov transition matrices

But you'll need to adjust for getting 9 at stage n and 10 at stage n+1, as these would be double counted.

Don't know if that's any use to use,...
My knowledge of Markov chains is very much "practical" (as in ways to solve maths puzzles and similar rather than theoretial), but I think you can do a little better here.

Make the states 0, 1, 2, 3, ..., 8 (as before), and then "got 9 or 10" and then "skipped 9 or 10" (which you might as well still call > 10). So "9 or 10" and ">10" are both 'stuck states' (is the formal term absorbing?) (i.e. p(9 or 10 -> 9 or 10) = p(>10 -> >10) = 1). Building the transition matrix M is going to be a little tedious, but your final result will just be the "9 or 10" element of M^10 (1 0 0 0 ... 0)^T.
2
reply
ghostwalker
  • Study Helper
Badges: 15
#6
Report 4 weeks ago
#6
(Original post by DFranklin)
My knowledge of Markov chains is very much "practical" (as in ways to solve maths puzzles and similar rather than theoretial), but I think you can do a little better here.

Make the states 0, 1, 2, 3, ..., 8 (as before), and then "got 9 or 10" and then "skipped 9 or 10" (which you might as well still call > 10). So "9 or 10" and ">10" are both 'stuck states' (is the formal term absorbing?) (i.e. p(9 or 10 -> 9 or 10) = p(>10 -> >10) = 1). Building the transition matrix M is going to be a little tedious, but your final result will just be the "9 or 10" element of M^10 (1 0 0 0 ... 0)^T.
Indeed, somewhat better, completely avoiding the fiddly double counting and summation. PRSOM.
reply
Gregorius
Badges: 14
Rep:
?
#7
Report 4 weeks ago
#7
(Original post by NotNotBatman)
 c_n is the cumulative number of rolls of a die up to time n, with state space {0,1,2,...}.
 c_0 = 0.

I need to find out the probability that 9 or 10 get mentioned (in all the different paths).

So I started thinking about the no. of ways 9 can get mentioned for up to 9 rolls. I.e. number of ways in 9 rolls is 9, in 8 rolls is 8, I'm not sure how to carry this process on and find a succinct way of working it out.
Tricky little question this, if you're to avoid awkward algebra. One of the wrinkles here is that if you start counting trajectories that include your targets 9 or 10, then it's not entirely clear what the denominator should be to get a probability. So, I'd calculate probabilities directly using a decomposition of the problem. I'll outline a simpler version and leave the rest to you!

The probability of the chain ever hitting 9 is just the sum of the probabilities of hitting 9 after exactly n throws, for n = 1 though to infinity. But most of these terms are zero, and we're left with the sum from 2 to 9. So, calculate (or just look up)

(i) The probability of landing on 9 in exactly 2 throws.
(ii) The probability of landing on 9 in exactly 3 throws.
(iii) etc.

Then add them up.
1
reply
DFranklin
Badges: 18
Rep:
?
#8
Report 4 weeks ago
#8
(Original post by Gregorius)
Tricky little question this, if you're to avoid awkward algebra. One of the wrinkles here is that if you start counting trajectories that include your targets 9 or 10, then it's not entirely clear what the denominator should be to get a probability. So, I'd calculate probabilities directly using a decomposition of the problem. I'll outline a simpler version and leave the rest to you!

The probability of the chain ever hitting 9 is just the sum of the probabilities of hitting 9 after exactly n throws, for n = 1 though to infinity. But most of these terms are zero, and we're left with the sum from 2 to 9. So, calculate (or just look up)

(i) The probability of landing on 9 in exactly 2 throws.
(ii) The probability of landing on 9 in exactly 3 throws.
(iii) etc.

Then add them up.
I have to admit, I'm not seeing a pleasant way of calculating, say, the probability of landing on 9 in exactly 5 throws.
(Original post by NotNotBatman)
I'm not sure how to carry this process on and find a succinct way of working it out.
OK, so I've actually done this (with computer), and I actually think this is fairly doable by hand.

Suppose after n throws, we have a_0, a_1, ..., a_8, a_9, a_{9+10}, a_{>10} as the number of ways of being in each state (states as described in previous post). And suppose we want to find b_0, ..., b_{>10} as the number of ways (*) for each state after n+1 throws. (*) Note that we will throw even if in a "stuck" state, so our "way counting" reflects the correct probability.

Then b_0 = 0
b_1 = a_0,
b_2 = a_1+a_2
...
b_7 = a_1+a_2+...+a_6,
b_8 = a_2 + a_3 + .... + a_7,
b_{9+10} = (a_3+...+a_8) + (a_4+...+a_8) + 6b_{9+10}. (Note the multiply by 6 which corresponds to (*)).

The key observation here is that most of these values can be found incrementally from the one before. e.g. b_3 = b_2 + a_2, b_7 = b_6 + a_7, b_8 = b_7 + a_8 - a_1 etc.

So on average, it turns out only need to do about 1 operation to calculate each element in the next state vector (particularly given after k tosses the first k values in the vector are 0). So you just repeat this process until everything is in a stuck state.

Note that the formula for b_{>10} is significantly different from the others, and somewhat messier. If you are confident you have done everything correctly, note that you don't actually need this value: it's not needed to calculate the next state vector, and since the sum of all the b_i (after n+1) throws must add up to 6^{n+1} you can use this to calculate it at the end.

For a check, the answer I get is 0.477 to 3dp (edit: sorry, that's the probability of overshooting. So 1-0.477 would be the probability you actually want).
Last edited by DFranklin; 4 weeks ago
0
reply
theOldBean
Badges: 15
Rep:
?
#9
Report 4 weeks ago
#9
I'm not 100% sure about this, but if you let P(n) be the probability that n appears at some stage in the chain, then you can condition on the first roll to deduce P(n)=\frac{P(n-1)+\dots+P(n-6)}{6} . You could work out P(1),\dots,P(5) by hand and use this recurrence to find P(9), P(10). Then P(9 or 10)=P(9)+P(10)-P(9 and 10)=P(9)+P(10)-P(9)/6.

Edit: I think this is wrong sadly. Even conditioning on the first roll being a 3, P[103 appears] is not the same thing as P[100 appears], because the 3 would need to occur exactly after getting a score of 100. You could instead let P(n,m) be the probability of getting a score of n in m rolls, so that P[n,m]=(1/6)P[n-1,m-1]+...+P[n-6,m-1] but this too looks a bit messy.
Last edited by theOldBean; 4 weeks ago
0
reply
Gregorius
Badges: 14
Rep:
?
#10
Report 4 weeks ago
#10
(Original post by DFranklin)
I have to admit, I'm not seeing a pleasant way of calculating, say, the probability of landing on 9 in exactly 5 throws.
It's one of those standard tortures about generating functions for undergraduates in advanced elementary probability theory! See here for the details.
0
reply
DFranklin
Badges: 18
Rep:
?
#11
Report 4 weeks ago
#11
(Original post by Gregorius)
It's one of those standard tortures about generating functions for undergraduates in advanced elementary probability theory! See here for the details.
Not to flog a dead horse, but it seems that page pretty much wimps out on doing any calculations with more than 4 dice (the most likely roll for n dice is fairly obvious by symmetry anyhow).

If I *had* to find "the probability of landing on 9 in exactly 5 throws", I'd definitely do it by the same "run the recurrence relationship 5 (*) times" method I've described earlier.

(*) actually 4, as we might as well start with the vector (1,1,1,1,1,1, 0, 0, 0).
0
reply
DFranklin
Badges: 18
Rep:
?
#12
Report 4 weeks ago
#12
(Original post by ghostwalker)
Using your initial transition matrix method, I get the same - 0.523 (3 dec.pl), or \dfrac{52...22}{6^9}
Agreed (I just didn't want to give away the exact answer).
0
reply
Gregorius
Badges: 14
Rep:
?
#13
Report 4 weeks ago
#13
(Original post by DFranklin)
Not to flog a dead horse, but it seems that page pretty much wimps out on doing any calculations with more than 4 dice (the most likely roll for n dice is fairly obvious by symmetry anyhow).
The formula wanted is the one for "c" (probability of scoring p, throwing n s-sided dice), just a few lines into the working. It ends up being a simple calculation.
0
reply
DFranklin
Badges: 18
Rep:
?
#14
Report 4 weeks ago
#14
(Original post by Gregorius)
The formula wanted is the one for "c" (probability of scoring p, throwing n s-sided dice), just a few lines into the working. It ends up being a simple calculation.
Cheers - I had somewhat skimmed and the line at the end of the page: "Unfortunately, P(p_L,n,s) does not have a simple closed-form expression" somewhat misled me. And the expression for c isn't *that* simple to actually calculate.
0
reply
X

Quick Reply

Attached files
Write a reply...
Reply
new posts
Latest
My Feed

See more of what you like on
The Student Room

You can personalise what you see on TSR. Tell us a little about yourself to get started.

Personalise

University open days

  • University of Birmingham
    Postgraduate Open Day Postgraduate
    Wed, 20 Mar '19
  • King's College London
    Postgraduate Taught Courses - Arts & Sciences - Strand Campus Postgraduate
    Wed, 20 Mar '19
  • University of East Anglia
    All Departments Open 13:00-17:00. Find out more about our diverse range of subject areas and career progression in the Arts & Humanities, Social Sciences, Medicine & Health Sciences, and the Sciences. Postgraduate
    Wed, 20 Mar '19

Where do you need more help?

Which Uni should I go to? (33)
13.87%
How successful will I become if I take my planned subjects? (21)
8.82%
How happy will I be if I take this career? (50)
21.01%
How do I achieve my dream Uni placement? (34)
14.29%
What should I study to achieve my dream career? (29)
12.18%
How can I be the best version of myself? (71)
29.83%

Watched Threads

View All