2
$\begingroup$

When calculating some probabilities, I got sums of the form $$\sum_{j=0}^c {j+a+b \choose a} p^j,$$ for integers $a, b, c > 0$.

Does someone know closed forms for these values?

  • 0
    It can be expressed in terms of hypergeometric functions according to *Mathematica*, but I doubt you'd want that closed form.2010-08-25
  • 0
    Do you need a fast algorithm to compute these, Or do you absolutely need a closed form? Are there any constraints on a? b,c?2010-08-25
  • 0
    @J. Mangaldan: correct. Thanks for plugging it into Mathematica.2010-08-25
  • 0
    @Moron: I'm not sure about constraints on a, b and c yet, since the probabilities are supposed to help me finding parameters for some algorithm. A closed form would be nice for the running time analysis of the algorithm, but maybe I can live without it.2010-08-25
  • 0
    @jug: So the sum you have is the runtime of some algorithm and you want to estimate it, i.e. a BigOh estimate will do? What are the variables? (I ask this based on your last sentence).2010-08-25
  • 0
    @Moron: This probability is only one term in a bigger sum, and it's too complicated to get into details about the variables. BigOh won't do.2010-08-25
  • 0
    jug: Would you mind posting the actual "bigger sum"?2010-08-26
  • 0
    @J.Mangaldan: Sorry for the late response; I found a different approach calculating the probabilities. I doubt the "bigger sum" would help as each summand has yet another coefficient. But if you are curious: The next bigger term has $(a+1)$ in the place of $a$, $b$ might be greater and the sum is starting at $(c+2)$.2010-08-26
  • 0
    @J.Mangaldan: Thanks for your interest. In the moment I'm content with Qiaochu Yuan's answer.2010-08-26

2 Answers 2

3

I don't have time right now to work out the exact answer, but the methods and identities in the middle third of this blog post will give a closed form for fixed $a$. Use the geometric series formula to find $\sum_{j=0}^c p^{a+b+j}$, differentiate $a$ times with respect to $p$, then divide by $a! p^b$.

If a closed form for fixed $a$ isn't good enough, you should probably be more precise about which of your parameters are large and which are small.

Edit: Still don't have time to give a complete answer, but here's a fun trick. Instead of computing the answer for fixed $a$ we can write down a generating function

$$\displaystyle P_{b,c}(x) = \sum_{a=0}^{\infty} x^a \sum_{j=0}^c {a+b+j \choose a} p^j$$

then exchange the order of summation, giving

$$\displaystyle \begin{align} P_{b,c}(x) &= \sum_{j=0}^c p^j \sum_{a=0}^{\infty} {a+b+j \choose a} x^a \\ &= \sum_{j=0}^c p^j \frac{1}{(1 - x)^{b+j+1}} \\ &= \frac{1}{(1 - x)^{b+1}} \sum_{j=0}^c \left( \frac{p}{1-x} \right)^j \\ &= \frac{1}{(1 - x)^{b+1}} \frac{1 - \left( \frac{p}{1-x} \right)^{c+1}}{1 - \frac{p}{1-x}} \\ &= \frac{(1-x)^{c+1} - p^{c+1}}{(1 - x)^{b+c+1}(1 - p - x)}. \end{align}$$

Then the coefficient of $x^a$ of this rational function is the number you want. Not sure how useful that is for you, but you might be able to extract a useful asymptotic from it. The identity in the second line is the binomial theorem for negative exponents.

  • 0
    Thanks for the hint, I'll check if I can get it working. Closed for fixed $a$ might be OK (not sure yet).2010-08-25
  • 0
    That's a great blog post.2010-08-25
0

If you don't need an exact closed form or just care about the asymptotic growth Stirling's Approximation might be useful. I've found it useful in the past for generating good asymptotic bounds on similar functions.

  • 0
    If p is small then you should get a much better asymptotic just by taking c to infinity. The dominant term here is the exponential, not its coefficient (which is merely polynomial).2010-08-25