# $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>?$

$$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 .

-
This looks like it came from the birthday problem, which you can see at en.wikipedia.org/wiki/Birthday_problem –  Ross Millikan Jun 2 '11 at 16:57
@Ross It is amazing how all these introductory problems have names and their own wikipedia articles. You are right of course, and thanks for telling me the general name. I am reading it now. –  kuch nahi Jun 2 '11 at 16:59
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. –  Ross Millikan Jun 2 '11 at 17:02

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,

-
To be fair, that isn't the "derivative" of $n!$, that is the derivative of a specific function which interpolates $n!$. Discrete functions don't have derivatives. –  Aaron Jun 2 '11 at 17:41
@Aaron. That is why I put it in quotations, and said "to make complete sense of this we would have to discuss the Gamma Function." –  Eric Naslund Jun 2 '11 at 17:44
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. –  Aaron Jun 2 '11 at 17:58

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}<q_n$, 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.

-
so if I didnt know the answer, only way is to calculate the $p_n$'s until I hit a value $>0.5$? –  kuch nahi Jun 2 '11 at 17:10
@yayu: or to use the approximations on the Wikipedia page. If you want to change the value 365, there is information under generalizations –  Ross Millikan Jun 2 '11 at 17:21
@ Ross Millikan: The approximation on the Wikipedia does work quite well, but it is only an approximation. To use it to determine any specific $n$ such that $p_n>1/2$, you would need to have good information on the accuracy of the approximation or to know that the approximation was an upper bound: if each term in a product was off by even 1%, multiplying them together would yield a fairly significant error. To find the minimal such $n$, you would need either very very accurate knowledge of the error term or a brute force calculation. That said, the approximation does work surprisingly well. –  Aaron Jun 2 '11 at 17:33
Surprisingly well? Maybe at first sight but not so much on a second thought. To wit, once the argument explained on the wikipedia page ensures that the optimal $n$ is such that $n(n-1)\le c_0$ for a given $c_0$, hence $n\ge23$, one knows that the product of terms $1-u$ involves only terms $0<u\le 23/365$. But on this interval, $1-u\ge\exp(-t_0u)$ with $t_0=1.033$. This means that the optimal $n$ is such that $n(n-1)\ge c_0/t_0$. The relative difference between the upper bound and the lower bound is about $3\%$ and, numerically, this is enough to show that the optimal $n$ is indeed $n=23$. –  Did Jun 2 '11 at 18:02
@Didier First, I believe that counts as knowing extra information about the approximation. I do quite like it, though. Second, I meant more generally that, when you are using approximations, there are limits to their usefulness in the absence of error approximations. By surprisingly well, I don't mean that it defies explanation here, I mean that there is an explanation that wouldn't necessarily hold in other situations. Of course, how well does this work for finding $p_n>0.99?$ It is surprising not because of specifics, but because of generalities. –  Aaron Jun 2 '11 at 18:29