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 .

  • 3
    This looks like it came from the birthday problem, which you can see at http://en.wikipedia.org/wiki/Birthday_problem2011-06-02
  • 0
    @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.2011-06-02
  • 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,

  • 1
    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.2011-06-02
  • 1
    @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."2011-06-02
  • 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.

  • 1
    so if I didnt know the answer, only way is to calculate the $p_n$'s until I hit a value $>0.5$?2011-06-02
  • 0
    @yayu: or to use the approximations on the Wikipedia page. If you want to change the value 365, there is information under generalizations2011-06-02
  • 0
    @ 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.2011-06-02
  • 0
    *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. 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$.2011-06-02
  • 0
    @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.2011-06-02
  • 0
    I understood what you wrote the first time, thanks. Once again my point is that, in this situation, the approximation of $1-u$ by $\exp(-u)$ is good because one uses it only for small values of $u$. Furthermore, once the upper bound $n\le23$ is rigorously proved like on the wikipedia page, one can quantify, again rigorously, how good the approximation is. In this case this is enough to prove that $n=23$ without having computed the value of a single $p_n$. .../...2011-06-02
  • 0
    .../... On a related note, I am surprised that you write that *one would need to know that the approximation [is] an upper bound*: it is, and we know it is (because $1-u$ is not only close to $\exp(-u)$, in fact $1-u\le\exp(-u)$).2011-06-02
  • 0
    @Didier I didn't say it was hard to show that it was an upper bound, just that it is an observation that needs to be made. And I know why the approximation is good, it is just that "good" has to be quantified (as you have done) to be useful. I'm not sure you get my point, so let me rephrase: mild insights which make things obvious to experts are not necessarily clear to the uninitiated, and in the absence of these observations, which sometimes go unstated or are quickly glossed over, some arguments do not work.2011-06-02
  • 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