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?

$\endgroup$
9
  • $\begingroup$ It can be expressed in terms of hypergeometric functions according to Mathematica, but I doubt you'd want that closed form. $\endgroup$ Aug 25, 2010 at 16:59
  • $\begingroup$ 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? $\endgroup$
    – Aryabhata
    Aug 25, 2010 at 17:09
  • $\begingroup$ @J. Mangaldan: correct. Thanks for plugging it into Mathematica. $\endgroup$
    – j.p.
    Aug 25, 2010 at 17:21
  • $\begingroup$ @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. $\endgroup$
    – j.p.
    Aug 25, 2010 at 17:24
  • $\begingroup$ @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). $\endgroup$
    – Aryabhata
    Aug 25, 2010 at 17:29

2 Answers 2

3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Thanks for the hint, I'll check if I can get it working. Closed for fixed $a$ might be OK (not sure yet). $\endgroup$
    – j.p.
    Aug 25, 2010 at 17:19
  • $\begingroup$ That's a great blog post. $\endgroup$
    – Rasmus
    Aug 25, 2010 at 19:22
0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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). $\endgroup$ Aug 25, 2010 at 17:02

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .