# How to improve the binomial algorithm?

Good evening!

I tried to model the Binomial theorem, that allows to expand any power of x + y into a sum of the form:

$$(x+y)^n = {n \choose 0}x^n y^0 + {n \choose 1}x^{n-1}y^1 + {n \choose 2}x^{n-2}y^2 + \cdots + {n \choose n-1}x^1 y^{n-1} + {n \choose n}x^0 y^n$$

Then, tried to estimate the number of recursive calls that would be used by the method call binomial1(100, 50, .25)

public class Binomial {

public static double binomial1(int N, int k, double p) {
if (N == 0 && k == 0) return 1.0;
if (N < 0 || k < 0) return 0.0;
return (1.0 - p) *binomial1(N-1, k, p) + p*binomial1(N-1, k-1, p);
}
public static void main(String[] args) {
int N = Integer.parseInt(args[0]);
int k = Integer.parseInt(args[1]);
double p = Double.parseDouble(args[2]);
StdOut.println(binomial1(N, k, p));
StdOut.println(binomial2(N, k, p));
}

}


I think I have $2^N$ recursive calls of binomial1, that is to say 10000 calls with our exemple. Because of this line:

return (1.0 - p) *binomial1(N-1, k, p) + p*binomial1(N-1, k-1, p);


I would like to explain it better... I think my answer is too intuitive: each time I call the algorithm, I call it twice until N reach 0.

How to improve with an implementation that would be based on saving computed values in an array?

• What is your question? How to calculate the probability that a binomial random variable $B(n,p)$ equals $k$? Please try to explain yourself better. Also, please replace your C++/Java code with pseudocode. – Yuval Filmus Oct 24 '15 at 19:08
• The binomial coefficient is really $$\binom{n}{k} = \frac{n^{\underline{k}}}{k!}$$, where $x^{\underline{k}} = x (x - 1) \dotsm (x - k + 1)$, which gives you the nice recursion $$\binom{n}{k + 1} = \binom{n}{k} \cdot \frac{n - k}{k + 1}$$ – vonbrand Oct 25 '15 at 0:33
• I don't understand the formula in context of the code. It seems to me that the answer is "compute $(x+y)^n$ directly". – Raphael Oct 26 '15 at 7:35
• @Raphael The program itself reads $n,k,p$ as input and outputs $\binom{n}{k} p^k (1-p)^{n-k}$. But it looks like an exercise in dynamic programming. – Yuval Filmus Oct 26 '15 at 7:43
• If this code runs and compiles without error you can post it on codereview and ask for hints to improve this code. – miracle173 Dec 21 '15 at 16:37

For completeness, here are the formula and the recursion: $$\binom{n}{k} = \frac{n \cdot (n-1) \cdots (n-k+1)}{k \cdot (k-1) \cdots (1)}, \qquad \binom{n}{k+1} = \frac{n-k}{k+1} \binom{n}{k}.$$
There are many ways to use memoization here. One natural way is to loop on n, and compute all values of binomial1 in sequence. This only requires knowing the values of binomial1 on n-1, which you save in an array. (Similarly you store the new values in a second array.) As an optimization, you only need to compute these values up to the given k.