Mixing
Cat / mouse probability question
Clash Royale CLAN TAG#URR8PPP
up vote
3
down vote
favorite
There exist 7 doors numbered in order from 1 to 7 (going from left to right). A mouse is initially placed at center door 4. The mouse can only move 1 door at a time to either adjacent door and does so, but is twice as likely to move to a lower numbered door than to a higher numbered door each time it moves 1 door. There are cats waiting at doors 1 and 7 that will eat the mouse immediately after the mouse moves to either of those 2 doors.
So for example, the mouse starts at door 4. He could then move to door 3, then to door 2, then back to 3, then back to 2, then to door 1 where he gets eaten. That counts as 5 moves total. Skipping doors is not allowed.
So there are 2 questions I have regarding this:
1) What is the expected average number of moves before the mouse gets eaten? (do not count the initial start at door 4 as a move but count any final move to doors 1 or 7 and any "intermediate" moves between those 2 states).
2) What is the probability that the mouse will survive for 100 or more moves?
probability
asked 4 hours ago
David
341830
add a comment |Â
up vote
3
down vote
favorite
There exist 7 doors numbered in order from 1 to 7 (going from left to right). A mouse is initially placed at center door 4. The mouse can only move 1 door at a time to either adjacent door and does so, but is twice as likely to move to a lower numbered door than to a higher numbered door each time it moves 1 door. There are cats waiting at doors 1 and 7 that will eat the mouse immediately after the mouse moves to either of those 2 doors.
So for example, the mouse starts at door 4. He could then move to door 3, then to door 2, then back to 3, then back to 2, then to door 1 where he gets eaten. That counts as 5 moves total. Skipping doors is not allowed.
So there are 2 questions I have regarding this:
1) What is the expected average number of moves before the mouse gets eaten? (do not count the initial start at door 4 as a move but count any final move to doors 1 or 7 and any "intermediate" moves between those 2 states).
2) What is the probability that the mouse will survive for 100 or more moves?
probability
asked 4 hours ago
David
341830
I do not know how to mathematically solve the 100+ move question either but I would guess it is extremely unlikely, but possible. The mouse would have to "tennis ball" between doors 2 and 6 (inclusive) for a long time before getting to doors 1 or 7. I'll take a guess and say 1 out of 1 billion that this will happen.
– David
3 hours ago
2
You may take a look at those markov chain / random walk / gambler ruins problem for a more generalized set up. For your particular problem it is possible to do with law of total probability and solving a recurrence relation. en.wikipedia.org/wiki/Absorbing_Markov_chain If you can understand those math behind, the wiki site has provided you the tools to analysis the problem.
– BGM
2 hours ago
The mouse will, on average, move twice to the left for every move to the right. So let's look at a few examples (starting at door 4). 5 moves : 3,2,3,2,1 (pattern is L,L,R...) 7 moves : 3,4,3,2,3,2,1 (pattern is L,R,L...) 9 moves : 5,4,3,4,3,2,3,2,1 (pattern is R,L,L) Assuming each of those 3 patterns is equally likely, I just took the average and it comes out to 7 moves. The other possible scenarios of moves are less likely so maybe those are not so significant and will not change the answer much or at all.
– David
2 hours ago
1
Your unscientific intuition is right. The expected number of moves starting from 4 to reach the absorbing states of 0 or 7 is indeed "7".
– Satish Ramanathan
1 hour ago
Wow, I wouldn't say unscientific since I got the patterns correct. I just don't have good math skills to run the Markov chain or whatever else is needed. I expected the answer to be 7 or something close to 7. As far as the 100+ move probability, I am working on it but still do not have an answer. I am hoping my guess of 1 out of a billion is at least in the right order of magnitude, but since it is just a guess, I don't expect it to be very accurate.
– David
1 hour ago
add a comment |Â
up vote
3
down vote
favorite
up vote
3
down vote
favorite
There exist 7 doors numbered in order from 1 to 7 (going from left to right). A mouse is initially placed at center door 4. The mouse can only move 1 door at a time to either adjacent door and does so, but is twice as likely to move to a lower numbered door than to a higher numbered door each time it moves 1 door. There are cats waiting at doors 1 and 7 that will eat the mouse immediately after the mouse moves to either of those 2 doors.
So for example, the mouse starts at door 4. He could then move to door 3, then to door 2, then back to 3, then back to 2, then to door 1 where he gets eaten. That counts as 5 moves total. Skipping doors is not allowed.
So there are 2 questions I have regarding this:
1) What is the expected average number of moves before the mouse gets eaten? (do not count the initial start at door 4 as a move but count any final move to doors 1 or 7 and any "intermediate" moves between those 2 states).
2) What is the probability that the mouse will survive for 100 or more moves?
probability
asked 4 hours ago
David
341830
There exist 7 doors numbered in order from 1 to 7 (going from left to right). A mouse is initially placed at center door 4. The mouse can only move 1 door at a time to either adjacent door and does so, but is twice as likely to move to a lower numbered door than to a higher numbered door each time it moves 1 door. There are cats waiting at doors 1 and 7 that will eat the mouse immediately after the mouse moves to either of those 2 doors.
So for example, the mouse starts at door 4. He could then move to door 3, then to door 2, then back to 3, then back to 2, then to door 1 where he gets eaten. That counts as 5 moves total. Skipping doors is not allowed.
So there are 2 questions I have regarding this:
1) What is the expected average number of moves before the mouse gets eaten? (do not count the initial start at door 4 as a move but count any final move to doors 1 or 7 and any "intermediate" moves between those 2 states).
2) What is the probability that the mouse will survive for 100 or more moves?
probability
probability
asked 4 hours ago
David
341830
asked 4 hours ago
David
341830
edited 3 hours ago
asked 4 hours ago
David
341830
asked 4 hours ago
David
341830
asked 4 hours ago
David
341830
341830
I do not know how to mathematically solve the 100+ move question either but I would guess it is extremely unlikely, but possible. The mouse would have to "tennis ball" between doors 2 and 6 (inclusive) for a long time before getting to doors 1 or 7. I'll take a guess and say 1 out of 1 billion that this will happen.
– David
3 hours ago
2
You may take a look at those markov chain / random walk / gambler ruins problem for a more generalized set up. For your particular problem it is possible to do with law of total probability and solving a recurrence relation. en.wikipedia.org/wiki/Absorbing_Markov_chain If you can understand those math behind, the wiki site has provided you the tools to analysis the problem.
– BGM
2 hours ago
The mouse will, on average, move twice to the left for every move to the right. So let's look at a few examples (starting at door 4). 5 moves : 3,2,3,2,1 (pattern is L,L,R...) 7 moves : 3,4,3,2,3,2,1 (pattern is L,R,L...) 9 moves : 5,4,3,4,3,2,3,2,1 (pattern is R,L,L) Assuming each of those 3 patterns is equally likely, I just took the average and it comes out to 7 moves. The other possible scenarios of moves are less likely so maybe those are not so significant and will not change the answer much or at all.
– David
2 hours ago
1
Your unscientific intuition is right. The expected number of moves starting from 4 to reach the absorbing states of 0 or 7 is indeed "7".
– Satish Ramanathan
1 hour ago
Wow, I wouldn't say unscientific since I got the patterns correct. I just don't have good math skills to run the Markov chain or whatever else is needed. I expected the answer to be 7 or something close to 7. As far as the 100+ move probability, I am working on it but still do not have an answer. I am hoping my guess of 1 out of a billion is at least in the right order of magnitude, but since it is just a guess, I don't expect it to be very accurate.
– David
1 hour ago
add a comment |Â
I do not know how to mathematically solve the 100+ move question either but I would guess it is extremely unlikely, but possible. The mouse would have to "tennis ball" between doors 2 and 6 (inclusive) for a long time before getting to doors 1 or 7. I'll take a guess and say 1 out of 1 billion that this will happen.
– David
3 hours ago
2
You may take a look at those markov chain / random walk / gambler ruins problem for a more generalized set up. For your particular problem it is possible to do with law of total probability and solving a recurrence relation. en.wikipedia.org/wiki/Absorbing_Markov_chain If you can understand those math behind, the wiki site has provided you the tools to analysis the problem.
– BGM
2 hours ago
The mouse will, on average, move twice to the left for every move to the right. So let's look at a few examples (starting at door 4). 5 moves : 3,2,3,2,1 (pattern is L,L,R...) 7 moves : 3,4,3,2,3,2,1 (pattern is L,R,L...) 9 moves : 5,4,3,4,3,2,3,2,1 (pattern is R,L,L) Assuming each of those 3 patterns is equally likely, I just took the average and it comes out to 7 moves. The other possible scenarios of moves are less likely so maybe those are not so significant and will not change the answer much or at all.
– David
2 hours ago
1
Your unscientific intuition is right. The expected number of moves starting from 4 to reach the absorbing states of 0 or 7 is indeed "7".
– Satish Ramanathan
1 hour ago
Wow, I wouldn't say unscientific since I got the patterns correct. I just don't have good math skills to run the Markov chain or whatever else is needed. I expected the answer to be 7 or something close to 7. As far as the 100+ move probability, I am working on it but still do not have an answer. I am hoping my guess of 1 out of a billion is at least in the right order of magnitude, but since it is just a guess, I don't expect it to be very accurate.
– David
1 hour ago
I do not know how to mathematically solve the 100+ move question either but I would guess it is extremely unlikely, but possible. The mouse would have to "tennis ball" between doors 2 and 6 (inclusive) for a long time before getting to doors 1 or 7. I'll take a guess and say 1 out of 1 billion that this will happen.
– David
3 hours ago
I do not know how to mathematically solve the 100+ move question either but I would guess it is extremely unlikely, but possible. The mouse would have to "tennis ball" between doors 2 and 6 (inclusive) for a long time before getting to doors 1 or 7. I'll take a guess and say 1 out of 1 billion that this will happen.
– David
3 hours ago
2
2
You may take a look at those markov chain / random walk / gambler ruins problem for a more generalized set up. For your particular problem it is possible to do with law of total probability and solving a recurrence relation. en.wikipedia.org/wiki/Absorbing_Markov_chain If you can understand those math behind, the wiki site has provided you the tools to analysis the problem.
– BGM
2 hours ago
You may take a look at those markov chain / random walk / gambler ruins problem for a more generalized set up. For your particular problem it is possible to do with law of total probability and solving a recurrence relation. en.wikipedia.org/wiki/Absorbing_Markov_chain If you can understand those math behind, the wiki site has provided you the tools to analysis the problem.
– BGM
2 hours ago
The mouse will, on average, move twice to the left for every move to the right. So let's look at a few examples (starting at door 4). 5 moves : 3,2,3,2,1 (pattern is L,L,R...) 7 moves : 3,4,3,2,3,2,1 (pattern is L,R,L...) 9 moves : 5,4,3,4,3,2,3,2,1 (pattern is R,L,L) Assuming each of those 3 patterns is equally likely, I just took the average and it comes out to 7 moves. The other possible scenarios of moves are less likely so maybe those are not so significant and will not change the answer much or at all.
– David
2 hours ago
The mouse will, on average, move twice to the left for every move to the right. So let's look at a few examples (starting at door 4). 5 moves : 3,2,3,2,1 (pattern is L,L,R...) 7 moves : 3,4,3,2,3,2,1 (pattern is L,R,L...) 9 moves : 5,4,3,4,3,2,3,2,1 (pattern is R,L,L) Assuming each of those 3 patterns is equally likely, I just took the average and it comes out to 7 moves. The other possible scenarios of moves are less likely so maybe those are not so significant and will not change the answer much or at all.
– David
2 hours ago
1
1
Your unscientific intuition is right. The expected number of moves starting from 4 to reach the absorbing states of 0 or 7 is indeed "7".
– Satish Ramanathan
1 hour ago
Your unscientific intuition is right. The expected number of moves starting from 4 to reach the absorbing states of 0 or 7 is indeed "7".
– Satish Ramanathan
1 hour ago
Wow, I wouldn't say unscientific since I got the patterns correct. I just don't have good math skills to run the Markov chain or whatever else is needed. I expected the answer to be 7 or something close to 7. As far as the 100+ move probability, I am working on it but still do not have an answer. I am hoping my guess of 1 out of a billion is at least in the right order of magnitude, but since it is just a guess, I don't expect it to be very accurate.
– David
1 hour ago
Wow, I wouldn't say unscientific since I got the patterns correct. I just don't have good math skills to run the Markov chain or whatever else is needed. I expected the answer to be 7 or something close to 7. As far as the 100+ move probability, I am working on it but still do not have an answer. I am hoping my guess of 1 out of a billion is at least in the right order of magnitude, but since it is just a guess, I don't expect it to be very accurate.
– David
1 hour ago
add a comment |Â
3 Answers
3
active
oldest
votes
up vote
2
down vote
I'll renumber the doors $0$ to $6$ to simplify the calculations.
For the first question, we can set up a recurrence for the expected number $a_n$ of moves the mouse will make starting at door $n$:
$$
a_n=1+(1-p)a_n-1+pa_n+1;,
$$
with $p=frac13$. A particular solution of the inhomogeneous equation is $a_n=3n$, and the homogeneous equation can be solved using the ansatz $a_n=lambda^n$, leading to the charateristic equation
$$
plambda^2-lambda+1-p=0
$$
with solutions $lambda=1$ and $lambda=frac1p-1=2$. Altogether,
$$
a_n=c_1+c_22^n+3n;.
$$
The boundary values are $a_0=a_6=0$, which yields
begineqnarray*
c_1+c_2&=&0;,\
c_1+64c_2+18&=&0;,
endeqnarray*
with solution $c_1=-c_2=frac27$. Thus the life expectancy in the middle is
$$
a_3=frac27-frac27cdot2^3+3cdot3=7;.
$$
For the second question, you can group the $100$ steps into $50$ pairs, reducing the process to doors $1$, $3$ and $5$. The transition matrix for each pair of steps is
$$
frac19pmatrix2&4&0\1&4&4\0&1&2;,
$$
which conveniently happens to have a nice eigensystem. The initial state decomposes as
$$
pmatrix0\1\0=frac16left(pmatrix4\4\1-pmatrix4\-2\1right);,
$$
where the first vector is an eigenvector with eigenvalue $frac23$ and the second vector is an eigenvector with eigenvalue $0$. Thus after $50$ pairs of steps the distribution on doors $1$, $3$ and $5$ is
$$
frac16left(frac23right)^50pmatrix4\4\1;,
$$
and the sum of these probabilities is
$$
left(frac23right)^49approx2.4cdot10^-9;,
$$
so your guess had the right order of magnitude.
We can also use this eigenanalysis to derive the life expectancy another way. After the first pair of steps, the distribution is
$$
frac19pmatrix4\4\1;.
$$
From then on, the mouse gets eaten with probability $frac13$ in each pair of steps, so the expected number of pairs after the first one is $3$. Since death occurs on the first step of a pair, that translates to $7$ steps.
answered 53 mins ago
joriki
168k10181336
add a comment |Â
up vote
1
down vote
The first matrix is the transition matrix with seven states. States 1 and 7 are absorbing states. The one shaded baige is the matrix Q. The next matrix below is (I-Q) and the one below it is its inverse. Take this inverse and multiply by (5X1) 1 vector. As you can see, the entry near 4 is the expected number of moves before it reaches either of the absorbing states. It works out to be 7. Had the starting state been 2, the expected number of moves before it is eaten is 2.714.
answered 1 hour ago
Satish Ramanathan
8,94231123
add a comment |Â
up vote
1
down vote
I'll take a shot at this........
1) The eventual fateful outcome occurs when the total number of moves, lower versus higher, differs by 3.
$E(x_L) - E(x_H) = 3$
$P_Lcdot n - P_Hcdot n = 3$
$frac23cdot n - frac13cdot n = 3$
$frac13cdot n = 3$
$n = 9$
Some commenters have given the answer as $7$, but the probability of getting to $1$ or $7$ in $7$ moves is $frac3881 (< 0.5)$
2) $$P(nge 100) = 1 - P(n<100)$$
$$P(n<100) = S_n = frac13+frac29+frac427+ .......+frac2^n-13^n$$
This turns out to be a geometric series, where $a_1 = frac13, r = frac23$ and $n = 49$ (odd from $3$ to $99$)
Example calculation for $3$rd term is: $9(frac23)^5(frac13)^2 + 9(frac13)^5(frac23)^2 = frac427$
$$P(nge 100) = 1 - fracfrac13(1-(frac23)^49)1-(frac23)$$
$$P(nge 100) = 1 - .9999999976 = 2.4cdot 10^-9$$
answered 1 hour ago
Phil H
2,2382311
If the probability of getting to states (doors) 1 or 7 in exactly 7 moves is slightly less than 1/2, then that actually seems like it could be the peak of the likely # of moves to be "absorbed" (eaten). My simplistic analysis also agrees that using the LLR, LRL, and RLL movements of the mouse in equal proportions, will result in 7 moves before death. I am not sure where you are getting 9 from. I think if the probability of moving either left or right was the same (50%), then the average number of moves would then be 9, but since there is a bias to move left, the 9 answer seems wrong to me.
– David
57 mins ago
1
Note that your result for $mathsf P(nge100)$ simplifies to $left(frac23right)^49$.
– joriki
52 mins ago
add a comment |Â
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
2
down vote
I'll renumber the doors $0$ to $6$ to simplify the calculations.
For the first question, we can set up a recurrence for the expected number $a_n$ of moves the mouse will make starting at door $n$:
$$
a_n=1+(1-p)a_n-1+pa_n+1;,
$$
with $p=frac13$. A particular solution of the inhomogeneous equation is $a_n=3n$, and the homogeneous equation can be solved using the ansatz $a_n=lambda^n$, leading to the charateristic equation
$$
plambda^2-lambda+1-p=0
$$
with solutions $lambda=1$ and $lambda=frac1p-1=2$. Altogether,
$$
a_n=c_1+c_22^n+3n;.
$$
The boundary values are $a_0=a_6=0$, which yields
begineqnarray*
c_1+c_2&=&0;,\
c_1+64c_2+18&=&0;,
endeqnarray*
with solution $c_1=-c_2=frac27$. Thus the life expectancy in the middle is
$$
a_3=frac27-frac27cdot2^3+3cdot3=7;.
$$
For the second question, you can group the $100$ steps into $50$ pairs, reducing the process to doors $1$, $3$ and $5$. The transition matrix for each pair of steps is
$$
frac19pmatrix2&4&0\1&4&4\0&1&2;,
$$
which conveniently happens to have a nice eigensystem. The initial state decomposes as
$$
pmatrix0\1\0=frac16left(pmatrix4\4\1-pmatrix4\-2\1right);,
$$
where the first vector is an eigenvector with eigenvalue $frac23$ and the second vector is an eigenvector with eigenvalue $0$. Thus after $50$ pairs of steps the distribution on doors $1$, $3$ and $5$ is
$$
frac16left(frac23right)^50pmatrix4\4\1;,
$$
and the sum of these probabilities is
$$
left(frac23right)^49approx2.4cdot10^-9;,
$$
so your guess had the right order of magnitude.
We can also use this eigenanalysis to derive the life expectancy another way. After the first pair of steps, the distribution is
$$
frac19pmatrix4\4\1;.
$$
From then on, the mouse gets eaten with probability $frac13$ in each pair of steps, so the expected number of pairs after the first one is $3$. Since death occurs on the first step of a pair, that translates to $7$ steps.
answered 53 mins ago
joriki
168k10181336
add a comment |Â
up vote
2
down vote
I'll renumber the doors $0$ to $6$ to simplify the calculations.
For the first question, we can set up a recurrence for the expected number $a_n$ of moves the mouse will make starting at door $n$:
$$
a_n=1+(1-p)a_n-1+pa_n+1;,
$$
with $p=frac13$. A particular solution of the inhomogeneous equation is $a_n=3n$, and the homogeneous equation can be solved using the ansatz $a_n=lambda^n$, leading to the charateristic equation
$$
plambda^2-lambda+1-p=0
$$
with solutions $lambda=1$ and $lambda=frac1p-1=2$. Altogether,
$$
a_n=c_1+c_22^n+3n;.
$$
The boundary values are $a_0=a_6=0$, which yields
begineqnarray*
c_1+c_2&=&0;,\
c_1+64c_2+18&=&0;,
endeqnarray*
with solution $c_1=-c_2=frac27$. Thus the life expectancy in the middle is
$$
a_3=frac27-frac27cdot2^3+3cdot3=7;.
$$
For the second question, you can group the $100$ steps into $50$ pairs, reducing the process to doors $1$, $3$ and $5$. The transition matrix for each pair of steps is
$$
frac19pmatrix2&4&0\1&4&4\0&1&2;,
$$
which conveniently happens to have a nice eigensystem. The initial state decomposes as
$$
pmatrix0\1\0=frac16left(pmatrix4\4\1-pmatrix4\-2\1right);,
$$
where the first vector is an eigenvector with eigenvalue $frac23$ and the second vector is an eigenvector with eigenvalue $0$. Thus after $50$ pairs of steps the distribution on doors $1$, $3$ and $5$ is
$$
frac16left(frac23right)^50pmatrix4\4\1;,
$$
and the sum of these probabilities is
$$
left(frac23right)^49approx2.4cdot10^-9;,
$$
so your guess had the right order of magnitude.
We can also use this eigenanalysis to derive the life expectancy another way. After the first pair of steps, the distribution is
$$
frac19pmatrix4\4\1;.
$$
From then on, the mouse gets eaten with probability $frac13$ in each pair of steps, so the expected number of pairs after the first one is $3$. Since death occurs on the first step of a pair, that translates to $7$ steps.
answered 53 mins ago
joriki
168k10181336
add a comment |Â
up vote
2
down vote
up vote
2
down vote
I'll renumber the doors $0$ to $6$ to simplify the calculations.
For the first question, we can set up a recurrence for the expected number $a_n$ of moves the mouse will make starting at door $n$:
$$
a_n=1+(1-p)a_n-1+pa_n+1;,
$$
with $p=frac13$. A particular solution of the inhomogeneous equation is $a_n=3n$, and the homogeneous equation can be solved using the ansatz $a_n=lambda^n$, leading to the charateristic equation
$$
plambda^2-lambda+1-p=0
$$
with solutions $lambda=1$ and $lambda=frac1p-1=2$. Altogether,
$$
a_n=c_1+c_22^n+3n;.
$$
The boundary values are $a_0=a_6=0$, which yields
begineqnarray*
c_1+c_2&=&0;,\
c_1+64c_2+18&=&0;,
endeqnarray*
with solution $c_1=-c_2=frac27$. Thus the life expectancy in the middle is
$$
a_3=frac27-frac27cdot2^3+3cdot3=7;.
$$
For the second question, you can group the $100$ steps into $50$ pairs, reducing the process to doors $1$, $3$ and $5$. The transition matrix for each pair of steps is
$$
frac19pmatrix2&4&0\1&4&4\0&1&2;,
$$
which conveniently happens to have a nice eigensystem. The initial state decomposes as
$$
pmatrix0\1\0=frac16left(pmatrix4\4\1-pmatrix4\-2\1right);,
$$
where the first vector is an eigenvector with eigenvalue $frac23$ and the second vector is an eigenvector with eigenvalue $0$. Thus after $50$ pairs of steps the distribution on doors $1$, $3$ and $5$ is
$$
frac16left(frac23right)^50pmatrix4\4\1;,
$$
and the sum of these probabilities is
$$
left(frac23right)^49approx2.4cdot10^-9;,
$$
so your guess had the right order of magnitude.
We can also use this eigenanalysis to derive the life expectancy another way. After the first pair of steps, the distribution is
$$
frac19pmatrix4\4\1;.
$$
From then on, the mouse gets eaten with probability $frac13$ in each pair of steps, so the expected number of pairs after the first one is $3$. Since death occurs on the first step of a pair, that translates to $7$ steps.
answered 53 mins ago
joriki
168k10181336
I'll renumber the doors $0$ to $6$ to simplify the calculations.
For the first question, we can set up a recurrence for the expected number $a_n$ of moves the mouse will make starting at door $n$:
$$
a_n=1+(1-p)a_n-1+pa_n+1;,
$$
with $p=frac13$. A particular solution of the inhomogeneous equation is $a_n=3n$, and the homogeneous equation can be solved using the ansatz $a_n=lambda^n$, leading to the charateristic equation
$$
plambda^2-lambda+1-p=0
$$
with solutions $lambda=1$ and $lambda=frac1p-1=2$. Altogether,
$$
a_n=c_1+c_22^n+3n;.
$$
The boundary values are $a_0=a_6=0$, which yields
begineqnarray*
c_1+c_2&=&0;,\
c_1+64c_2+18&=&0;,
endeqnarray*
with solution $c_1=-c_2=frac27$. Thus the life expectancy in the middle is
$$
a_3=frac27-frac27cdot2^3+3cdot3=7;.
$$
For the second question, you can group the $100$ steps into $50$ pairs, reducing the process to doors $1$, $3$ and $5$. The transition matrix for each pair of steps is
$$
frac19pmatrix2&4&0\1&4&4\0&1&2;,
$$
which conveniently happens to have a nice eigensystem. The initial state decomposes as
$$
pmatrix0\1\0=frac16left(pmatrix4\4\1-pmatrix4\-2\1right);,
$$
where the first vector is an eigenvector with eigenvalue $frac23$ and the second vector is an eigenvector with eigenvalue $0$. Thus after $50$ pairs of steps the distribution on doors $1$, $3$ and $5$ is
$$
frac16left(frac23right)^50pmatrix4\4\1;,
$$
and the sum of these probabilities is
$$
left(frac23right)^49approx2.4cdot10^-9;,
$$
so your guess had the right order of magnitude.
We can also use this eigenanalysis to derive the life expectancy another way. After the first pair of steps, the distribution is
$$
frac19pmatrix4\4\1;.
$$
From then on, the mouse gets eaten with probability $frac13$ in each pair of steps, so the expected number of pairs after the first one is $3$. Since death occurs on the first step of a pair, that translates to $7$ steps.
answered 53 mins ago
joriki
168k10181336
edited 21 mins ago
answered 53 mins ago
joriki
168k10181336
answered 53 mins ago
joriki
168k10181336
answered 53 mins ago
joriki
168k10181336
168k10181336
add a comment |Â
add a comment |Â
up vote
1
down vote
The first matrix is the transition matrix with seven states. States 1 and 7 are absorbing states. The one shaded baige is the matrix Q. The next matrix below is (I-Q) and the one below it is its inverse. Take this inverse and multiply by (5X1) 1 vector. As you can see, the entry near 4 is the expected number of moves before it reaches either of the absorbing states. It works out to be 7. Had the starting state been 2, the expected number of moves before it is eaten is 2.714.
answered 1 hour ago
Satish Ramanathan
8,94231123
add a comment |Â
up vote
1
down vote
The first matrix is the transition matrix with seven states. States 1 and 7 are absorbing states. The one shaded baige is the matrix Q. The next matrix below is (I-Q) and the one below it is its inverse. Take this inverse and multiply by (5X1) 1 vector. As you can see, the entry near 4 is the expected number of moves before it reaches either of the absorbing states. It works out to be 7. Had the starting state been 2, the expected number of moves before it is eaten is 2.714.
answered 1 hour ago
Satish Ramanathan
8,94231123
add a comment |Â
up vote
1
down vote
up vote
1
down vote
The first matrix is the transition matrix with seven states. States 1 and 7 are absorbing states. The one shaded baige is the matrix Q. The next matrix below is (I-Q) and the one below it is its inverse. Take this inverse and multiply by (5X1) 1 vector. As you can see, the entry near 4 is the expected number of moves before it reaches either of the absorbing states. It works out to be 7. Had the starting state been 2, the expected number of moves before it is eaten is 2.714.
answered 1 hour ago
Satish Ramanathan
8,94231123
The first matrix is the transition matrix with seven states. States 1 and 7 are absorbing states. The one shaded baige is the matrix Q. The next matrix below is (I-Q) and the one below it is its inverse. Take this inverse and multiply by (5X1) 1 vector. As you can see, the entry near 4 is the expected number of moves before it reaches either of the absorbing states. It works out to be 7. Had the starting state been 2, the expected number of moves before it is eaten is 2.714.
answered 1 hour ago
Satish Ramanathan
8,94231123
answered 1 hour ago
Satish Ramanathan
8,94231123
answered 1 hour ago
Satish Ramanathan
8,94231123
answered 1 hour ago
Satish Ramanathan
8,94231123
8,94231123
add a comment |Â
add a comment |Â
up vote
1
down vote
I'll take a shot at this........
1) The eventual fateful outcome occurs when the total number of moves, lower versus higher, differs by 3.
$E(x_L) - E(x_H) = 3$
$P_Lcdot n - P_Hcdot n = 3$
$frac23cdot n - frac13cdot n = 3$
$frac13cdot n = 3$
$n = 9$
Some commenters have given the answer as $7$, but the probability of getting to $1$ or $7$ in $7$ moves is $frac3881 (< 0.5)$
2) $$P(nge 100) = 1 - P(n<100)$$
$$P(n<100) = S_n = frac13+frac29+frac427+ .......+frac2^n-13^n$$
This turns out to be a geometric series, where $a_1 = frac13, r = frac23$ and $n = 49$ (odd from $3$ to $99$)
Example calculation for $3$rd term is: $9(frac23)^5(frac13)^2 + 9(frac13)^5(frac23)^2 = frac427$
$$P(nge 100) = 1 - fracfrac13(1-(frac23)^49)1-(frac23)$$
$$P(nge 100) = 1 - .9999999976 = 2.4cdot 10^-9$$
answered 1 hour ago
Phil H
2,2382311
If the probability of getting to states (doors) 1 or 7 in exactly 7 moves is slightly less than 1/2, then that actually seems like it could be the peak of the likely # of moves to be "absorbed" (eaten). My simplistic analysis also agrees that using the LLR, LRL, and RLL movements of the mouse in equal proportions, will result in 7 moves before death. I am not sure where you are getting 9 from. I think if the probability of moving either left or right was the same (50%), then the average number of moves would then be 9, but since there is a bias to move left, the 9 answer seems wrong to me.
– David
57 mins ago
1
Note that your result for $mathsf P(nge100)$ simplifies to $left(frac23right)^49$.
– joriki
52 mins ago
add a comment |Â
up vote
1
down vote
I'll take a shot at this........
1) The eventual fateful outcome occurs when the total number of moves, lower versus higher, differs by 3.
$E(x_L) - E(x_H) = 3$
$P_Lcdot n - P_Hcdot n = 3$
$frac23cdot n - frac13cdot n = 3$
$frac13cdot n = 3$
$n = 9$
Some commenters have given the answer as $7$, but the probability of getting to $1$ or $7$ in $7$ moves is $frac3881 (< 0.5)$
2) $$P(nge 100) = 1 - P(n<100)$$
$$P(n<100) = S_n = frac13+frac29+frac427+ .......+frac2^n-13^n$$
This turns out to be a geometric series, where $a_1 = frac13, r = frac23$ and $n = 49$ (odd from $3$ to $99$)
Example calculation for $3$rd term is: $9(frac23)^5(frac13)^2 + 9(frac13)^5(frac23)^2 = frac427$
$$P(nge 100) = 1 - fracfrac13(1-(frac23)^49)1-(frac23)$$
$$P(nge 100) = 1 - .9999999976 = 2.4cdot 10^-9$$
answered 1 hour ago
Phil H
2,2382311
If the probability of getting to states (doors) 1 or 7 in exactly 7 moves is slightly less than 1/2, then that actually seems like it could be the peak of the likely # of moves to be "absorbed" (eaten). My simplistic analysis also agrees that using the LLR, LRL, and RLL movements of the mouse in equal proportions, will result in 7 moves before death. I am not sure where you are getting 9 from. I think if the probability of moving either left or right was the same (50%), then the average number of moves would then be 9, but since there is a bias to move left, the 9 answer seems wrong to me.
– David
57 mins ago
1
Note that your result for $mathsf P(nge100)$ simplifies to $left(frac23right)^49$.
– joriki
52 mins ago
add a comment |Â
up vote
1
down vote
up vote
1
down vote
I'll take a shot at this........
1) The eventual fateful outcome occurs when the total number of moves, lower versus higher, differs by 3.
$E(x_L) - E(x_H) = 3$
$P_Lcdot n - P_Hcdot n = 3$
$frac23cdot n - frac13cdot n = 3$
$frac13cdot n = 3$
$n = 9$
Some commenters have given the answer as $7$, but the probability of getting to $1$ or $7$ in $7$ moves is $frac3881 (< 0.5)$
2) $$P(nge 100) = 1 - P(n<100)$$
$$P(n<100) = S_n = frac13+frac29+frac427+ .......+frac2^n-13^n$$
This turns out to be a geometric series, where $a_1 = frac13, r = frac23$ and $n = 49$ (odd from $3$ to $99$)
Example calculation for $3$rd term is: $9(frac23)^5(frac13)^2 + 9(frac13)^5(frac23)^2 = frac427$
$$P(nge 100) = 1 - fracfrac13(1-(frac23)^49)1-(frac23)$$
$$P(nge 100) = 1 - .9999999976 = 2.4cdot 10^-9$$
answered 1 hour ago
Phil H
2,2382311
I'll take a shot at this........
1) The eventual fateful outcome occurs when the total number of moves, lower versus higher, differs by 3.
$E(x_L) - E(x_H) = 3$
$P_Lcdot n - P_Hcdot n = 3$
$frac23cdot n - frac13cdot n = 3$
$frac13cdot n = 3$
$n = 9$
Some commenters have given the answer as $7$, but the probability of getting to $1$ or $7$ in $7$ moves is $frac3881 (< 0.5)$
2) $$P(nge 100) = 1 - P(n<100)$$
$$P(n<100) = S_n = frac13+frac29+frac427+ .......+frac2^n-13^n$$
This turns out to be a geometric series, where $a_1 = frac13, r = frac23$ and $n = 49$ (odd from $3$ to $99$)
Example calculation for $3$rd term is: $9(frac23)^5(frac13)^2 + 9(frac13)^5(frac23)^2 = frac427$
$$P(nge 100) = 1 - fracfrac13(1-(frac23)^49)1-(frac23)$$
$$P(nge 100) = 1 - .9999999976 = 2.4cdot 10^-9$$
answered 1 hour ago
Phil H
2,2382311
answered 1 hour ago
Phil H
2,2382311
answered 1 hour ago
Phil H
2,2382311
answered 1 hour ago
Phil H
2,2382311
2,2382311
If the probability of getting to states (doors) 1 or 7 in exactly 7 moves is slightly less than 1/2, then that actually seems like it could be the peak of the likely # of moves to be "absorbed" (eaten). My simplistic analysis also agrees that using the LLR, LRL, and RLL movements of the mouse in equal proportions, will result in 7 moves before death. I am not sure where you are getting 9 from. I think if the probability of moving either left or right was the same (50%), then the average number of moves would then be 9, but since there is a bias to move left, the 9 answer seems wrong to me.
– David
57 mins ago
1
Note that your result for $mathsf P(nge100)$ simplifies to $left(frac23right)^49$.
– joriki
52 mins ago
add a comment |Â
If the probability of getting to states (doors) 1 or 7 in exactly 7 moves is slightly less than 1/2, then that actually seems like it could be the peak of the likely # of moves to be "absorbed" (eaten). My simplistic analysis also agrees that using the LLR, LRL, and RLL movements of the mouse in equal proportions, will result in 7 moves before death. I am not sure where you are getting 9 from. I think if the probability of moving either left or right was the same (50%), then the average number of moves would then be 9, but since there is a bias to move left, the 9 answer seems wrong to me.
– David
57 mins ago
1
Note that your result for $mathsf P(nge100)$ simplifies to $left(frac23right)^49$.
– joriki
52 mins ago
If the probability of getting to states (doors) 1 or 7 in exactly 7 moves is slightly less than 1/2, then that actually seems like it could be the peak of the likely # of moves to be "absorbed" (eaten). My simplistic analysis also agrees that using the LLR, LRL, and RLL movements of the mouse in equal proportions, will result in 7 moves before death. I am not sure where you are getting 9 from. I think if the probability of moving either left or right was the same (50%), then the average number of moves would then be 9, but since there is a bias to move left, the 9 answer seems wrong to me.
– David
57 mins ago
If the probability of getting to states (doors) 1 or 7 in exactly 7 moves is slightly less than 1/2, then that actually seems like it could be the peak of the likely # of moves to be "absorbed" (eaten). My simplistic analysis also agrees that using the LLR, LRL, and RLL movements of the mouse in equal proportions, will result in 7 moves before death. I am not sure where you are getting 9 from. I think if the probability of moving either left or right was the same (50%), then the average number of moves would then be 9, but since there is a bias to move left, the 9 answer seems wrong to me.
– David
57 mins ago
1
1
Note that your result for $mathsf P(nge100)$ simplifies to $left(frac23right)^49$.
– joriki
52 mins ago
Note that your result for $mathsf P(nge100)$ simplifies to $left(frac23right)^49$.
– joriki
52 mins ago
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2924838%2fcat-mouse-probability-question%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
I do not know how to mathematically solve the 100+ move question either but I would guess it is extremely unlikely, but possible. The mouse would have to "tennis ball" between doors 2 and 6 (inclusive) for a long time before getting to doors 1 or 7. I'll take a guess and say 1 out of 1 billion that this will happen.
– David
3 hours ago
2
You may take a look at those markov chain / random walk / gambler ruins problem for a more generalized set up. For your particular problem it is possible to do with law of total probability and solving a recurrence relation. en.wikipedia.org/wiki/Absorbing_Markov_chain If you can understand those math behind, the wiki site has provided you the tools to analysis the problem.
– BGM
2 hours ago
The mouse will, on average, move twice to the left for every move to the right. So let's look at a few examples (starting at door 4). 5 moves : 3,2,3,2,1 (pattern is L,L,R...) 7 moves : 3,4,3,2,3,2,1 (pattern is L,R,L...) 9 moves : 5,4,3,4,3,2,3,2,1 (pattern is R,L,L) Assuming each of those 3 patterns is equally likely, I just took the average and it comes out to 7 moves. The other possible scenarios of moves are less likely so maybe those are not so significant and will not change the answer much or at all.
– David
2 hours ago
1
Your unscientific intuition is right. The expected number of moves starting from 4 to reach the absorbing states of 0 or 7 is indeed "7".
– Satish Ramanathan
1 hour ago
Wow, I wouldn't say unscientific since I got the patterns correct. I just don't have good math skills to run the Markov chain or whatever else is needed. I expected the answer to be 7 or something close to 7. As far as the 100+ move probability, I am working on it but still do not have an answer. I am hoping my guess of 1 out of a billion is at least in the right order of magnitude, but since it is just a guess, I don't expect it to be very accurate.
– David
1 hour ago