![](/i/fill.gif) |
![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
On Thu, 18 Dec 2008 08:38:40 +0100, "scott" <sco### [at] scott com> 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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
On Thu, 18 Dec 2008 12:02:19 +0000, Invisible <voi### [at] dev null> 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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
>> *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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
On Thu, 18 Dec 2008 12:25:37 +0000, Invisible <voi### [at] dev null> 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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
>> 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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
On Thu, 18 Dec 2008 12:55:00 +0000, Invisible <voi### [at] dev null> 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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
Warp wrote:
> Invisible <voi### [at] dev null> 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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
Sabrina Kilian <"ykgp at vtSPAM.edu"> wrote:
> Warp wrote:
> > Invisible <voi### [at] dev null> 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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |