**O**n the Riddler of last week, first a birthday puzzle:

*Given a group of 23 persons, what is the probability of observing three pairs of identical birthdays?*

which can be found by a quick simulation as

ave=0
for (t in 1:1e6){
dupz=dates[duplicated(sample(1:365,23,rep=TRUE))]
ave=ave+as.integer((length(dupz)==3)&
(length(unique(dupz))==3))}}
ave/M

returning a value of 0.0183, but which combinatoric resolution I could not fully fathom without a little help from a friend (-ly blog). I had the multinomial coefficient

for the allocation of the 23 persons to one of the three pairs or none, as well as the probability

but I had forgotten the 3! in the denominator for the permutations of the three pairs, which leads again to

A question that also led to an unsolved question: in the even this probability was much smaller, what is an easy way into constructing a more efficient importance sampler?

The second riddle was just as easy to code in R:

*A game of tag goes by the following rules: (i) anyone untagged can tag anyone untagged; (ii) anyone tagged by a player tagged gets untagged; (iii) the winner is the last untagged player. What is the expected number of runs for N players?*

The outcome of

game=function(N=12){
a=rep(0,N);T=0
while (sum(a==0)>1){
ij=sample((1:N)[a==0],2)
a[ij[2]]=ij[1];a[a==ij[2]]=0
T=T+1}
return(T)}

leads to an average value of

but I had no clear quick explanation for the doubling phenomenon. Until I picked a pen and a sheet of paper and drew the last steps of the game: to decrease down to 1, the size of the untagged survivors has to get through …,3,2 and *each time* the eliminated player needs to have tagged no other player since otherwise the population grows again. This has to apply all the way to the second round, where N-1 players remain and the one tagged needs to be anyone but the one who tagged the first one. And so on…

### Like this:

Like Loading...