Probability.

[M R]

A spinner has three possible outcomes which occur with probabilities a, b and c where a+b+c=1.

What is the expected number of spins required until all three outcomes are seen?

There's an easy way and a harder way to do this. Guess which I did first.

 

[Opalg]

A spinner has three possible outcomes which occur with probabilities a, b and c where a+b+c=1.

What is the expected number of spins required until all three outcomes are seen?

There's an easy way and a harder way to do this. Guess which I did first.

This is a variation on the coupon collector's problem. In the case when all the probabilities are equal ($a=b=c=1/3$), the expected number of spins is $3\bigl(1 +\frac12 + \frac13) = \frac{11}2.$

In the general case, I certainly don't see an easy way to approach the problem, and I don't get an easy-looking formula for the answer.

Write $A$, $B$, $C$ for the outcomes with probabilities $a$, $b$, $c$ respectively. If the first spin gives an $A$, then the expected number of spins until a $B$ or $C$ occurs is $\dfrac1{b+c}$. The probability that this outcome is a $B$ is $\dfrac b{b+c}$, in which case the expected number of further spins until a $C$ turns up is $1/c.$ And the probability that a $C$ occurs before a $B$ is $\dfrac c{b+c}$, in which case the expected number of further spins until a $B$ turns up is $1/b.$ Therefore the total expected number of spins for all three outcomes to occur (given that the $A$ appears first) is $$1 + \frac1{b+c}\Bigl(\frac b{b+c}\,\frac1c + \frac c{b+c}\,\frac1b\Bigr) = 1 + \frac{b^2+c^2}{(b+c)^2bc} = \frac1{bc} - \frac2{(1-a)^2}$$ (in the last step, I have written the $b^2+c^2$ in the numerator as $(b+c)^2 - 2bc$, and in the denominator $b+c = 1-a$).

Multiply that by $a$, which is the probability of the $A$ occurring first, add two similar terms for the probabilities of $B$ or $C$ occurring first, and you get the answer for the expected number of spins as $$ 1 + \frac{a^2+b^2+c^2}{abc} - 2\biggl(\frac a{(1-a)^2} + \frac b{(1-b)^2} + \frac c{(1-c)^2}\biggl).$$

That looks messy, not the sort of thing that you could find easily? But it does reduce to $11/2$ when $a=b=c=1/3$, which makes me think that it should be correct.

 

[M R]

Hi Opalg

Maybe it wasn't easy but it was much easier than the other method which I will post if no one else does.

Your formula does give the right answer for a=b=c but not for other possibilities.

For comparison purposes:

a=1/2, b=1/3, c=1/6 should give 73/10

and

a=9/20, b=9/20, c=1/10 should give 353/33.

 

[Opalg]

Your formula does give the right answer for a=b=c but not for other possibilities.

For comparison purposes:

a=1/2, b=1/3, c=1/6 should give 73/10

and

a=9/20, b=9/20, c=1/10 should give 353/33.

Stupid stupid mistake! My method was correct but I left out a $+$ sign, converting a sum into a product. The expression $$1 + \frac1{b+c}\Bigl(\frac b{b+c}\,\frac1c + \frac c{b+c}\,\frac1b\Bigr)$$
(for the expected number of spins for all three outcomes to occur, given that the $A$ appears first) should have been $$1 + \frac1{b+c} + \Bigl(\frac b{b+c}\,\frac1c + \frac c{b+c}\,\frac1b\Bigr) = 1 + \frac{bc + b^2+c^2}{(b+c)bc} = 1 + \frac{(b+c)^2 - bc}{(b+c)bc} = 1 + \frac{b+c}{bc} - \frac1{b+c}. $$ The answer for the total expected number of spins then comes out as $$ 1 + \frac{a(b+c)}{bc} + \frac{b(c+a)}{ca} + \frac{c(a+b)}{ab} - \frac a{b+c} - \frac b{c+a} - \frac c{a+b}.$$ That gives values agreeing with your results for a=1/2, b=1/3, c=1/6 and for a=9/20, b=9/20, c=1/10.

 

[M R]

The history of this problem (for me personally):

On another forum someone posted a 'hard probability question'. It was the a=b=9/20, c=1/10 case. Looking back at that forum I see that I managed to get an answer six days later.

Months later I saw a post on MHF which taught me a better approach so I went back and did it again, the easy way. Unfortunately I can't view MHF to find out who my teacher was.

I think it's essentially the same as Opalg's method but here's the 'easy' method as I did it:

Spoiler

Events A, B and C have probabilities a, b and c.

Let the expected waiting time until A occurs be [tex]E(W_A)[/tex],

and the expected waiting time until A and B occur be [tex]E(W_{AB})[/tex] and so on.

[tex]E(W_{AB})=c(1+E(W_{AB}))+a(1+E(W_B))+b(1+E(W_A))[/tex]

[tex]E(W_{AB})=c(1+E(W_{AB}))+a(1+1/b)+b(1+1/a)[/tex]

[tex]E(W_{AB})=1 +cE(W_{AB})+a/b+b/a[/tex]

[tex]E(W_{AB})=\frac{1+a/b+b/a}{1-c}[/tex]

Similarly

[tex]E(W_{AC})=\frac{1+a/c+c/a}{1-b}[/tex]

and

[tex]E(W_{BC})=\frac{1+b/c+c/b}{1-a}[/tex]

Then [tex]E(W_{ABC})=a(1+E(W_{BC}))+b(1+E(W_{AC}))+c(1+E(W_{AB}))[/tex]

and the method I used at first:

Spoiler

By thinking about how the sequence ends I knew I wanted all the ways to get As and Bs ending with C etc.

ABC
BAC

AABC
ABAC
BAAC

ABBC
BABC
BBAC

etc.

This led me to the sum

[tex]\displaystyle E(W)=\sum_{n=2}^\infty (n+1) \sum_{r=1}^{n-1} \binom{n}{r}(a^rb^{n-r}c+a^rc^{n-r}b+b^rc^{n-r}a)[/tex]

[tex]\displaystyle =\sum_{n=2}^\infty (n+1) [ c((a+b)^n-a^n-b^n) +b((a+c)^n-a^n-c^n)+a((b+c)^n-b^n-c^n)][/tex]

This sum involves a number of geometric progressions and a number of sums of another type.

The other type is of the form [tex]\displaystyle S=\sum_{n=2}^\infty n x^n[/tex].

Multiplying by [tex]\displaystyle x [/tex] gives [tex]\displaystyle Sx=\sum_{n=2}^\infty n x^{n+1}[/tex] and so [tex]\displaystyle S-Sx = 2x^2+x^3+x^4+...[/tex]

[tex]\displaystyle S(1-x)=x^2 + \frac{x^2}{1-x}[/tex] and [tex]\displaystyle S=\frac{x^2}{1-x}+\frac{x^2}{(1-x)^2}[/tex]

Applying this formula, together with the formula for the sum of a GP we get

[tex]\displaystyle E(W)=[/tex]

[tex]\displaystyle (a+b)^2-\frac{ca^2}{1-a}-\frac{cb^2}{1-b}[/tex]

[tex]\displaystyle + (a+c)^2-\frac{ba^2}{1-a}-\frac{bc^2}{1-c}[/tex]

[tex]\displaystyle + (b+c)^2-\frac{ab^2}{1-b}-\frac{ac^2}{1-c}[/tex]

[tex]\displaystyle +(a+b)^2(1+1/c)-c\left(\frac{a^2}{1-a}+\frac{a^2}{(1-a)^2}+\frac{b^2}{1-b}+\frac{b^2}{(1-b)^2}\right)[/tex]

[tex]\displaystyle +(a+c)^2(1+1/b)-b\left(\frac{a^2}{1-a}+\frac{a^2}{(1-a)^2}+\frac{c^2}{1-c}+\frac{c^2}{(1-c)^2}\right)[/tex]

[tex]\displaystyle +(b+c)^2(1+1/a)-a\left(\frac{b^2}{1-b}+\frac{b^2}{(1-b)^2}+\frac{c^2}{1-c}+\frac{c^2}{(1-c)^2}\right)[/tex]

What a mess!

This could be simplified using [tex]\displaystyle a+b+c=1[/tex] but having checked it against the first method I'm happy that it's correct and I'm not interested in doing the simplification.