another riddle with a stopping rule

A puzzle on The Riddler last week that is rather similar to an earlier one. Given the probability (1/2,1/3,1/6) on {1,2,3}, what is the mean of the number N of draws to see all possible outcomes and what is the average number of 1’s in those draws? The second question is straightforward, as the proportions of 1’s, 2’s and 3’s in the sequence till all values are observed remain 3/6, 2/6 and 1/6. The first question follows from the representation of the average

\mathbb{E}[N]=\sum_{n=3}^\infty \mathbb{P}(N>n) + 3

as the probability to exceed n is the probability that at least one value is not observed by the n-th draw, namely

3+(1/2)n+(2/3)n+(5/6)n-(1/6)n-(1/3)n-(1/2)n

which leads to an easy summation for the expectation, namely

3+(2/3)³/(1/3)+(5/6)³/(1/6)-(1/3)³/(2/3)-(1/6)³/(5/6)=73/10

Checking the results hold is also straightforward:

averages <- function(n=1){
    x=matrix(sample(1:3,100,rep=TRUE,prob=1:3),100,3)
    x[,1]=as.integer(x[,2]<2) x[,3]=as.integer(x[,2]>2)
    x[,2]=1-x[,1]-x[,3]
    y=apply(apply(x,2,cumsum),1,prod)
    m=1+sum(y==0)
    return(apply(x[1:m,],2,sum))}

since this gives

mumbl=matrix(0,1e5,3)
for (t in 1:1e5) mumbl[t,]=averages()
> apply(mumbl,2,mean)
[1] 1.21766 2.43265 3.64759
> sum(apply(mumbl,2,mean))
[1] 7.2979
> apply(mumbl,2,mean)*c(6,3,2)
[1] 7.30596 7.29795 7.29518

(The puzzle this week is not intelligible for someone foreign to baseball rules so I will not mention it next week!)

4 Responses to “another riddle with a stopping rule”

  1. On a different note, but recently I’m wondering more and more about MCMC work on stopping chains rather than running them till equilibrium.

    This arxiv paper makes a connection to the size of objects in a search space and their symmetries: https://arxiv.org/abs/1412.6621. It’s also like Markov chains stopped prematurely. Maybe you’d like it.

  2. BRUNERO LISEO Says:

    I have included a very similar problem in a probability test last week, taken form Grimmett and Welsh, Probability, pag 36, n.6.

    A fair die having two faces coloured blue, two red and two green, is thrown repeatedly. Find the probability that not all colours occur in the first k throws.
    Deduce that, if N is the random variable which takes the value n if all three colours occur in the first n throws but only two of the colours in the first n − 1 throws, then the expected value of N is 11/2 . (Oxford 1979M)

Leave a comment

This site uses Akismet to reduce spam. Learn how your comment data is processed.