1
$\begingroup$

$p_n = 1- \left( 1-\frac{1}{365}\right)\left( 1-\frac{2}{365}\right)\cdots \left( 1-\frac{n-1}{365}\right)$ Then $p_n>\frac{1}{2}$ for $n>?$

This occured in a probability problem. The result was simply stated that this is true for $n>25$. I think I can see that this expression is monotonically increasing. But I am not sure that differentiating an expression like this which is not in closed form is correct. For example, I did

$\frac{dp_n}{dn} = + \frac{1}{365}\left( 1-\frac{1}{365}\right)\left( 1-\frac{2}{365}\right)\cdots \left( 1-\frac{n-2}{365}\right)$

But I still have $n-2$ so is this derivative correct? Otherwise I do not see how this is even monotonic. What would be the correct way to use calculus for this so that I can find $n$ after which the expression is more than half. If there are any algebraic techniques I would be glad to know them.

This came from: $p_n = 1-\frac{^{365}P_n}{365^n}$ where $^nP_x$ is the number of x-permutations of n objects .

  • 0
    Generally, when taking a derivative, you need to take it with respect to a variable that can take a continuous range of values. If you use Stirling's approximation, you can take it to a function of $n$ that has a natural extension to allow $n$ to take real values.2011-06-02

2 Answers 2

6

It is worth taking a look at this Wikipedia page: The Birthday Problem.

It turns out, the answer is $n\geq 23$ rather then $25$. Your derivative is not correct at all, think about taking the derivative of $n!$. It is not just $(n-1)!$, there are more complicated things going on here. The "derivative" of $n!$ is actually $n!\left(-\gamma +\sum_{k=1}^n \frac{1}{k}\right)$ where $\gamma$ is the Euler-Mascheroni constant. To say this concretely, and make complete sense of this, we would have to discuss the Gamma function, and its logarithmic derivative, the Digamma function.

Back to your problem, how do we find it is $n=23$? Probably the easiest way is to check numerically, and note that the function is monotonically increasing.

A very nice way of getting $23$ is also explained in the wikipedia article. See this. That approach is due to Paul Halmos, and uses simple approximations.

Hope that helps,

  • 0
    I know you did. But this doesn't really generalize. To talk about the "derivative" of a sequence (even in quotations) is dangerous, at least when you are talking to someone who might think that sequences have derivatives. It is sort of okay for $n!$, as the gamma function is the unique interpolation satisfying a few natural properties, and no experienced mathematician will be confused, but talking about these things casually is pedagogically unsound unless you really know your audience.2011-06-02
1

Here you have given $p_n$ as a sequence, not as a continuous function. You can't take the derivative at $x$ unless you have a function defined for every real number close to $x$.

If you want to see that the $p_n$ is increasing, look at $q_n=1-p_n$. Then $q_{n+1}=q_n \left(1-\frac{n}{365}\right)$. As long as $1\leq n \leq 365$, you are multiplying a positive number by something less than $1$, and thus $q_{n+1}, hence $p_{n+1}>p_n$.

All bets are off when $n>365$, as $q_n$ will start changing signs and will eventually start growing in size.

The fact that $p_n>1/2$ when $n>25$ follows from calculating $p_{25}$ and using the fact that the sequence is increasing.

  • 0
    Sorry but, generalities not being my cup of tea, I will stick to the case at hand. In this context I find the invocation of *experts* and *uninitiated* rather strange: the most uninitiated reader of the wikipedia page can read there the observation that $1-x\le\exp(-x)$ (note the inequality sign, not to be confused with an approximation sign), which is all that is needed. So in the end, I do not understand your remark to Ross (which he probably did not get because of the extra space you left between the @ sign and his name). Enough for me.2011-06-02