Markov Chains and Conditional Probability: Easy rat in the maze problem Why is the following soluti

Brock Byrd 2022-07-03 Answered
Markov Chains and Conditional Probability: Easy rat in the maze problem
Why is the following solution to this problem incorrect,
A rat is trapped in a maze with three doors and some hidden cheese. If the rat takes door one, he will wander around the maze for 2 minutes and return to where he started. If he takes door two, he will wander around the maze for 3 minutes and return to where he started. If he takes door three, he will ind the cheese after 1 minute. If the rat returns to where he started he immediately picks a door to pass through. The rat picks each door uniformly at random. How long, on average, will the rat wander before finding the cheese?
1. Construct a graph with three vertices: X, Y, Z, each of which represents a door in the original problem.
2. Add edges between every vertex, including self-loops, each of which has a weight of 1/3.
3. Take the stationary distribution to be (1/3, 1/3, 1/3). It is unique because the probability transition question for the graph in (1) is regular (i.e., its limit is just the same matrix with all entries equal to 1/3)
4. Compute the expected time as 21 / 3 + 31 / 3 + 1 1 / 3 = 2
The correct answer is 6. I know that the set-up is completely wrong and that I should use conditional probability, but is there a way to do it like this? The main issue is that we don't know the total time spent in the maze (this is kind of what we need to find) so I can see that it doesn't really make sense to take this approach.
You can still ask an expert for help

Want to know more about Discrete math?

Expert Community at Your Service

  • Live experts 24/7
  • Questions are typically answered in as fast as 30 minutes
  • Personalized clear answers
Learn more

Solve your problem for the price of one coffee

  • Available 24/7
  • Math expert for every subject
  • Pay only if we can solve it
Ask Question

Answers (1)

Perman7z
Answered 2022-07-04 Author has 13 answers
Step 1
The rat's sojourn time may be modeled by a Markov chain with transition matrix
P = ( 0 1 3 1 3 0 1 3 0 0 0 1 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 1 ) .
Let Q be the matrix whose entries are the expected number of visits to a transient state starting from another transient state, then since Q 1 = sup 1 i t j = 1 t Q i j = 2 3 < 1, the series
N = k = 0 Q k
converges to
( 3 2 1 2 3 3 1 3 3 3 2 3 3 2 1 3 ) .
Step 2
The expected number of steps before being absorbed when starting in a transient state are given by the entries of the vector
t = N 1 = ( 8 10 11 9 ) .
It follows that the expected soujourn time is 8.

We have step-by-step solutions for your answer!

Expert Community at Your Service

  • Live experts 24/7
  • Questions are typically answered in as fast as 30 minutes
  • Personalized clear answers
Learn more

You might be interested in

asked 2021-08-18
Discrete Mathematics Basics
1) Determine whether the relation R on the set of all Web pages is reflexive, symmetric, antisymmetric, and/or transitive, where (a,b)R if and only if
I) everyone who has visited Web page a has also visited Web page b.
II) there are no common links found on both Web page a and Web page b.
III) there is at least one common link on Web page a and Web page b.
asked 2021-08-15
How many elements are in the set { 0, { { 0 } }?
asked 2020-11-09
Use proof by Contradiction to prove that the sum of an irrational number and a rational number is irrational.
asked 2021-07-28

Let A, B, and C be sets. Show that (AB)C=(AC)(BC)
image

asked 2022-05-21
Partitions of n where every element of the partition is different from 1 is p ( n ) p ( n 1 )
I am trying to prove that p(n| every element in the partition is different of 1 ) = p ( n ) p ( n 1 ), and I am quite lost... I have tried first giving a biyection between some sets, trying to draw an example in a Ferrers diagram and working on it... Nevertheless, I have not obtained significant results. Then, I have thought about generating functions; we know that the generating function of { p ( n ) } n N is i = 1 1 1 x i , so { p ( n 1 ) } n N will have i = 1 x 1 x i as generating function. So, what we have to prove is that i = 1 1 1 x i i = 1 x 1 x i = ( 1 -x). i = 1 1 1 x i is the generating function of p(n|every element in the partition is different of 1)... but i'm am not seeing why! Any help or hint will be appreciate it!
asked 2022-05-23
Equivalence of mathematical induction and strong induction
Mathematical induction and strong induction are equivalent. That is, each can be shown to be a valid proof technique assuming that the other is valid.
I interpret this to mean that neither proof technique can be used where the other could not be used. That being the case, why bother about strong induction at all?
asked 2022-09-04
Help with Strong Induction proof
A n = { 3 , n = 1 9 , n = 2 2 A n 1 , n 1  and  n  odd 4 A n 1 , n  even
Need to prove A n 3 n n in N 1 by strong induction. After case n = 1 and n = 2, i thought about going for something like n = 2 k for n even and n = 2 k + 1 for n odd but i got stuck and have yet no idea how to proceed after the two inicial cases.

New questions

Solve your problem for the price of one coffee

  • Available 24/7
  • Math expert for every subject
  • Pay only if we can solve it
Ask Question