Re: Birthday problem for such non-uniform birthday probabilities

On Mon, 21 Nov 2005 10:30:59 -0600, "Doug" <nospam@xxxxxxxxxx> wrote:

>
>"David M Einstein" <Deinst@xxxxxxxxx> wrote in message
>news:1132586540.046923.115340@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
>>
>> Doug wrote:
>>> "Helmut Zeisel" <helmut.zeisel@xxxxxx> wrote in message
>>> news:dls5fv.5lg.1@xxxxxxxxxxxxxxxxx
>>> > Consider the birthday problem:
>>> >
>>> > There are n randomly chosen person in a room. What is the proabability
>>> > that there exist k persons who have birthday on the same day.
>>> >
>>> > I know how to compute the probability assuming a uniform birthday
>>> > distribution.
>>> >
>>> > It is reasonable that this probability increases for a non-uniform
>>> > birthday distribution.
>>> >
>>> > Where can I find a proof for this result?
>>
>> Blom, D. (1973), "A birthday problem", American Mathematical Monthly,
>> vol. 80, pp. 1141-1142
>>
>>> >
>>> > Helmut
>>>
>>> You won't, as it is also reasonable that this probability decreases for a
>>> non-uniform
>>> distribution.
>>>
>>> You need to specify the "non-uniform" distributions to determine if it
>>> increases/decreases.
>>
>> I would be very interested in seeing a distribution that decreases the
>> probability of
>> a match.
>>
>
>simple- define "distribution" as sequential days beginning on Jan 1
>

Wrong.

Remember, no matter what distribution you specify, we are selecting
randomly from it, so if k>1, repetitions are always possible.

If the distribution is not uniform, the probability of a match in k
sample elements, where n>=k>1, is always greater than it would be if
the distribution was uniform,

It's not hard to prove this in general, but as an example, assume a 2
day year and let n>=k=2.

Number the days of the year 1,2.

(Note that for this type of year, every day is either New Year's Day
or New Year's Eve)

Let p1, p2 be the probabilities of having a birthday on days 1,2
respectively.

Since n>=k=2, the probability of a match can be calculated exactly as
p1^2+p2^2.

Since p1, p2 are nonnegative,

p1^2+p2^2 >= 2*p1*p2 with equality iff p1=p2.

Then, adding p1^2+p2^2 to both sides and factoring, we get

2(p1^2+p2^2) >= (p1+p2)^2

Since p1+p2=1, we get

p1^2+p2^2 >= 1/2 with equality iff p1=p2.

Hence if the distribution is uniform, the probability of a match is
exactly 1/2, otherwise it's strictly greater than 1/2.

quasi
.

Relevant Pages

  • Re: Pigeons, People, and Priors
    ... the variance of the probability generator go to zero you have a continuum ... a random-interval 60 s schedule is not. ... The Exponential Distribution ... I probably should have used the phrase "statistical learning theory" rather ...
    (comp.ai.philosophy)
  • Re: Cantorian pseudomathematics
    ... >> I understand the probability a divides n when we have a uniform ... >> But there is no uniform distribution on N, so I don't see what Han ... no way to do that with a countable set of discrete ...
    (sci.math)
  • Re: So called "stimulus/response" models
    ... Instead of answering to each misunderstood, ironic and out of context ... Sorry, you exhibit a simplistic view of probability theory, and an even more ... of acquiring the consequences of responses. ... distribution over consequences of a given act. ...
    (comp.ai.philosophy)
  • Re: Calculus XOR Probability
    ... case where you have a uniform probability distribution over an infinite set of ... Um, I'm not a probability expert, but isn't it the case that given a ... distribution, you can say what the _expected value_ of a random ... uniform distribution will be recognisably ordinary pofnats, ...
    (sci.math)
  • Re: Cantorian pseudomathematics
    ... Han is talking about the probability that a randomly chosen ... >> segment of the naturals, and the limit of this probability as that initial ... > But there is no uniform distribution on N, so I don't see what Han ...
    (sci.math)