Recursive and non recursive implementation code examples of binomial distribution in Java programming

The main content of this paper is the recursive and non recursive implementation of binomial distribution in Java programming, as follows.

Source of problem:

Problem 27 in Section 1.1 of the fourth edition of the algorithm: return (1.0 - P) * binomial (n - 1, K, P) + p * binomial (n - 1, K - 1, P); Calculate the number of recursive calls. How does the recursive formula come from here?

Binomial distribution:

Definition: n independent discrete probability distributions of success times K in yes / no experiments. The probability of success of each experiment is p, which is recorded as B (n, P, K).

Probability formula: P（ ξ= K)= C(n,k) * p^k * (1-p)^(n-k)

Where C (n, K) = (n-k)/ (k! * (n-k)!)， record as ξ~ B (n, P), expectation: e ξ= NP, variance: D ξ= NPQ, where q = 1-p.

There is a recursive formula in probability statistics:

This is the source of recursion in the title.

The recurrence formula comes from: C (n, K) = C (n-1, K) + C (n-1, k-1). The actual scene is k selected from n people. How many combinations are there? Arrange n people in the order of 1 ~ n. if the k-th person is not selected, you need to select k from the remaining n-1 people; If the K is selected, you need to select k-1 from the remaining n-1 individuals.

Recursive implementation of binomial distribution in the book:

Experimental results:

It can be seen from the results that the number of calls required by this recursive method is a geometric disaster, and N to 50 can't go on.

Improved binomial distribution recursive implementation:

Experimental results:

The experimental results show that the number of calls is greatly reduced and the algorithm can be used.

Non recursive implementation of binomial distribution:

In fact, it is faster to calculate the combination number and factorial directly without recursion.

Experimental results:

Compared with the previous algorithm, the calculation result is correct and the running speed is very fast.

summary

The above is all about the recursive and non recursive implementation code examples of binomial distribution in Java programming. I hope it will be helpful to you. Interested friends can continue to refer to other related topics on this site. If there are deficiencies, please leave a message to point out. Thank you for your support!