Upgrade your account to a Community Supporter account and remove most of the site ads.

Reply to thread

Message: <blockquote data-quote="Olgar Shiverstone" data-source="post: 1207462" data-attributes="member: 5868">How many rooms do you actually need a solution for?This is a fairly simple Markov chain problem; for a simple combination, there are formulas that allow you to derive the steady-state probabilities directly.For a 100-room problem, you need some computing power (we're not talking paper & pencil here, since you've got a 100 x 100 matrix).  Luckily, most of the entries in the matrix are zero since from a given room you can't get to many other rooms -- a little playing around with the system of equations and you should be able to get a computer solution for the steady-state probabilities.It's probably still more work than you want to go through, though -- what exactly are you traying to achieve (maybe there's another way to approach the problem)?EDIT:For your six-room example, given above, the Markov chain matrix is given by (forgive formatting):--1---2---3---4---5---61-0---1---0---0---0---02-.33-----.33-.33--0---03-.5--0---0---0---.5---04-0--.5---0---0---.5---05-0---0--.33-.33---0--.336-0---0---0---0---1---0Given the matrix above P, the probability of the dragon being in a given room after the nth move is P^n (martix multiplication -- in the resulting matrix, cross reference the starting room with the target room to get the probability of being in the target room after n steps.).  With n high enough, you start to approach steady-state probabilitiesThere aren't any absorbing states (which would make direct calculation easier), but by solving a system of six equations for the six unknown steady state probabilities p(i) you can calculate the steady state probability of being in a room.the system is given by:P(i) = Sum (p(i) * P),so P(1) = .33 P(2) + .5 P(3)P(2) = P(1) + .5 P(4)P(3) = .33 P(2) + .33 P(5)P(4) = .33P(2)+ .33 P(5)P(5) = .5P(3)+.5P(4)+P(6)P(6) = .33P(5)Solve the above, and you get the steady-state chance of being in a given room a time approaches infinity (though the chances of being in a given room at the nth step depend on where you started and n -- see my note on P^n above).If you've followed that (I'm compressing a lot of Markov theory) you can extend it to any number of rooms, though the computing power required increases quite a bit.EDIT 2: And I see this has already essentially been posted ... apologies for redundancy.</blockquote>

Verification