The main content of this paper is the recursive and non-recursive implementation of Java programming binomial distribution, as follows.
Source of the problem:
Exercise 27 of Section 1.1, 4th Edition of Algorithm, Section 1.1: return (1.0 - p) * binomial(N - 1, k, p) + p * binomial(N - 1, k - 1, p);
Calculate the number of recursive calls. How did the recursive formula come from here?
Binomial distribution:
Definition: The discrete probability distribution of n independent yes/non-experiments of success times k, the probability of success in each experiment is p, which is denoted as B(n, p, k).
Probability formula: P(ξ=K)= C(n,k) * p^k * (1-p)^(nk)
Where C(n, k) = (nk) !/(k! * (nk)!), is denoted as ξ~B(n,p), expectation: Eξ=np, variance: Dξ=npq, where q=1-p.
There is a recursive formula in the probability statistics:
This is the source of the recursive form in the question.
The recursive formula comes from: C(n,k)=C(n-1,k)+C(n-1,k-1). The actual scenario is to choose k from n individuals. How many combinations are there? Arrange n people in order from 1 to n. If the kth one is not selected, you need to select k from the remaining n-1 people; if the kth one is selected, you need to select k-1 from the remaining n-1 people.
Recursive implementation of binomial distribution in the book:
public static double binomial(int N, int k, double p) { COUNT++; //Record the number of recursive calls if (N == 0 && k == 0) { return 1.0; } if (N < 0 || k < 0) { return 0.0; } return (1.0 - p) * binomial(N - 1, k, p) + p * binomial(N - 1, k - 1, p); }Experimental results:
nkp number of calls 10 5 0.25 246720 10 0.25 243553830 15 0.25 2440764535
From the results, we can see that the number of times this recursive method needs to be called is a geometric disaster, and even if n to 50 is not considered.
Improved binomial distribution recursive implementation:
private static long COUNT = 0; private static double[][] M; private static double binomial(int N, int k, double p) { COUNT++; if (N == 0 && k == 0) { return 1.0; } if (N < 0 || k < 0) { return 0.0; } if (M[N][k] == -1) { //Save the calculation result and use it directly if you have calculated it, no need to recursively calculate M[N][k] = (1.0 - p) * binomial(N - 1, k, p) + p * binomial(N - 1, k - 1, p); } return M[N][k]; } public static double Binomial(int N, int k, double p) { M = new double[N + 1][k + 1]; for (int i = 0; i <= N; i++) { for (int j = 0; j <= k; j++) { M[i][j] = -1; } } return binomial(N, k, p); }Experimental results:
nkp number of calls 10 5 0.25 10120 10 0.25 45230 15 0.25 120350 25 0.25 3204100 50 0.25 5205
From the experimental results, we can see that the number of calls is greatly reduced and the algorithm can be used.
Non-recursive implementation of binomial distribution:
In fact, instead of using recursion, directly calculating the combined numbers and factorials is faster.
//Calculate the number of combinations public static double combination(double N, double k) { double min = k; double max = Nk; double t = 0; double NN=1; double kk=1; if(min>max){ t=min; min = max; max=t; } while(N>max){//The factorial of the larger part in the denominator does not need to be calculated NN=NN*N; N--; } while(min>0){//Calculate the factorial of the smaller part kk=kk*min; min--; } return NN/kk; } //Calculate the binomial distribution value public static double binomial(int N,int k,double p) { double a=1; double b=1; double c =combination(N,k); while((Nk)>0){ //Calculate the (Nk) power of (1-p) a=a*(1-p); N--; } while(k>0){ //Calculate the k power of p b=b*p; k--; } return c*a*b; }Experimental results:
nkp binomial distribution value 10, 5, 0.25 0.05839920043945312520, 10, 0.25 0.00992227527967770650, 25, 0.25 8.44919466990397E-5
Comparing with the previous algorithm, the calculation results are correct and the running speed is very fast.
Summarize
The above is the entire content of this article about recursive and non-recursive implementation code examples of Java programming binomial distribution. I hope it will be helpful to everyone. Interested friends can continue to refer to other related topics on this site. If there are any shortcomings, please leave a message to point it out. Thank you friends for your support for this site!