# Expected number of questions to win a game

#### concept

##### New member
Let, a person is taking part in a quiz competition.
For each question in the quiz, there are 3 answers, and for each correct answer he gets 1 point.
When he gets 5 points, he wins the game.
If he gives 4 consecutive wrong answers, then his points resets to zero (i.e. if his score is now 4 and he gives 2 wrong answers, then his score resets to 0).

My question is, on an average how much questions he needs to answer to win the game?
Someone plz help.

Last edited:

#### chisigma

##### Well-known member
Let, a person is taking part in a quiz competition.
For each question in the quiz, there are 3 answers, and for each correct answer he gets 1 point.
When he gets 5 points, he wins the game.
If he gives 2 consecutive wrong answers, then his points resets to zero (i.e. if his score is now 4 and he gives 2 wrong answers, then his score resets to 0).

My question is, on an average how much questions he needs to answer to win the game?
Someone plz help.
An important detail is missing: for each question what is the probability p of correct answer?... if p=1 then the expected number of answers is 5... of course...

Kind regards

$\chi$ $\sigma$

#### concept

##### New member
An important detail is missing: for each question what is the probability p of correct answer?... if p=1 then the expected number of answers is 5... of course...

Kind regards

$\chi$ $\sigma$
Since there are 3 choices per question, so probability of correct question is 1/3

#### chisigma

##### Well-known member
Never mind, we can indicate with p the probability of correct answer and q=1-p the probability of wrong answer at each step. The problem is a Markov chain type that uses the following state transition diagram... The probability transition matrix is...

$\displaystyle P = \left | \begin{matrix} q & p & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & q & p & 0 & 0 & 0 & 0 & 0 & 0 \\ q & 0 & 0 & p & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & q & p & 0 & 0 & 0 & 0 \\ q & 0 & 0 & 0 & 0 & p & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & q & p & 0 & 0 \\ q & 0 & 0 & 0 & 0 & 0 & 0 & p & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & q & p \\ q & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & p \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \end{matrix} \right|$ (1)

The presence of the final state 10 makes the Markov chain an Adsorbing Markov chain and, because the state 10 is the only adsorbing state we can compute the fundamental matrix N as...

$\displaystyle N = \sum_{k=0}^{\infty} Q^{k} = (I_{9}-Q)^{-1}$ (2)

... where $I_{9}$ is the 9 x 9 unity matrix and Q is the 9 x 9 matrix obtained from P deleting the last row and the last column...

$\displaystyle Q = \left | \begin{matrix} q & p & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & q & p & 0 & 0 & 0 & 0 & 0 \\ q & 0 & 0 & p & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & q & p & 0 & 0 & 0 \\ q & 0 & 0 & 0 & 0 & p & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & q & p & 0 \\ q & 0 & 0 & 0 & 0 & 0 & 0 & p & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & q \\ q & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{matrix} \right|$ (3)

Now the expected number of steps is the vector...

$\displaystyle \overrightarrow{t} = N \cdot \overrightarrow{1}$ (4)

... where $\displaystyle \overrightarrow{1}$ is the 9 x 1 'all 1' column vector. Of course the main task is the matrix inversion in (2), normally very time expensive to do by hand...

Kind regards

$\chi$ $\sigma$

Last edited:

#### concept

##### New member
The presence of the final state 10 makes the Markov chain an Adsorbing Markov chain and, because the state 10 is the only adsorbing state we can compute the fundamental matrix N as...

$\displaystyle N = \sum_{k=0}^{\infty} Q^{k} = (I_{9}-Q)^{-1}$ (2)
Thankx for ur great help.
But one question, I can't find any transient state in the matrix. Is it possible to implement the above equation if there is no transient state?

Could you please suggest me a book to read and understand this scenario of marcov chain in detail?

Regards
Concept

#### chisigma

##### Well-known member
Thankx for ur great help.
But one question, I can't find any transient state in the matrix. Is it possible to implement the above equation if there is no transient state?

Could you please suggest me a book to read and understand this scenario of marcov chain in detail?

Regards
Concept
The states from 1 to 9 are all 'transient states' and the matrix P represents the probability to pass from the state i to the state j for i=1,2,...,10 and j=1,2,...,10...

Regarding a 'good text' about Markov chain I can suggest You the following tutorial article ...

http://www.dartmouth.edu/~chance/teaching_aids/books_articles/probability_book/Chapter11.pdf

... that includes a large number of exercizes and references...

Kind regards

$\chi$ $\sigma$

#### concept

##### New member
The states from 1 to 9 are all 'transient states'
Thankx you.
From the book of Wayne winston, I find that,a state i is transient if there is a way to leave state i that never returns to state i.
I can move from state 1 to state 0 by giving 4 consecutive wrong answers and again can come back to state 1 by giving right answer. So, is it a transient state?

Another approach: I need three chances to answer a correct question. So, it will take 5*3=15 questions to get 5 points. Is it right?

#### chisigma

##### Well-known member
Thankx you.
From the book of Wayne winston, I find that,a state i is transient if there is a way to leave state i that never returns to state i.
I can move from state 1 to state 0 by giving 4 consecutive wrong answers and again can come back to state 1 by giving right answer. So, is it a transient state?

$\chi$ $\sigma$