1
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – Yuval Filmus Oct 24 '15 at 19:08
  • 3
    $\begingroup$ 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}$$ $\endgroup$ – vonbrand Oct 25 '15 at 0:33
  • $\begingroup$ I don't understand the formula in context of the code. It seems to me that the answer is "compute $(x+y)^n$ directly". $\endgroup$ – Raphael Oct 26 '15 at 7:35
  • $\begingroup$ @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. $\endgroup$ – Yuval Filmus Oct 26 '15 at 7:43
  • $\begingroup$ If this code runs and compiles without error you can post it on codereview and ask for hints to improve this code. $\endgroup$ – miracle173 Dec 21 '15 at 16:37
2
$\begingroup$

The answer for your question How to improve with an implementation that would be based on saving computed values in an array? is to use memoization (sometimes known as dynamic programming), which incidentally is the same as saving computed values. But this is a somewhat odd solution to the problem. A better solution is computing the binomial coefficient according to the formula and recursion in vonbrand's comment, and use exponentiation to complete the calculation.

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.

I'll let you come up with matching code and runtime analysis.

$\endgroup$
  • $\begingroup$ "memoization (sometimes known as dynamic programming)" -- obligatory note for the reader: some people use these terms as though they were synonyms, but they are not. $\endgroup$ – Raphael Oct 26 '15 at 7:35
  • 1
    $\begingroup$ Another hint: the binomial coefficients are symmetric. $\endgroup$ – Raphael Oct 26 '15 at 7:36

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.