In previous question, I asked how one would simplify the following equation for the case where the variables are very big:

$\sum\limits^{k}_{i=m}(N-i)^{k-i}(\frac{1}{N})^k\frac{k!}{(k-i)!i!} \leq a$

This answer was basically to use an approximation like Stirling's formula. Having implemented this with some code, it still takes too long to find the maximum value of N so that the inequality holds true. Therefore, I need a direct solution for N. So the new question is, how would you go about solving this equation for N?

(Some simplifications are acceptable, but I would like to have it as accurate as possible. The values this equation will be used for are all in the 100,000-1,000,000 range, except $m$, which is in the 100s range.)

  • $\begingroup$ What can be said about m and k? Because if m were smal, the sum with m = 0 can be probably computed explicitely using exponential generating functions (e.g.f.) and then you can approximate only the first terms. Of course, if m is too big, this is not feasible. Also if k is too big, the solution with e.g.f. might not help you much. $\endgroup$
    – Marek
    Nov 12 '10 at 15:40

Now you are basically into root finding. I love Numerical Recipes. I have had the book over 30 years. Good discussion of the techniques and code supplied in various languages. Your formula should be an easy one. Other numerical analysis books will work, too.

A small thought: if m is as small as you say, there might be some algebraic simplification in making it 1. I haven't found it, but others are better at these combinatoric identities.

If you are actually doing the sum every time, you might be able to identify the range of i that is the big contribution. It looks like it should be somewhat below k/2. You can probably reduce the terms in the sum by a large factor, at least to get close to N. Then use the full formula for final refinement. And take the N^(-k) out of the sum.

  • $\begingroup$ I've finally been able to get the book, Numerical Recipes, but since I'm new to the field, would you mind pointing me to the appropriate chapter for this kind of problem? Is it the chapter on root finding? $\endgroup$
    – Herman
    Oct 14 '10 at 13:28
  • $\begingroup$ By simple variable substitution I've managed to reduce the formula to the following: $-a(x+k)^k + \sum\limits_{j=0}^{y}x^{j}\bigl(\frac{k}{k-j}\bigr) \leq 0$. This seems right in the domain of root finding, I see. $\endgroup$
    – Herman
    Oct 14 '10 at 14:01
  • $\begingroup$ Sorry, that formula was meant to be: $-a(x+k)^k + \sum\limits_{j=0}^{y}x^{j}\binom{k}{k-j} \leq 0$ $\endgroup$
    – Herman
    Oct 14 '10 at 14:08
  • $\begingroup$ Yes, you have a one-dimensional root finding problem. If you use Stirling for the k choose k-j you can consider the variables to be reals instead of integers. My edition has Brent's method at the bulletproof recommendation and I have used it successfully. $\endgroup$ Oct 14 '10 at 22:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.