posted by [identity profile] at 01:02pm on 19/11/2013
Right, that sounds good to me. I assumed this would be easy, but now I think it isn't :)

An alternative way of putting it would be to say "I'm trying to collect N coupons, and every box I order has a 5/8 chance of containing a coupon". I'm not sure if that would be any easier to solve.
posted by [identity profile] at 01:04pm on 19/11/2013
I sort of assumed someone like you or Simon would come along and go 'but this is trivially equivalent to $thing' and solve it in three lines, so it's nice that no-one so far has pointed out anything Completely Obvious I'm missing...
posted by [identity profile] at 01:09pm on 19/11/2013
I feel unreasonably glowy to be included in a group with Simon :) You're the one who knows about stats :)

That's what I thought at first, but it seems statistics is full of things like the birthday paradox where it's not _that_ complicated, but "finding the proper name for it on wikipedia" is the only successful strategy to actually finding the solution, which is what someone did.

Addendum: Scratch my previous suggestion, all the formulas in wikipedia are expressed in terms of a sum from 1 to 8 of the time needed to get the N'th coupon, so you ought to be able to just drop the first few terms of the series. And it's short enough you might just be able to calculate a numerical value for 8... (Although the "how many to have a 90% chance of getting all" is a bit more complicated than "expect time to get all")
simont: (Default)
posted by [personal profile] simont at 09:34am on 20/11/2013
I've only just now seen this post :-) but here's an analytic solution of sorts.

If there's only one Octonaut you need, that's reasonably easy: ordering n Octonauts and finding that not one of them is the kind you need is equivalent to saying that all of them are chosen from the remaining 7 possibilities, so the chance of that happening is (7/8)n. Hence, getting at least one of the kind you're looking for will happen with probability (1 - (7/8)n).

And if you wanted at least one of the five kinds of Octonaut, the same reasoning would apply: you'll get at least one of them with probability (1 - (3/8)n), because the only way you can't is if all n of them are one of the 3 kinds you've got already.

(You've gone through that reasoning yourself in your original post, I know. I'm just going through it again myself as a warm-up exercise to get my head in gear.)

But if you want all of the five kinds to show up at once, that's more fiddly. I suspect an Inclusion-Exclusion Principle exercise will be required.

Start with probability 1 (all possibilities).

Subtract five lots of (7/8)n, indicating the five subsets of possibilities in which one or other of the Octonauts you want fail to show up.

Now we've double-subtracted every situation in which two desired Octonauts fail to show up. There are (5 choose 2) = 10 of those and each one has probability (6/8)n, so add 10 × (6/8)n back in.

But now we've got an extra copy of each case in which three fail to show up, so now subtract again, and so on.

So we end up with the probability of getting at least one of each of the five required Octonauts being

P = 1 - 5 × (7/8)n + 10 × (6/8)n - 10 × (5/8)n + 5 × (4/8)n - 1 × (3/8)n

And that formula gives me 0.1616 for n=10, and 0.9107 for n=30, so it agrees with your Excel solution.

I suspect there's no nice formula to invert this (i.e. to give you n when you put in P), but it's an analytic solution to half of it at least.
posted by [identity profile] at 12:15pm on 20/11/2013
Collating comments from email so I have them all in one place. You know, for all those other times I need to solve this problem ;-)

"I was briefly worried that my calculation didn't _exactly_ match
Pete's numerical Perl solution, until I realised he'd done it in a
Monte Carlo way so some deviation from the true figures is to be
posted by [identity profile] at 12:30pm on 20/11/2013
> I know nothing about monte carlo - is there a dummy's guide to what it is
> and why it's not exact?

What I meant by a Monte Carlo approach is a random approach. Pete's
program actually modelled the problem as if for real - it chose a
bunch of Octonauts _at random_, checked whether they included one of
each of the five desired kinds, and then did that over and over again
in a loop and tracked what proportion of the trials were successful.

So it's inexact simply because it depends on randomness - if he'd been
really unlucky, his program might have just happened to get one of
every kind of Octonaut in every trial by sheer luck, or get none of
them on any occasion. The best you can say about the accuracy of the
Monte Carlo approach is that there's a _high probability_ of the
experimental result being near to the exact value, and it clusters
more closely the more trials you do.

(But its great virtue is that if you can live with that uncertainty in
the output, it's able to model problems of arbitrary complexity, long
after it becomes intractable to do the maths analytically or to
iterate over absolutely all possibilities!)
posted by [identity profile] at 12:31pm on 20/11/2013

Oh, of course. He rolled lots of dice, and although that's a good way of
working out probability, it's not a great way, because you could just be
really lucky at rolling dice.
posted by [identity profile] pete stevens at 02:17pm on 20/11/2013
Hmm. My program isn't terminating - it will run until power failure if it keeps being unlucky.

But on the being lucky/unlucky. I ran 16k full trials. So the probability of coming out with the answer 5 is (5/8 . 4/8 . 3/8 . 2/8 . 1/8)^16384 which is 120 * 2^-245760 which is well below the Heisenberg limit of 6.6 * 10^-34 at which point you probably need to start worrying about the correct type of octonaut spontaneously popping into existence without having to visit Tescos.

Incidentally in 64k trails (65536) the worse results were 86, 83 and 81 purchases to get the full set.


2 3