0
$\begingroup$

I've got a problem that looks like $$y = \sum\limits^x_{i=0} { a \choose i } b^i$$ where $a, b$ are constant. I'd like to rewrite this equation to define $x$ in terms of $y$, to directly compute the $x$ that belong to certain values of $y$.

If I use the Binomial identity $(1 + b)^a = \sum^\infty_{i=0} { a \choose i}b^i$, I can write the problem as $$y = \sum\limits^x_{i=0} { a \choose i } b^i= \sum^\infty_{i=0} {a \choose i}b^i - \sum^\infty_{i=x+1} {a \choose i}b^i = (1+b)^a - \sum^\infty_{i=x+1} {a \choose i}b^i $$ but that doesn't get me much further...

$\endgroup$
  • $\begingroup$ So just to clarify, you want to calculate $x(y)$, right? $\endgroup$ – Ali Jun 29 '18 at 11:51
  • $\begingroup$ That's correct. $\endgroup$ – Thom Wiggers Jun 29 '18 at 14:37
  • 1
    $\begingroup$ There is no closed-form of $y(x)$, and even less of the inverse. $\endgroup$ – Yves Daoust Jun 29 '18 at 14:40
  • $\begingroup$ That's unfortunate... I'll just have to brute force it then (luckily $x$ won't be that large) $\endgroup$ – Thom Wiggers Jun 29 '18 at 14:54
  • 1
    $\begingroup$ @ThomWiggers: I cannot prove this, but due to the relation with the cumulative binomial distribution, we have sufficient evidence that no easy formula is available (besides explicit summation). The normal approximation doesn't help much, as it would require the inverse of the error function. $\endgroup$ – Yves Daoust Jun 29 '18 at 15:13
1
$\begingroup$

Set $\dfrac p{1-p}=b$ and write

$$y=\sum_{i=0}^x\binom aib^i=\sum_{i=0}^x\binom ai\frac{p^i}{(1-p)^i}=\frac 1{(1-p)^a}\sum_{i=0}^x\binom ai p^i(1-p)^{a-i}.$$

Then $y$ is a scaled cumulative binomial distribution, which can be denoted $(1-p)^aF(x;n,p)$.

The inverse can be expressed as

$$x=F^{-1}\left(\frac y{(1-p)^a};n,p\right)$$ and there is no explicit formula.


If what you are after is a computation algorithm (which I suspect), a possible way is to precompute and store the partial sums up to the maximum $x$ and answer queries by dichotomic search.

$\endgroup$
  • $\begingroup$ I assume $F$ is the error function you mentioned in your comment? I'm indeed after the results of $x(y)$ much more than I want a formula, but a formula would've been nice. It seems I'm out of luck though – I'll just put a table in my thesis. Thanks! $\endgroup$ – Thom Wiggers Jun 29 '18 at 16:28
  • $\begingroup$ @ThomWiggers: no, ther error function is $\text{erf}$. $\endgroup$ – Yves Daoust Jun 29 '18 at 17:32

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.