Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
It can be expressed in terms of hypergeometric functions according to Mathematica, but I doubt you'd want that closed form. –  J. M. Aug 25 '10 at 16:59
    
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? –  Aryabhata Aug 25 '10 at 17:09
    
@J. Mangaldan: correct. Thanks for plugging it into Mathematica. –  j.p. Aug 25 '10 at 17:21
    
@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. –  j.p. Aug 25 '10 at 17:24
    
@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). –  Aryabhata Aug 25 '10 at 17:29
show 4 more comments

2 Answers

up vote 3 down vote accepted

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.

share|improve this answer
    
Thanks for the hint, I'll check if I can get it working. Closed for fixed $a$ might be OK (not sure yet). –  j.p. Aug 25 '10 at 17:19
    
That's a great blog post. –  Rasmus Aug 25 '10 at 19:22
add comment

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.

share|improve this answer
    
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). –  Qiaochu Yuan Aug 25 '10 at 17:02
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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