Solving Transition Matrix: Octopus Training

[mathmari]

Hey!

An octopus is trained to chosose from two objects A and B always the object A. Repeated training shows the octopus both objects, if the octopus chooses object A, he will be rewarded. The octopus can be in 3 levels of training:
Level 1: He can not remember which object was rewarded.
Level 2: He briefly remembers, chooses object A, but he can forget it again.
Level 3: He remembers, chooses object A and never forgets it.
The probability that the octopus rises from level 1 to level 2 is the same great, as he learns nothing.
When the octopus reaches level 2, the probability of falling back to level 1 is the same as staying in level 2 and rising to level 3 together.
The probability of moving up from level 2 to level 3 is 5 times greater than staying in level 2.
The octopus can not skip any training level and we assume that he is in level 1 at the beginning of the workout.

1. Set up the associated transition matrix of this markov chain and specify the initial distribution.
2. What is the probability that the octopus learns nothing in the first 5 attempts and stays completely in level 1?
3. How big are the probabilities of the individual training levels after 3 attempts?

I have done the following:

1. The stochastic matrix is in the following form: $$P=\begin{pmatrix}P_{1,1} & P_{1,2} & P_{1,3} \\ P_{2,1} & P_{2,2} & P_{2,3} \\ P_{3,1} & P_{3,2} & P_{3,3}\end{pmatrix}$$
   We have the following information:
   • $P_{1,2}=P(\text{Learns nothing})$
   • $P_{2,1}=P_{2,2}+P_{2,3}$
   • $P_{2,3}=5\cdot P_{2,2}$
   At each row of the transition matrix the sum of the probabilities is equal to $1$, so we have that $P_{1,1}+P_{1,2}+P_{1,3}=1$, $P_{2,1}+P_{2,2}+P_{2,3}=1$, $P_{3,1}+P_{3,2}+P_{3,3}=1$.
   
   Which is the probability $P(\text{Learns nothing})$ ? (Wondering)
   
   We have that $P_{2,1}+P_{2,2}+P_{2,3}=1$ and $P_{2,1}=P_{2,2}+P_{2,3}$ and $P_{2,3}=5\cdot P_{2,2}$, so we get the following: \begin{align*}P_{2,2}+P_{2,3}+P_{2,2}+P_{2,3}=1&\Rightarrow 2\cdot P_{2,2}+2\cdot P_{2,3}=1 \\ & \Rightarrow 2\cdot P_{2,2}+2\cdot (5\cdot P_{2,2})=1 \\ & \Rightarrow 2\cdot P_{2,2}+10\cdot P_{2,2}=1 \\ & \Rightarrow 12\cdot P_{2,2}=1 \\ & \Rightarrow P_{2,2}=\frac{1}{12}\end{align*}
   So, we get also $\displaystyle{P_{2,3}=5\cdot P_{2,2}=5\cdot \frac{1}{12}=\frac{5}{12}}$ and $\displaystyle{P_{2,1}=P_{2,2}+P_{2,3}=\frac{1}{12}+\frac{5}{12}=\frac{6}{12}=\frac{1}{2}}$.
   
   So, we get the transition matrix: $$P=\begin{pmatrix}P_{1,1} & P_{1,2} & P_{1,3} \\ \frac{1}{2} & \frac{1}{12} & \frac{5}{12} \\ P_{3,1} & P_{3,2} & P_{3,3}\end{pmatrix}$$
   
   How can we complete the remaining matrix? (Wondering)
   

 

[I like Serena]

The probability that the octopus rises from level 1 to level 2 is the same great, as he learns nothing.

Which is the probability $P(\text{Learns nothing})$ ?

Hey mathmari!

When at level 1, what's the alternative to rising to level 2?
Did the octopus learn anything in that case? (Wondering)

 

[mathmari]

When at level 1, what's the alternative to rising to level 2?
Did the octopus learn anything in that case? (Wondering)

At level 1 the octopus can not remember which object was rewarded and at level 2 he briefly remembers, chooses object A, but he can forget it again. Does that mean that the octopus doesn't learn anything when he rises from level 1 to level 2? (Wondering)

 

[I like Serena]

At level 1 the octopus can not remember which object was rewarded and at level 2 he briefly remembers, chooses object A, but he can forget it again. Does that mean that the octopus doesn't learn anything when he rises from level 1 to level 2? (Wondering)

From level 1 we can either go to level 2 ($P_{1,2}$), or we can stay at level 1 ($P_{1,1}$) can't we?
And if we stay at level 1, we have 'Level 1: He can not remember which object was rewarded.'.
Isn't that the same as that he didn't learn anything? (Wondering)

 

[mathmari]

From level 1 we can either go to level 2 ($P_{1,2}$), or we can stay at level 1 ($P_{1,1}$) can't we?
And if we stay at level 1, we have 'Level 1: He can not remember which object was rewarded.'.
Isn't that the same as that he didn't learn anything? (Wondering)

Ah yes. So, we have that $P_{1,1}=P(\text{Learns nothing})$. It also given that $P_{1,2}=P(\text{Learns nothing})$. Since we cannot skip a level the probability $P_{1,3}$ is equal to $0$, right?
So we get that $$P_{1,1}+P_{1,2}+P_{1,3}=1 \Rightarrow P(\text{Learns nothing})+P(\text{Learns nothing})+0=1 \Rightarrow 2\cdot P(\text{Learns nothing})=1 \Rightarrow P(\text{Learns nothing})=\frac{1}{2}$$

Therefore, we have that $P_{1,1}=\frac{1}{2}$ and $P_{1,2}=\frac{1}{2}$. Is this correct? (Wondering)

 

[I like Serena]

Yep. (Nod)

 

[mathmari]

Yep. (Nod)

So, we get $$P=\begin{pmatrix}\frac{1}{2} & \frac{1}{2} & 0 \\ \frac{1}{2} & \frac{1}{12} & \frac{5}{12} \\ P_{3,1} & P_{3,2} & P_{3,3}\end{pmatrix}$$

How can we calculate the last row? Do we have any information for that? (Wondering)

 

[I like Serena]

How can we calculate the last row? Do we have any information for that? (Wondering)

We have 'Level 3: He remembers, chooses object A and never forgets it.' (Thinking)

 

[mathmari]

We have 'Level 3: He remembers, chooses object A and never forgets it.' (Thinking)

That means that the probability that he falls to level 1 or 2 is equal to 0. Since he will never forget it the probability that he stays in level 3 is equal to 1.

Therefore we get $$P=\begin{pmatrix}\frac{1}{2} & \frac{1}{2} & 0 \\ \frac{1}{2} & \frac{1}{12} & \frac{5}{12} \\ 0 & 0 & 1\end{pmatrix}$$

Is everything correct? (Wondering)

 

[I like Serena]

Yup. (Nod)

 

[mathmari]

1. specify the initial distribution.

How can we find the initial distribution?

2. What is the probability that the octopus learns nothing in the first 5 attempts and stays completely in level 1?

The probability that the octopus learns nothing in the first 5 attempts is equal to $5\cdot P_{1,1}=5\cdot \frac{1}{2}=\frac{5}{2}$, or not?

Is the probability that he stays completely in level 1 equal to $(\text{total number of attempts})\cdot P_{1,1}$ ?

 

[I like Serena]

How can we find the initial distribution?

It says 'we assume that he is in level 1 at the beginning of the workout.' (Thinking)

The probability that the octopus learns nothing in the first 5 attempts is equal to $5\cdot P_{1,1}=5\cdot \frac{1}{2}=\frac{5}{2}$, or not?

Is the probability that he stays completely in level 1 equal to $(\text{total number of attempts})\cdot P_{1,1}$ ?

A probability cannot be greater than 1 can it?
Shouldn't we multiply the probabilities of events that are independent and that are all true? (Wondering)

 

[mathmari]

It says 'we assume that he is in level 1 at the beginning of the workout.' (Thinking)

The initial distribution is the probability of the state $i$ at time $n=0$. Since we assume that he is in level 1 at the beginning of the workout, we have that the probability that the octopus at time $n=0$ is at level 1 is equal to 1 and the probability that he is at level 2 or 3 is equal to 0, since we know that he is at level 1. So, we have that the initial distribution is equal to $(1,0,0)$. Is this correct? (Wondering)
2. What is the probability that the octopus learns nothing in the first 5 attempts and stays completely in level 1?

It holds that the distribution at time n is equal to $P(n)^n\cdot p(0)$, where $p(0)$ is the initial distribution. The $i$th component of that vector is the probability that at time $n$ we are at state $i$.

So, the probability that the octopus learns nothing in the first 5 attempts and stays completely in level 1 is equal to the first component of the vector $P(n)^5\cdot p(0)$, right?

We have that $p(0)=(1,0,0)$ and $$P=\begin{pmatrix}\frac{1}{2} & \frac{1}{2} & 0 \\ \frac{1}{2} & \frac{1}{12} & \frac{5}{12} \\ 0 & 0 & 1\end{pmatrix}\Rightarrow P^5=\frac{1}{248832}\begin{pmatrix}69156& 46266 & 133410 \\ 46266 & 30601 & 171965 \\ 0 & 0 & 248832\end{pmatrix}$$

So, we get that $$P(n)^5\cdot p(0)=\begin{pmatrix}\frac{69156}{248832} \\ \frac{46266}{248832} \\ 0 \end{pmatrix}$$

Therefore, the probability that the octopus learns nothing in the first 5 attempts and stays completely in level 1 is equal to $\frac{69156}{248832}=27,79\%$.

Is everything correct? (Wondering)
3. How big are the probabilities of the individual training levels after 3 attempts?

We have to caclulate $P(n)^3\cdot p(0)$, or not?

We have that $$P^3=\frac{1}{1728}\begin{pmatrix}648& 474 & 570 \\ 474 & 289 & 965 \\ 0 & 0 & 1728\end{pmatrix}$$

Therefore, we get that $$P(n)^3\cdot p(0)=\begin{pmatrix}\frac{648}{1728} \\ \frac{474}{1728} \\ 0 \end{pmatrix}$$ whoch means that the probability to be at level 1 after 3 attempts is equal to $\frac{648}{1728}$, to be at level 2 the probability is equal to $\frac{474}{1728}$ and to be at level 3 the probability is equal to $0$.

Is this correct? (Wondering)

 

[I like Serena]

The initial distribution is the probability of the state $i$ at time $n=0$. Since we assume that he is in level 1 at the beginning of the workout, we have that the probability that the octopus at time $n=0$ is at level 1 is equal to 1 and the probability that he is at level 2 or 3 is equal to 0, since we know that he is at level 1. So, we have that the initial distribution is equal to $(1,0,0)$. Is this correct?

Yep. (Nod)

2. What is the probability that the octopus learns nothing in the first 5 attempts and stays completely in level 1?

It holds that the distribution at time n is equal to $P(n)^n\cdot p(0)$, where $p(0)$ is the initial distribution. The $i$th component of that vector is the probability that at time $n$ we are at state $i$.

So, the probability that the octopus learns nothing in the first 5 attempts and stays completely in level 1 is equal to the first component of the vector $P(n)^5\cdot p(0)$, right?

Nope. That is the probability that the octopus ends up in level 1 after 5 attempts.
In particular it does not mean that he stays completely at level 1. (Shake)

We are looking for $P(\text{1st attempt fails}\land \text{2nd attempt fails}\land ... \land \text{5th attempt fails})$.
Previously you calculated this with the sum rule... but the sum rule only applies if we have OR instead of AND, and moreover, if the events are mutually exclusive, which they are not.
Shouldn't we use the product rule instead? (Thinking)

3. How big are the probabilities of the individual training levels after 3 attempts?

We have to caclulate $P(n)^3\cdot p(0)$, or not?

We have that $$P^3=\frac{1}{1728}\begin{pmatrix}648& 474 & 570 \\ 474 & 289 & 965 \\ 0 & 0 & 1728\end{pmatrix}$$

Therefore, we get that $$P(n)^3\cdot p(0)=\begin{pmatrix}\frac{648}{1728} \\ \frac{474}{1728} \\ 0 \end{pmatrix}$$ whoch means that the probability to be at level 1 after 3 attempts is equal to $\frac{648}{1728}$, to be at level 2 the probability is equal to $\frac{474}{1728}$ and to be at level 3 the probability is equal to $0$.

Is this correct?

Let's take a step back.
Suppose we do only 1 attempt.
Which distribution do we get?
Is it what we expect? (Wondering)

 

[mathmari]

Nope. That is the probability that the octopus ends up in level 1 after 5 attempts.
In particular it does not mean that he stays completely at level 1. (Shake)

We are looking for $P(\text{1st attempt fails}\land \text{2nd attempt fails}\land ... \land \text{5th attempt fails})$.
Previously you calculated this with the sum rule... but the sum rule only applies if we have OR instead of AND, and moreover, if the events are mutually exclusive, which they are not.
Shouldn't we use the product rule instead? (Thinking)

We have that \begin{align*}P&(\text{1st attempt fails}\land \text{2nd attempt fails}\land \ldots \land \text{5th attempt fails}) \\ & =P(\text{1st attempt fails})\cdot P(\text{2nd attempt fails})\cdot \ldots \cdot P(\text{5th attempt fails}) \\ & =P_{1,1}\cdot P_{1,1}\cdot P_{1,1}\cdot P_{1,1}\cdot P_{1,1} \\ & =P_{1,1}^5 \\ & = \left (\frac{1}{2}\right )^5 \\ & =\frac{1}{32}\end{align*}

So, is the probability that the octopus learns nothing in the first 5 attempts and stays completely in level 1 equal to $\frac{1}{32}$ ?

But why does he stays completely in level 1 with this probability?

(Wondering)

Let's take a step back.
Suppose we do only 1 attempt.
Which distribution do we get?
Is it what we expect? (Wondering)

This distribution is equal to $$P\cdot p(0)=\begin{pmatrix}\frac{1}{2} & \frac{1}{2} & 0 \\ \frac{1}{2} & \frac{1}{12} & \frac{5}{12} \\ 0 & 0 & 1\end{pmatrix}\cdot \begin{pmatrix}1\\ 0 \\ 0\end{pmatrix}=\begin{pmatrix}\frac{1}{2}\\ \frac{1}{2} \\ 0\end{pmatrix}$$ or not?

That means that after the first attempt the octopus can either stay at level 1 or rise to level 2, and each of the possibilities has the probability $\frac{1}{2}$, right?

(Wondering)

 

[I like Serena]

We have that \begin{align*}P&(\text{1st attempt fails}\land \text{2nd attempt fails}\land \ldots \land \text{5th attempt fails}) \\ & =P(\text{1st attempt fails})\cdot P(\text{2nd attempt fails})\cdot \ldots \cdot P(\text{5th attempt fails}) \\ & =P_{1,1}\cdot P_{1,1}\cdot P_{1,1}\cdot P_{1,1}\cdot P_{1,1} \\ & =P_{1,1}^5 \\ & = \left (\frac{1}{2}\right )^5 \\ & =\frac{1}{32}\end{align*}

So, is the probability that the octopus learns nothing in the first 5 attempts and stays completely in level 1 equal to $\frac{1}{32}$ ?

Yep. (Nod)
And note that we assume that the attempts are independent, because otherwise we wouldn't be allowed to apply this product rule.

But why does he stays completely in level 1 with this probability?

It means that after every attempt he is still in level 1. Isn't that what would be intended with 'he stays completely in level 1'? (Wondering)


This distribution is equal to $$P\cdot p(0)=\begin{pmatrix}\frac{1}{2} & \frac{1}{2} & 0 \\ \frac{1}{2} & \frac{1}{12} & \frac{5}{12} \\ 0 & 0 & 1\end{pmatrix}\cdot \begin{pmatrix}1\\ 0 \\ 0\end{pmatrix}=\begin{pmatrix}\frac{1}{2}\\ \frac{1}{2} \\ 0\end{pmatrix}$$ or not?

That means that after the first attempt the octopus can either stay at level 1 or rise to level 2, and each of the possibilities has the probability $\frac{1}{2}$, right?

Heh. The values of those probabilities is a bit unfortunate. (Lipssealed)
We picked the leftmost column that just happened to be the same as the topmost row in this case.
But should we have the leftmost column? Or should we have the topmost row? (Wondering)

Shouldn't we calculate:
$$
\begin{pmatrix}1 & 0 &\ 0\end{pmatrix} \cdot
\begin{pmatrix}\frac{1}{2} & \frac{1}{2} & 0 \\ \frac{1}{2} & \frac{1}{12} & \frac{5}{12} \\ 0 & 0 & 1\end{pmatrix}
=\begin{pmatrix}\frac{1}{2}& \frac{1}{2} & 0\end{pmatrix}$$
? (Wondering)

 

[mathmari]

Yep. (Nod)
And note that we assume that the attempts are independent, because otherwise we wouldn't be allowed to apply this product rule.

To clarify... At the question 2 "What is the probability that the octopus learns nothing in the first 5 attempts and stays completely in level 1?" we want to calculate the possibility that in the first 5 attempts the octopus is always in level 1, right?
Or does "...stays completetly in level 1" means not only in the first 5 attempts but in each attempt?

(Wondering)

Heh. The values of those probabilities is a bit unfortunate. (Lipssealed)
We picked the leftmost column that just happened to be the same as the topmost row in this case.
But should we have the leftmost column? Or should we have the topmost row? (Wondering)

Shouldn't we calculate:
$$
\begin{pmatrix}1 & 0 &\ 0\end{pmatrix} \cdot
\begin{pmatrix}\frac{1}{2} & \frac{1}{2} & 0 \\ \frac{1}{2} & \frac{1}{12} & \frac{5}{12} \\ 0 & 0 & 1\end{pmatrix}
=\begin{pmatrix}\frac{1}{2}& \frac{1}{2} & 0\end{pmatrix}$$
? (Wondering)

Ah so we have to multiply the initial distribution from the left side with the transition matrix, right? (Wondering)

 

[I like Serena]

To clarify... At the question 2 "What is the probability that the octopus learns nothing in the first 5 attempts and stays completely in level 1?" we want to calculate the possibility that in the first 5 attempts the octopus is always in level 1, right?
Or does "...stays completetly in level 1" means not only in the first 5 attempts but in each attempt?

I don't really know what was intended with the word 'completely'.
My interpretation is that they mean after every attempt, but they could also mean before and after the 5 attempts combined.
I was hoping that you could clarify. (Worried)

Ah so we have to multiply the initial distribution from the left side with the transition matrix, right? (Wondering)

When multiplying on the left, we get the topmost row, which gives the probabilities that we either stay in level 1, or that we end up in level 2.
So yes, I think we should get the topmost row, and therefore we have to multiply on the left. (Thinking)

 

[mathmari]

I don't really know what was intended with the word 'completely'.
My interpretation is that they mean after every attempt, but they could also mean before and after the 5 attempts combined.
I was hoping that you could clarify. (Worried)

If it is intended that in each of the first 5 attempts the octopus stays in level 1 then the probability is equal to $P_{1,1}^5=\frac{1}{32}$.

If it is intended that generally he stays in level 1, so not only in the first 5 attempts but in all attempts, then we cannot say something about the probability, can we? (Wondering)

When multiplying on the left, we get the topmost row, which gives the probabilities that we either stay in level 1, or that we end up in level 2.
So yes, I think we should get the topmost row, and therefore we have to multiply on the left. (Thinking)

Ah ok!

To get the probabilities of the individual training levels after 3 attempts do we have to multiply the initial distribution on the left with the transition matrix raised to $3$, i.e. $(1, 0, 0)\cdot P^3$ ? (Wondering)

 

[I like Serena]

If it is intended that in each of the first 5 attempts the octopus stays in level 1 then the probability is equal to $P_{1,1}^5=\frac{1}{32}$.

Yep.

If it is intended that generally he stays in level 1, so not only in the first 5 attempts but in all attempts, then we cannot say something about the probability, can we?

Staying in level 1 after any number of attempts has probability $(\frac 12)^n \to 0$ if $n\to \infty$.
Beginning in level 1, and being again in level 1 after 5 attempts has the top left most probability in $P^5$, which is what you already found. (Thinking)

To get the probabilities of the individual training levels after 3 attempts do we have to multiply the initial distribution on the left with the transition matrix raised to $3$, i.e. $(1, 0, 0)\cdot P^3$ ? (Wondering)

Yep. (Nod)

 

[mathmari]

Yep.
Staying in level 1 after any number of attempts has probability $(\frac 12)^n \to 0$ if $n\to \infty$.
Beginning in level 1, and being again in level 1 after 5 attempts has the top left most probability in $P^5$, which is what you already found. (Thinking)

Yep. (Nod)

Thank you so much! (Mmm)