So, about this math problem...

[apsuman]

What you just said is this: there are 100 rooms. I put the dragon in one at random. Thus, there is 1 in 100 chance that the dragon is in any given room.

Yes, that is what I said.

I went to the trouble of posting some assumptions so that later posters could tell me why I was wrong and even refute my assumptions if they needed to.

However, and please take this for the humor intended, I did answer the question: "what are the odds of him being in any room at some given time?"

If you have X rooms, say 100, the odds of him being in any one room is 1/x, or 1/100.

Now I think we can both agree that the original poster wanted to know how to solve these problems in general, not in one specific narrow example.

But answering that question will require knowing a few more things, like the map of rooms, how often he moves, etc.

Now, if anyone wants to tell me knowing the map is not necessary, I am all ears.


g!

 

[Altamont Ravenard]

Reminds me of my course in Stochastic Processus (have a bachelor's degree in math (that I don't use), but all I'm remembering at this moment are vague notions and headaches after headaches after headaches... good times...)

AR

 

[Saeviomagy]

Yes, that is what I said.

If you have X rooms, say 100, the odds of him being in any one room is 1/x, or 1/100.

Well, no, it's not.

As T->infinity, the chance of the dragon being in a given room will become proportional to the number of entrances that room has. Prior to that, it'll be proportional to the number of ways that the dragon could have ended up in that room.

It's never going to be a flat 1/100 unless the initial drop room was random and every single room has the same number of entrances.

 

[Clear Dragon]

A smart dragon would cast Quantum Polymorph, and become delocalized over his entire lair (this being the lowest energy state). His wavefunction would then collapse into a particular room only when some annoying party of adventures attempted to find outwhere he is (measuring his postition) and he could then eat them at his leisure.

 

[The Sigil]

Jeez, FyreHowl... us dorks are having fun with math here!

After trying a few randomly-created networks, it appears Sigil's intuition is correct for the general case, and that the general case is not nearly as chaotic as I thought.

To wit: The probability P(i) of the dragon being in room i is equal to the number of connections attached to room i, C(i), divided by twice the total number of connections.

UNLESS there are no rings in the network with an odd number of rooms, in which case the probabilities are bistable, and you need to (1) determine which rooms are separated by an odd number of steps from the starting room, and which are separated by an even number of steps, then (2) apply the same formula, separately to each set of rooms.

Intuitively, I came up with the same answer a few minutes after my post above - by which time our internet connection at work had been severed by the local SBC crew. :b

I expressed it as M/N where M is the number of "entrances to the room" and N is the total number of entrances to all rooms (in case you have a funny "one-way" movement method such as a teleporter), since a "one-way" passage does not need to be double-counted as a connection. (I figured since this is fantasy, a "one-way" move is a possibility).

I didn't prove it, but it looked intuitively correct and the math works out (i.e., Probability across all rooms sums to one) so I was fine to assert it was so. As you mentioned, there are two cases to consider - one with a "bistable" solution (of steps only from point A to point B regardless of path is always odd or always even) and one "stable" solution (where the number of steps from point A to point B can be odd or even depending on which path you take). To the layman...

If you have no case where you can move one step at a time from Point A to Point B to Point C to Point A, you have a "bistable" solution and will have one set of probabilities for all the "even" rooms and one set for all the "odd" rooms (i.e., rooms that are reached from the start in an even/odd number of steps). No room will be in both the "Even" and "Odd" sets... your solution is then for t=odd it is M(odd)/N(odd) and for t=even it is M(even)/N(even). If you DO have any point where you can move from A-B-C-A then it's "general" solution of M/N at any time t.

--The Sigil

 

[apsuman]

Well, no, it's not.

As T->infinity, the chance of the dragon being in a given room will become proportional to the number of entrances that room has. Prior to that, it'll be proportional to the number of ways that the dragon could have ended up in that room.

It's never going to be a flat 1/100 unless the initial drop room was random and every single room has the same number of entrances.

Every time I assume something, I get myself in trouble.

The original question was: "Given some pattern of movement (for example,once every minute the dragon moves through a random exit in the room he's in) what are the odds of him being in any room at some given time?"

Now I assume the dragon is in the cave.

The odds of him being in any room are 100%

Now if we take the original question to mean: "What are the odds of me picking the room he is in?" I think the answer to that question is 1/100, as it is simply a random selecton problem.

If the original question is : "How do I solve the problem of determining the probability of occupying a given room X in map matrix M over a period of T, given a restlessness period of Z with the following caveats determining movement..." Then my answer is completely out and many others have answered the question.

But to actually be able to answer the question that way you must know the Map, right?

g!

 

[BlackMoria]

This is precisely the reason why I am grateful that I don't have a mathematican or statistican at my game table.

 

[Olgar Shiverstone]

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---6
1-0---1---0---0---0---0
2-.33-----.33-.33--0---0
3-.5--0---0---0---.5---0
4-0--.5---0---0---.5---0
5-0---0--.33-.33---0--.33
6-0---0---0---0---1---0

Given 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 probabilities

There 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.

 

[The Sigil]

If the original question is : "How do I solve the problem of determining the probability of occupying a given room X in map matrix M over a period of T, given a restlessness period of Z with the following caveats determining movement..." Then my answer is completely out and many others have answered the question.

But to actually be able to answer the question that way you must know the Map, right?

g!

The original question seems to be, "at a given time T, what are the odds of the dragon being in room X in map matrix M, after starting from point Y, with a restlessness period of Z?"

Where T is very small (a few multiples of Z), it is quite important to analyze the structure of matrix M, especially as it refers to Y and X. However, this analysis is relatively easy and straightforward and does not need a general solution.

As T gets very large (many multiples of Z), the starting point Y becomes less important except that the number of steps between Y and X is important (though not Y and X themselves; merely their separation) to determine whether this is a bistatial problem. Once we've determined that, the solution is only trivially different than the (possibly bistatial) M/N solution I posited earlier. You are welcome to run the numbers yourself for *any* matrix M that you like and see that it is indeed the correct solution.

Another way to think about the importance of the starting point is to handle the problem "in reverse" - if the dragon is at X now what are the odds he was at Y a few Z's ago? Obviously, the fewer Z's, the fewer possible solutions. As the number of "steps backwards" gets larger, the possible number of permutations gets larger and larger until you get (quickly, I might add) to a point where you have no real certainty of where the starting point was. Thus, for a time elapsed that is large since the start, the starting point is of little import.

Simply put, this is a problem that DOES have a simple general case. The *only* thing that matters in terms of the structure of M is whether that structure demands a bistatial solution.

--The Sigil

 

[apsuman]

The original question seems to be, "at a given time T, what are the odds of the dragon being in room X in map matrix M, after starting from point Y, with a restlessness period of Z?"

[stuff deleted]

--The Sigil

Yes, I agree.

However, just in case the original poster was asking a trick question, I wanted to have my bases covered.

[humor]
Now, I agree with virtually everything you posted and Olgar in the immediate previous post. But, given that this is a very old dragon, no doubt he has many many teleport spells and dimention door, and gate, and magic items similar. So his matrix has him potentially going from one room to any other room.
[/end humor]

g!