Math Is Fun Forum
  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

#1 2015-12-20 02:26:35

Agnishom
Real Member
From: Riemann Sphere
Registered: 2011-01-29
Posts: 24,769
Website

Absorbing Markov Chains reloaded

A game takes place in discrete "rounds".

In the beginning, a player is given 3 lives. At each round, he may either loose, with a 10% chance, and loose a life. Or, he may win, in which case, he gains a life. However, the last rule never lets him gain more than 3 lives.

The game ends when a player reaches 0 lives.

Calculate the expected number of rounds the player plays using an absorbing markov model


'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
I'm not crazy, my mother had me tested.

Offline

#2 2015-12-20 02:51:24

Relentless
Member
Registered: 2015-12-15
Posts: 624

Re: Absorbing Markov Chains reloaded

I am very ignorant of higher maths and will be unable to shed much light on this problem, but just to get the ball rolling I think it's clear that it must be more than 12 (since there is greater than a 50% chance of winning the first 6 and that guarantees a minimum 12).

Last edited by Relentless (2015-12-20 03:00:24)

Offline

#3 2015-12-20 15:53:28

Agnishom
Real Member
From: Riemann Sphere
Registered: 2011-01-29
Posts: 24,769
Website

Re: Absorbing Markov Chains reloaded

Hmm..

I think the answer is close to 1000


'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
I'm not crazy, my mother had me tested.

Offline

#4 2015-12-20 15:57:42

Relentless
Member
Registered: 2015-12-15
Posts: 624

Re: Absorbing Markov Chains reloaded

I suppose I'm right then. lol

Offline

#5 2015-12-20 16:39:35

Agnishom
Real Member
From: Riemann Sphere
Registered: 2011-01-29
Posts: 24,769
Website

Re: Absorbing Markov Chains reloaded

You are.

The correct answer is 1020.

chain = DiscreteMarkovProcess[
   4, {{1, 0, 0, 0}, {0.1, 0, 0.9, 0}, {0, 0.1, 0, 0.9}, {0, 0, 0.1, 
     0.9}}];

Mean[FirstPassageTimeDistribution[chain, {1}]]

'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
I'm not crazy, my mother had me tested.

Offline

#6 2015-12-20 21:00:03

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Absorbing Markov Chains reloaded

So what did you need help with?

I will ask you some questions from the point of view given by EM:

1) How certain are you that you have the correct answer?

2) If I said that answer was incorrect, or that M was not getting the right answer, what would you reply?


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#7 2015-12-20 23:09:56

Agnishom
Real Member
From: Riemann Sphere
Registered: 2011-01-29
Posts: 24,769
Website

Re: Absorbing Markov Chains reloaded

The answer agrees with a sim and an analytical approach


'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
I'm not crazy, my mother had me tested.

Offline

#8 2015-12-21 05:43:12

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Absorbing Markov Chains reloaded

That is correct and so is the answer.


The expected time to absorption is given by t where the starting states are rows (shown in the first column).

B is the probability of ending in some absorbing state (first row) starting in some transient state (first column).



In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#9 2016-10-08 22:51:54

Matir
Member
Registered: 2016-10-08
Posts: 22

Re: Absorbing Markov Chains reloaded

Do we really need Markov chains for this problem? Plain algebra should be enough.

Offline

#10 2016-10-08 22:55:25

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Absorbing Markov Chains reloaded

In this thread there is no chatter, I am from Missouri, so you are going to have to show it else the comment is removed. But remember this thread is for computer math so you must use computer math.

http://www.mathisfunforum.com/viewtopic.php?id=15250

Agnishom's solution in post #5 is the only solution because it uses Mathematica.


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#11 2016-10-09 01:04:28

Matir
Member
Registered: 2016-10-08
Posts: 22

Re: Absorbing Markov Chains reloaded

This is the set of equations you'll need,

is the number of rounds you should survive with
lives.

Plugging into Wolfram|Alpha / pen+paper gives:
http://www.wolframalpha.com/input/?i=R3 … 2B9R2%2F10

I guess you should accept that my head is a (not too good!) computer...

Offline

#12 2016-10-09 03:02:16

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Absorbing Markov Chains reloaded

The Markov chain does all that automatically. But you do have another solution so congratulations! Very good.

Can you please introduce yourself in Introductions.


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

Board footer

Powered by FluxBB