 |
|
|
|
|
|
| |
| |
|
|
|
|
| |
| |
|
|
If you have a box with N balls numbered 1 to N, and you repeatedly pull one
out at random (replacing it each time), on average how many times would you
expect to pull out a ball until you have seen all the balls 1 to N?
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
scott wrote:
> If you have a box with N balls numbered 1 to N, and you repeatedly pull
> one out at random (replacing it each time), on average how many times
> would you expect to pull out a ball until you have seen all the balls 1
> to N?
N is trivially the lower bound.
Each ball appears with probability 1/N, so the probability for all balls
to appear (given that these events are clearly independent) in N trials
would be (1/N)^N, which is 1/(N^N).
Hmm, but wait! This does not count for ordering. There are N!
permutations of N events, so taking *that* into account, we now actually
have N! / N^N.
Now, if we perform K trails, the probability of seeing all the balls is
(N! + (K-N)!) / N^N. (Assuming K >= N.)
Assuming that by "on average" you mean "with probability > 50%", it is
now a matter of choosing K such that the above formula comes out to more
than 0.5.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
> Now, if we perform K trails, the probability of seeing all the balls is
> (N! + (K-N)!) / N^N. (Assuming K >= N.)
Can you explain how you got that formula?
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
scott wrote:
>> Now, if we perform K trails, the probability of seeing all the balls
>> is (N! + (K-N)!) / N^N. (Assuming K >= N.)
>
> Can you explain how you got that formula?
Intuitively, assuming N trials the formula is just N! / N^N, so if we
add (K-N) extra trails, you get the formula above.
On reflection, I'm not sure that's actually correct...
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
>>> Now, if we perform K trails, the probability of seeing all the balls is
>>> (N! + (K-N)!) / N^N. (Assuming K >= N.)
>>
>> Can you explain how you got that formula?
>
> Intuitively, assuming N trials the formula is just N! / N^N, so if we add
> (K-N) extra trails, you get the formula above.
>
> On reflection, I'm not sure that's actually correct...
What if K=5 and N=2? I think the answer should be a 30/32 chance of seeing
both balls, but your formula gives 8/4 !
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Invisible wrote:
> N is trivially the lower bound.
>
> Each ball appears with probability 1/N, so the probability for all balls
> to appear (given that these events are clearly independent) in N trials
> would be (1/N)^N, which is 1/(N^N).
>
> Hmm, but wait! This does not count for ordering. There are N!
> permutations of N events, so taking *that* into account, we now actually
> have N! / N^N.
>
> Now, if we perform K trails...
Let's try that again...
If we select one ball, the probability of it being ball #1 is 1/N.
If we select K balls, the probability of ball #1 appearing becomes 1/N +
1/N + 1/N + 1/N + ... K times over, minus the probability of ball #1
appearing more than once.
In other words, we have K/N - E, and I can't figure out how to compute E.
(Presumably combinatorics provides a trivial way to solve this. Too bad
I don't know combinatorics, eh?)
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
> If we select K balls, the probability of ball #1 appearing becomes 1/N +
> 1/N + 1/N + 1/N + ... K times over, minus the probability of ball #1
> appearing more than once.
>
> In other words, we have K/N - E, and I can't figure out how to compute E.
You can think of it the other way round, ie the probability of ball #1
appearing after K tries is 1 minus the probability of ball #1 not occurring
after K tries. That is 1-((N-1)/N)^K.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
scott wrote:
>> If we select K balls, the probability of ball #1 appearing becomes 1/N
>> + 1/N + 1/N + 1/N + ... K times over, minus the probability of ball #1
>> appearing more than once.
>>
>> In other words, we have K/N - E, and I can't figure out how to compute E.
>
> You can think of it the other way round, ie the probability of ball #1
> appearing after K tries is 1 minus the probability of ball #1 not
> occurring after K tries.
Ah. So instead of a chain of non-exclusive OR events, you construct a
chain of independent AND events? Ingenius...
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
scott wrote:
> If you have a box with N balls numbered 1 to N, and you repeatedly pull
> one out at random (replacing it each time), on average how many times
> would you expect to pull out a ball until you have seen all the balls 1
> to N?
I'm sure the answer is in the back of a textbook somewhere ... :)
--
~Mike
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
And lo On Wed, 17 Dec 2008 13:49:38 -0000, scott <sco### [at] scott com> did
spake thusly:
> If you have a box with N balls numbered 1 to N, and you repeatedly pull
> one out at random (replacing it each time), on average how many times
> would you expect to pull out a ball until you have seen all the balls 1
> to N?
Do a search for Coupon Collector's Problem. For equal random drawings it's
roughly nHn that is n * Sum k=1-n of 1/k multiplied by n
--
Phil Cook
--
I once tried to be apathetic, but I just couldn't be bothered
http://flipc.blogspot.com
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
And lo On Wed, 17 Dec 2008 17:08:21 -0000, Phil Cook v2
<phi### [at] nospamrocainfreeservecouk> did spake thusly:
> And lo On Wed, 17 Dec 2008 13:49:38 -0000, scott <sco### [at] scottcom> did
> spake thusly:
>
>> If you have a box with N balls numbered 1 to N, and you repeatedly pull
>> one out at random (replacing it each time), on average how many times
>> would you expect to pull out a ball until you have seen all the balls 1
>> to N?
>
> Do a search for Coupon Collector's Problem. For equal random drawings
> it's roughly nHn that is n * Sum k=1-n of 1/k multiplied by n
Brain death! - n * Sum k=1-n of 1/k
--
Phil Cook
--
I once tried to be apathetic, but I just couldn't be bothered
http://flipc.blogspot.com
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
scott wrote:
> If you have a box with N balls numbered 1 to N, and you repeatedly pull
I have often wondered this, occasionally looked for the answer, and never
really needed to know enough to work it out from first principles.
--
Darren New, San Diego CA, USA (PST)
The NFL should go international. I'd pay to
see the Detroit Lions vs the Roman Catholics.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On Wed, 17 Dec 2008 09:24:17 -0800, Darren New <dne### [at] sanrrcom> wrote:
>scott wrote:
>> If you have a box with N balls numbered 1 to N, and you repeatedly pull
>
>I have often wondered this, occasionally looked for the answer, and never
>really needed to know enough to work it out from first principles.
Strange, I've never wondered about it o_O
--
Regards
Stephen
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Invisible <voi### [at] devnull> wrote:
> If we select one ball, the probability of it being ball #1 is 1/N.
You are thinking it in the wrong way.
The very first time you select one ball, the probability it's a ball you
have never seen before is 1.
The second time you select a ball, the probability it's a ball you have
never seen before is (N-1)/N.
With the third ball, the probability is (N-2)/N. And so on.
--
- Warp
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
"scott" <sco### [at] scottcom> wrote:
> If you have a box with N balls numbered 1 to N, and you repeatedly pull one
> out at random (replacing it each time), on average how many times would you
> expect to pull out a ball until you have seen all the balls 1 to N?
For sufficiently large N, I'd expect to keep pulling out balls until I die. I
guess something in the order of N=1000 should be sufficient for this.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Warp wrote:
> You are thinking it in the wrong way.
>
> The very first time you select one ball, the probability it's a ball you
> have never seen before is 1.
>
> The second time you select a ball, the probability it's a ball you have
> never seen before is (N-1)/N.
>
> With the third ball, the probability is (N-2)/N. And so on.
As with most mathematical problems, it's trivially easy once you already
know what the answer is... :-}
(And let's not forget, I have the lowest IQ in this newsgroup...)
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Orchid XP v8 <voi### [at] devnull> wrote:
> > The very first time you select one ball, the probability it's a ball you
> > have never seen before is 1.
> >
> > The second time you select a ball, the probability it's a ball you have
> > never seen before is (N-1)/N.
> >
> > With the third ball, the probability is (N-2)/N. And so on.
> As with most mathematical problems, it's trivially easy once you already
> know what the answer is... :-}
OTOH that only tells us the probability of getting distinct balls when
taking N balls out. It doesn't tell us how many balls must be taken in
average in order to get N distinct balls.
Btw, if you didn't bother continuing that chaing of deductions, the
probability of getting all distinct balls when taking out N balls is
N!/(N^N).
--
- Warp
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
>>> In other words, we have K/N - E, and I can't figure out how to compute
>>> E.
>>
>> You can think of it the other way round, ie the probability of ball #1
>> appearing after K tries is 1 minus the probability of ball #1 not
>> occurring after K tries.
>
> Ah. So instead of a chain of non-exclusive OR events, you construct a
> chain of independent AND events? Ingenius...
Yes, it's a useful trick to remember :-)
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
>>I have often wondered this, occasionally looked for the answer, and never
>>really needed to know enough to work it out from first principles.
>
> Strange, I've never wondered about it o_O
Hehe, the exact problem I was applying it to was that I needed to save all
the possible images generated by some website, I knew there was a certain
number of possibilities and that it was random that each one appeared, so I
just wondered how many times I would need to try before I got all of them.
I didn't need to know exactly, eg if N=100, am I expecting 150 tries, 200
tries, 500 tries? But knowing the exact formula would be cool as it seemed
an interesting problem without an obvious result.
Another situation I can think of is if you need to check every item in a
physical population, but you can only select ones at random (eg tagging fish
in a lake or something).
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Am Wed, 17 Dec 2008 14:49:38 +0100 schrieb scott:
> If you have a box with N balls numbered 1 to N, and you repeatedly pull
> one out at random (replacing it each time), on average how many times
> would you expect to pull out a ball until you have seen all the balls 1
> to N?
Without looking at the other solutions (and excluding the trivial case),
I would guess, that such average number does not exist. There is the real
possibility of always pulling the same ball. In fact there is an infinite
number of such combinations, where you can pull balls without ever
getting all the balls. If the pulling of balls is truely random and
independently, such combinations are not less likely (seems unintuitive,
but there is no way of predicting which ball you will pull based on which
balls you already pulled). In this case the infinite sum is diverging and
you can't calculate an average.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Am Thu, 18 Dec 2008 02:55:41 -0500 schrieb Florian Pesth:
> In this case the infinite sum is
> diverging and you can't calculate an average.
Ah... forget that, there is also an infinite number of solutions of the
same length. Even though it is an infinite sum, one can calculate it.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
>> Do a search for Coupon Collector's Problem. For equal random drawings
>> it's roughly nHn that is n * Sum k=1-n of 1/k multiplied by n
>
>
> Brain death! - n * Sum k=1-n of 1/k
Thanks Phil, when you know what it's called it's easy to find.
So, my answer is that the expected number of drawings to get all balls is
given by:
E[T] = n*(1/1 + 1/2 + 1/3 + ... 1/n)
Cool neat little formula :-)
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
And lo On Thu, 18 Dec 2008 08:26:56 -0000, scott <sco### [at] scottcom> did
spake thusly:
>>> Do a search for Coupon Collector's Problem. For equal random drawings
>>> it's roughly nHn that is n * Sum k=1-n of 1/k multiplied by n
>>
>>
>> Brain death! - n * Sum k=1-n of 1/k
>
> Thanks Phil, when you know what it's called it's easy to find.
Indeed, one of the major difficulties in research is trying to guess what
someone else might have named their solution ;-)
> So, my answer is that the expected number of drawings to get all balls
> is given by:
>
> E[T] = n*(1/1 + 1/2 + 1/3 + ... 1/n)
>
> Cool neat little formula :-)
Yup, of course as you recognise it's only an estimate the lower bound
being n and the upper bound being infinity; there's no reason why you
can't be pulling out the same number over and over again although you
might suspect a fiddle if it yields a high mean absolute error.
--
Phil Cook
--
I once tried to be apathetic, but I just couldn't be bothered
http://flipc.blogspot.com
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
>> E[T] = n*(1/1 + 1/2 + 1/3 + ... 1/n)
>>
>> Cool neat little formula :-)
>
> Yup, of course as you recognise it's only an estimate the lower bound
> being n and the upper bound being infinity; there's no reason why you
> can't be pulling out the same number over and over again although you
> might suspect a fiddle if it yields a high mean absolute error.
On an only slightly related topic, I did manage to find this one
http://en.wikipedia.org/wiki/Benford%27s_law
without knowing what it was called beforehand.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On Thu, 18 Dec 2008 08:38:40 +0100, "scott" <sco### [at] scottcom> wrote:
>> Strange, I've never wondered about it o_O
>
>Hehe, the exact problem I was applying it to was that I needed to save all
>the possible images generated by some website, I knew there was a certain
>number of possibilities and that it was random that each one appeared, so I
>just wondered how many times I would need to try before I got all of them.
>
>I didn't need to know exactly, eg if N=100, am I expecting 150 tries, 200
>tries, 500 tries? But knowing the exact formula would be cool as it seemed
>an interesting problem without an obvious result.
>
OK, a real world problem. I don't think that I've come across the need to work
out probabilities in RL.
>Another situation I can think of is if you need to check every item in a
>physical population, but you can only select ones at random (eg tagging fish
>in a lake or something).
>
There are more things in Heaven and Earth than in my philosophy, Scott. :)
--
Regards
Stephen
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Stephen wrote:
> OK, a real world problem. I don't think that I've come across the need to work
> out probabilities in RL.
*Clearly* you're not a betting man. ;-)
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On Thu, 18 Dec 2008 12:02:19 +0000, Invisible <voi### [at] devnull> wrote:
>Stephen wrote:
>
>> OK, a real world problem. I don't think that I've come across the need to work
>> out probabilities in RL.
>
>*Clearly* you're not a betting man. ;-)
Not with anything as trivial as money. ;)
--
Regards
Stephen
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
>> *Clearly* you're not a betting man. ;-)
>
> Not with anything as trivial as money. ;)
Oh I see... You wager with beer, eh?
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On Thu, 18 Dec 2008 12:25:37 +0000, Invisible <voi### [at] devnull> wrote:
>>> *Clearly* you're not a betting man. ;-)
>>
>> Not with anything as trivial as money. ;)
>
>Oh I see... You wager with beer, eh?
Generally with mars bars.
--
Regards
Stephen
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
>> Oh I see... You wager with beer, eh?
>
> Generally with mars bars.
Eww... beer and mars bars?? o_O
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On Thu, 18 Dec 2008 12:55:00 +0000, Invisible <voi### [at] devnull> wrote:
>>> Oh I see... You wager with beer, eh?
>>
>> Generally with mars bars.
>
>Eww... beer and mars bars?? o_O
Dipso :)
--
Regards
Stephen
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
scott wrote:
> If you have a box with N balls numbered 1 to N, and you repeatedly pull
> one out at random (replacing it each time), on average how many times
> would you expect to pull out a ball until you have seen all the balls 1
> to N?
http://xkcd.com/356/
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Warp wrote:
> Invisible <voi### [at] devnull> wrote:
>> If we select one ball, the probability of it being ball #1 is 1/N.
>
> You are thinking it in the wrong way.
>
> The very first time you select one ball, the probability it's a ball you
> have never seen before is 1.
>
> The second time you select a ball, the probability it's a ball you have
> never seen before is (N-1)/N.
>
> With the third ball, the probability is (N-2)/N. And so on.
>
It is very likely that, for the third pick of a substantial N balls that
the probability is (N-2)/N. However, if the first two picks happened to
be the same, the probability would still be (N-1)/N.
Example: Lets say 100 balls, labeled 1 to 100. For the first 99 picks,
I've pulled out ball #1. That doesn't mean that, on the 100th draw, I
have (100-99)/100 chance of pulling out a ball I haven't seen. In
(N-K)/N, K needs to account for how many you've seen, not how many
previous picks have been performed. Which means to solve for K on any
draw at N=100, we have to solve this problem of how many picks it would
take for N=99. For N=99, we'd have to solve for N=98. And so on.
I remember this problem from combinatorics, I just don't remember where
my textbook is.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Sabrina Kilian <"ykgp at vtSPAM.edu"> wrote:
> Warp wrote:
> > Invisible <voi### [at] devnull> wrote:
> >> If we select one ball, the probability of it being ball #1 is 1/N.
> >
> > You are thinking it in the wrong way.
> >
> > The very first time you select one ball, the probability it's a ball you
> > have never seen before is 1.
> >
> > The second time you select a ball, the probability it's a ball you have
> > never seen before is (N-1)/N.
> >
> > With the third ball, the probability is (N-2)/N. And so on.
> >
> It is very likely that, for the third pick of a substantial N balls that
> the probability is (N-2)/N. However, if the first two picks happened to
> be the same, the probability would still be (N-1)/N.
As I said in my followup post, my suggestion gives the probability of
getting all the unique balls on the first try (iow. N!/(N^N).) It doesn't
tell how many balls you have to take out in average to see them all.
--
- Warp
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
