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

You are not logged in.

- Topics: Active | Unanswered

**lucik1900****Member**- Registered: 2013-03-15
- Posts: 12

A rat is released in the space outside a maze consisting of three rooms and six doors, as depicted in the following figure.

Whenever the rat is in a space or room with k doors, it chooses each of these doors to move through next with probability 1/k. We are interested in the movement of the rat from when it first enters the maze until it first leaves.

(a) If the rat enters the maze at Room 1, find the probability that it will leave

from Room 3.

(b) If the rat starts in the space around the maze, find the probability that it will

eventually leave the maze from Room 3.

(c) If the rat leaves the maze from Room 3 find the probability that it entered at

Room 1.

(d) Suppose that the rat is now in the maze and we gain information which

makes us 70% confident that it entered at Room 1 and 20% confident

that it entered at Room 2.

Find the probability that:

(i) the rat will leave from Room 3

(ii) the rat entered at Room 1 if it leaves from Room 3

(iii) the rat entered at Room 1 if it leaves from Room 1.

For (d) it may be assumed that had we known at which room the rat entered the maze,

the said additional information would not alter our beliefs regarding subsequent movements of the rat.

Please help me !!Thank you very much!

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 86,676

Hi;

(a) If the rat enters the maze at Room 1, find the probability that it will leave

from Room 3.

These are Markov chains but the terminology is confusing. What does it mean to leave from room 3. Does it mean to end up in the space or in room 2?

*Last edited by bobbym (2013-03-18 00:18:51)*

**In mathematics, you don't understand things. You just get used to them.Of course that result can be rigorously obtained, but who cares?Combinatorics is Algebra and Algebra is Combinatorics.**

Offline

**lucik1900****Member**- Registered: 2013-03-15
- Posts: 12

"We are interested in the movement of the rat from when it first enters the maze until it first leaves."

It should be "end up the space"

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 86,676

Hi;

So we start in the space and for this one we end up in the space.

**In mathematics, you don't understand things. You just get used to them.Of course that result can be rigorously obtained, but who cares?Combinatorics is Algebra and Algebra is Combinatorics.**

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 86,676

Hi;

*Last edited by bobbym (2013-03-18 06:33:29)*

**In mathematics, you don't understand things. You just get used to them.Of course that result can be rigorously obtained, but who cares?Combinatorics is Algebra and Algebra is Combinatorics.**

Offline

**lucik1900****Member**- Registered: 2013-03-15
- Posts: 12

Hi,

How do you get that?

could you please show me your working?

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 86,676

Hi;

Two ways, computer simulation and Absorbing Markov chain. There is a third way but I am unable to get it to work,

Of course that result can be rigorously obtained, but who cares?

Combinatorics is Algebra and Algebra is Combinatorics.

Offline

What are Markov Chains?

'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'

'Humanity is still kept intact. It remains within.' -Alokananda

**Online**

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 86,676

named after Andrey Markov, is a mathematical system that undergoes transitions from one state to another, between a finite or countable number of possible states. It is a random process usually characterized as memoryless: the next state depends only on the current state and not on the sequence of events that preceded it. This specific kind of "memorylessness" is called the Markov property. Markov chains have many applications as statistical models of real-world processes

As usual Wikipedia achieves new heights in turning something simple into something that only Einstein can understand.

To understand them you have to see them.

Of course that result can be rigorously obtained, but who cares?

Combinatorics is Algebra and Algebra is Combinatorics.

Offline

Hopefully not with a video

'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'

'Humanity is still kept intact. It remains within.' -Alokananda

**Online**

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 86,676

No, with a small example. I was just working on one that is tiny.

Of course that result can be rigorously obtained, but who cares?

Combinatorics is Algebra and Algebra is Combinatorics.

Offline

Will you please show me?

'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'

'Humanity is still kept intact. It remains within.' -Alokananda

**Online**

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 86,676

Markov chains are used i probability and you will need to understand matrices and vectors. If you do not, don't worry, just enjoy the show and it all will come later.

Lets say a city has 85% of its living in the city and 15% of the population lives in the suburbs. But each year 7% of the people in the city move to the suburbs but only 1% of the people in the suburbs move back to the city. Assuming that the total population remains constant ( suburbs + city ) what percentage of people will be in the city after 5 years?

How do we answer this question?

Of course that result can be rigorously obtained, but who cares?

Combinatorics is Algebra and Algebra is Combinatorics.

Offline

We calculate it one by one year stepwise

'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'

'Humanity is still kept intact. It remains within.' -Alokananda

**Online**

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 86,676

There is an easier way.

This is the initial state vector,

The transition matrix P is

Nothing amazing here just defining the terms.

We can strip away the labels and just leave the numbers.

To get the answer we just evaluate

To do that take this expression

{.85,.15}.MatrixPower({{.93,.07},{.01,.99}},5)

over to Wolfram and let me know what you get.

Of course that result can be rigorously obtained, but who cares?

Combinatorics is Algebra and Algebra is Combinatorics.

Offline

'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'

'Humanity is still kept intact. It remains within.' -Alokananda

**Online**

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 86,676

That is very good.

Remember how the A0 vector ( initial state vector ) was labelled?

That says the first element is the percentage in the city and the second element, the percentage in the suburbs.

Now your answer was

That says 60.28% are in the city and 39.71% are now living in the suburbs after 5 years.

Of course that result can be rigorously obtained, but who cares?

Combinatorics is Algebra and Algebra is Combinatorics.

Offline

Ok

'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'

'Humanity is still kept intact. It remains within.' -Alokananda

**Online**

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 86,676

This is a pretty dry example that only touches the surface of what they can do. A real problem would be much larger and more meaningful.

The OP's problem can be solved with Markov chains.

But at least you got to see a little bit of it.

Of course that result can be rigorously obtained, but who cares?

Combinatorics is Algebra and Algebra is Combinatorics.

Offline

Oh! So it is a way to do a chain of calculations quickly with matrices?

'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'

'Humanity is still kept intact. It remains within.' -Alokananda

**Online**

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 86,676

Yes, it is like condensing a whole tree down to just a box of numbers. Also it can contain a tree that has an infinite number of levels, branches and nodes. One that you could never draw...

Of course that result can be rigorously obtained, but who cares?

Combinatorics is Algebra and Algebra is Combinatorics.

Offline

How to setup the simulation for this problem?

'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'

'Humanity is still kept intact. It remains within.' -Alokananda

**Online**

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 86,676

Hi;

We can solve the problem using 2 linked recurrences:

I spoke to soon before, there might be a way to simulate this process. We will talk about it when I get back.

Of course that result can be rigorously obtained, but who cares?

Combinatorics is Algebra and Algebra is Combinatorics.

Offline

Sorry for the confusion, I meant : the simulation approach for the OP's problem

'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'

'Humanity is still kept intact. It remains within.' -Alokananda

**Online**

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 86,676

Which part? There are a lot of questions that the OP wanted answers to.

Of course that result can be rigorously obtained, but who cares?

Combinatorics is Algebra and Algebra is Combinatorics.

Offline