## 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

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!)

January 18, 2017 at 11:06 am

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.

May 27, 2016 at 10:00 am

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)

May 27, 2016 at 11:52 am

And how did they do in the exam?

May 28, 2016 at 6:49 am

badly …..