Extra exercise during class

[Mister_JWO]

Hello everyone

During class our math teacher gave us an extra exercise to make this week. We can use every source we want to find the solution. Can someone help me with the work method to solve this problem?

A man is participating in a television program. He has to follow a way and on 4 points he has to do a task. When he fails a task he has to go back to point 1. On the first point he has 85% chance to succeed, on the second point 65%, on the third point 45% and on the fourth point he has 25% chance to succeed. When he has passed the fourth point he wins. How much task has the man in average to do before he wins?

I’ve put it already into a graph to make it more visual:


Thank you very much.

 

[blamocur]

I would consider Markov chain -- are you familiar with those?

 

[Mister_JWO]

I know a little bit how Markov chains work, but not very well. And doesn't it take to long to work it out till the chances are negligible?

 

[blamocur]

I know a little bit how Markov chains work, but not very well. And doesn't it take to long to work it out till the chances are negligible?

It does take long if one does it by hand, but if you are allowed to use a computer you can do relatively fast: my Python script take less than 0.5 seconds.

 

[blamocur]

It does take long if one does it by hand, but if you are allowed to use a computer you can do relatively fast: my Python script take less than 0.5 seconds.

Another data point: my brute-force simulation script takes about 15 seconds for 1 million tries but has about 0.3% relative error.

 

[Mister_JWO]

We have kind to prove with intermediate steps how we get to the answer, so we can't really do it with a python script.

 

[blamocur]

It does take long if one does it by hand, but if you are allowed to use a computer you can do relatively fast: my Python script take less than 0.5 seconds.

On the second thought, you can do this without a computer, but will have to do some matrix manipulation.
Another hint: can you handle infinite matrix sums?

 

[Mister_JWO]

What do you mean by matrix manipulation?
And I had never heard before fron infinite matrix sums?

But when I add some matrices and some powers of matrices how am I able to read the amount of tasks it takes to win the program out of it?

 

[blamocur]

On the third thought, you can do it without Markov chains, but play some (recursive) tricks with infinite sums. Let me know if you need more hints.

 

[JeffM]

The probability of doing all four tasks is 0.85 * 0.65 * 0.45 * 0.25 [imath]\approx[/imath] 1/16. Thus, the probability of failing [imath]\approx[/imath] 15/16.

If we treat failures as independent events, what might we do?

 

[BigBeachBanana]

Consider the transition matrix [imath]P[/imath]:
[math]P=\begin{bmatrix} .15 & .85 & 0 & 0 & 0\\ .35 & 0 & .65 & 0 & 0\\ .55 & 0 & 0 & .45 & 0\\ .75 & 0 & 0 & 0 & .25\\ 0 & 0 & 0 & 0 & 1\\ \end{bmatrix}[/math]
Let [imath]N[/imath] be a sub-matrix of [imath]P[/imath] without the absorbing state:
[math]N=\begin{bmatrix} .15 & .85 & 0 & 0 \\ .35 & 0 & .65 & 0 \\ .55 & 0 & 0 & .45 \\ .75 & 0 & 0 & 0 \\ \end{bmatrix}[/math]
Find [imath]F=(I-N)^{-1}[/imath], the fundamental matrix of [imath]P[/imath]. The sum of the top row of matrix [imath]F[/imath] is the expected number of tasks needed to win.

 

[Mister_JWO]

Thank you very much. But why do you have to do F to the power of negative 1, because I don't really understand and I want to explain it in my answer.

 

[BigBeachBanana]

Thank you very much. But why do you have to do F to the power of negative 1, because I don't really understand and I want to explain it in my answer.

You haven't stated what math class you're taking (and at what level). The theory behind it requires knowledge in Linear Algebra and Stochastic Processes. Here's a link that explains it.

 

[blamocur]

Thank you very much. But why do you have to do F to the power of negative 1, because I don't really understand and I want to explain it in my answer.

"Hint" : [math](I-N)^{-1} = \sum_{k=0}^\infty N^k[/math]