Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

there is a simple game using number of coins. initially, player has score 0 and is given three number of coins. then he flips all his coins at once. the number of coins showed head will be added to his score. if player scored 1, he will do the next flip, with only 2 coins, scoring rules are same. if player scored 2, he will do the next flip with only one coin and scoring rules are same. if player scored 3, he won. ... so, a player with score s will flip (3-s) coins, and with number of coins showed head being added to score, until his total score reaches 3. what is expected number of flips in this game?

I think this 'expected number of flips' is confusing me.

let's say his current score is 2. he can score 1 with probability of 0.5. therefore expected number of flips to win his game is 2.

let's say his current score is 1. he can score 1 with probability of 0.5 and score 2 with probability of 0.25. Now it's where I'm stuck. if he wants to score 1+1 and win the game, the probability is 0.5*0.5 - which means 4 more turns are expected to win the game in such scoring combination. if he wants to score 2 and win the game, the probability is 0.25, which means also 4 more turns are expected to win the game by flipping two coins and scoring two heads. I don't really know what else to do here.

share|improve this question
    
The game does not seem fully defined. (1( What happens if we get $0$ heads on a turn? Prsumably we flip again, same conditions. (2) Do we count number of flips, so $3$ for first round, or do we count the number of rounds? (3) What happens if we go "over," that is, jump from $2$ to $4$? –  André Nicolas Nov 19 '12 at 3:01
    
1) if you get 0 heads, flip again. 2) number of round. 3) we can't go over, since we're flipping (3-s) coins. –  thkang Nov 19 '12 at 3:13

1 Answer 1

up vote 0 down vote accepted

The following is a general-purpose approach. At any time, our score (State) is $0$, $1$, $2$, or $3$. Let $a$ be the expected number of additional rounds needed if we are in State $0$, $b$ be the expected number of additional rounds needed if we are in State $1$, and $c$ the expected number of additional rounds needed if we are in State $2$. We only want to find $a$, but $b$ and $c$ will be useful.

Suppose we are in State $0$. Flip. This has a cost of $1$ (round). With probability $\frac{1}{8}$ we get $0$ heads. Then we stay in State $0$, and our expected number of additional rounds needed is $a$. With probability $\dfrac{3}{8}$ we get $1$ head, and enter State $1$, and our expected number of additional rounds becomes $b$. With probability $\dfrac{3}{8}$ we get $2$ heads, and enter State $2$, with expected additional rounds needed equal to $c$. Finally, with probability $\dfrac{1}{8}$ the game is over, no additional rounds needed. We have obtained the equation $$a=1+\frac{a}{8}+\frac{3b}{8}+\frac{3c}{8}.$$

Suppose we are in State $1$. Flip (cost, $1$ round). With probability $\dfrac{1}{4}$, we remain in State $1$, and the expected number of additional rounds needed is $b$. With probability $\dfrac{2}{4}$ we enter State $2$, and the expected number of additional rounds needed is $c$. With probability $\dfrac{1}{4}$ the game is over. So $$b=1+\frac{b}{4}+\frac{2c}{4}.$$

Finally, suppose we are in State $c$. The same reasoning shows that $$c=1+\frac{c}{2}.$$

It is almost obvious that $a$, $b$, and $c$ are finite. Under the assumption that they are, to find $a$, $b$, and $c$ we only need to solve a simple system of $3$ linear equations in $3$ unknowns.

share|improve this answer
    
thank you. It wasn't obvious for me when I started thinking about this, but after your explanation it is crystal clear. It is used to solve this: projecteuler.net/problem=323 –  thkang Nov 20 '12 at 4:08
    
@thkang: For a variant of your coin problem in which the numbers are very large, one might have to use efficient techniques to solve the linear algebra problem. There is a huge amount of theoretical and practical work that deals with Markov chains and their transition probabilities. –  André Nicolas Nov 20 '12 at 4:24

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.