Welcome to our community

Be a part of something great, join today!

Expected number of questions to win a game

concept

New member
Apr 3, 2013
4
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
Feb 13, 2012
1,704
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
Apr 3, 2013
4
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
Feb 13, 2012
1,704
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
Apr 3, 2013
4
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
Feb 13, 2012
1,704
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
Apr 3, 2013
4
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?

Could you please explain?

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
Feb 13, 2012
1,704
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?

Could you please explain?

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?
In your case for the states from 1 to 9 there is at least one emerging path that conducts to the adsorbing state 10, so that they are all transient states...

Regarding 'other approaches' what I can say is that the problem can't [probably] be solved with 'conventional' statistic approaches...

Kind regards

$\chi$ $\sigma$