negative _binomial_distribution in C++ with examples
By Ramneeq SodhiIn this article, we are going to learn what is negative binomial distribution and how we can implement it in C++
Bernoulli Trials are experiments in which there are two possible outcomes only. One outcome is called success and the other one is called failure. The probability of success denoted by ‘p’. The probability of failure is ‘1-p’.
The probability of success always remains the same (that is ‘p’) whenever the experiment is performed and the outcomes of the experiment are always independent.
P = n-1 Cr-1 * p^r * (1 – p)^n-r
n– number of trials
r- number of success
p- the probability of success
P- negative probability
Let us understand the meaning of negative binomial distribution through an example. An experiment is to be performed multiple times (say for example ‘n’ times) where the probability of success is ‘p’ and probability of failure is ‘q’. Of course, ‘q’ is equal to ‘1-p’.
We want to find the probability wherein ‘n’ number of trials, there should be exactly ‘r’ successes, and also the last trial should be a success.
Consider the example of rolling a dice. Let us define success to be an occurrence of number three. The value of ‘p’ is 1/6 and ‘q’ is 5/6. Let us take the value of ‘n’ as nine and the value of ‘r’ as three.
Therefore, we want to find the probability of third success (occurrence of number three on the dice third time) appearing only in the last trial (that is a ninth trial).
This means that the other two successes can occur any time before the last trial but the last success should occur only and only in the last trial of the experiment.
The number of trials (denoted by ‘n’) should always be greater than or equal to the number of successes required (denoted by ‘r’). We can write ‘n’ as a sum of two variables, ‘k’ and ‘r’. (that is n = k + r).
The graph of this probability (probability for different values of ‘k’) versus ‘k’ for a fixed value of ‘r’ is called negative probability distribution. If the value of ‘r’ is changed, of course, the values of probabilities for different values of ‘k’ will change and we obtain a different graph.
Now for different values of ‘n’ (or different values of ‘k’), we have different probabilities for a fixed value of ‘r’. Consider the example of rolling dice as explained above. The value of ‘r’ in the example was taken to be three.
When we obtain three successes, we stop rolling the dice and our job is done. This is only one job. Now let us suppose there are 1000 people performing the same job. The number of trials/attempts required by every person to obtain three successes will be different. Consider the example table below to understand this better:
| Trials/Attempts required to complete the job (‘n’) | Number of people (Total = 1000) |
| 3 | 11 |
| 4 | 19 |
| 5 | 24 |
And so on.
We want to fill this table using our code. We know that for different values of ‘n’ (or different values of ‘k’), we have different probabilities as explain above. Therefore, multiply each probability with the total number of people performing the job to find the expected number of people for every value of ‘n’.
In other words for every ‘n’, find Prob(n) * 1000(Total people performing job).
After a certain value of ‘n’, the probability will start tending to zero and the expected number of people for those values will be zero.
C++ program for calculating negative binomial distribution
#include <bits/stdc++.h>
using namespace std;
/**Number of trials/attempts denoted by n*/
int n = 3;
/**Number of successes denoted by r*/
int numberOfSucessRequired = 3;
/** k = n - r */
int k = 0;
/**Probability of success denoted by p*/
double successProbability = 0.16;
int numberOfJobs = 1000;
/** Global strings to print the header of the table */
string NUM_TRIALS = "Number of trials(n)";
string K = "k(n-r)";
string PROB_DISTRIBUTION = "Negative Probability Distribution";
string NUM_PEOPLE = "Expected Number of People";
/**Table Spacing */
int tableSpacing = 4;
/**This variable indicates that the probability is now tending to zero*/
double epsilon = 0.00099;
/** function for calculating a^b*/
double power(double a, int b)
{
if (b == 0)
return 1.0;
else if (b % 2 == 0)
return power(a, b / 2) * power(a, b / 2);
else
return a * power(a, b / 2) * power(a, b / 2);
}
/** function for calculation combination ncr */
long long int calculateNcr(long long int n,
long long int denominator ,
long long int previousNcr){
long long int updatedNcr = (previousNcr*n)/denominator;
return updatedNcr;
}
/**This function calculates the probability
using the formula */
double getProbability(double ncr, double p,int r){
double probability = ncr*power(p,r)*power(1-p,n-r);
return probability;
}
void printBlankSpaces(int n){
for(int index = 0; index < n; index++){
cout<<" ";
}
}
void printString(string str) {
cout<<str;
}
void printTableRow(string colFirst,string colSecond,
string colThird,string colFourth) {
printString(colFirst);
printBlankSpaces(tableSpacing + NUM_TRIALS.length()
- colFirst.length());
printString(colSecond);
printBlankSpaces(tableSpacing + K.length()
- colSecond.length());
printString(colThird);
printBlankSpaces(tableSpacing + PROB_DISTRIBUTION.length()
- colThird.length());
printString(colFourth);
cout<<endl;
}
int main()
{
/** Question- Refer to the documentation for
the problem to be solved.*/
/** Print Headings of Table*/
printTableRow(NUM_TRIALS,K,PROB_DISTRIBUTION,NUM_PEOPLE);
/**Variable to store value of n-1Cr-1*/
double ncr;
/**This variable is used to update the value
of n-1Cr-1 after each iteration*/
int denominator = 1;
for( ; ;n++,k++,denominator++){
/**as for the first iteration 3C3 = 1*/
if(n == 3) {
ncr = 1;
} else {
/**Updating value of n-1Cr-1 as n increases
by 1 after each iteration*/
ncr = calculateNcr(n-1,denominator-1,ncr);
}
double prob =
getProbability(ncr,successProbability,numberOfSucessRequired);
/**Checks if probability tends to zero*/
if(prob <= epsilon){
break;
}
/**Multiplying probability with a total number of
jobs to get expected number of jobs for given n*/
int expectedJobsNum = prob*numberOfJobs;
/**Print table row*/
printTableRow(to_string(n),to_string(k),to_string(prob)
,to_string(expectedJobsNum));
}
return 0;
}
implementation
In the main function, there is a loop that finds the value of probability for a given value of n. Initially, the value of n is three because in the example explained above, three successes are required and therefore the minimum value of n should be three.
After this probability calculation using the formula written above, the expected number of people completing the job in ‘n’ number of trials are found by multiplying ‘n’ with the probability calculated.
Then the value of ‘n’ increases in the next iteration and the process continues. The loop breaks when the value of probability after a certain number of iterations starts tending to zero because the expected number of people will also start tending to zero.
All the data is printed in the form of a table.
output
Number of trials(n) k(n-r) Negative Probability Distribution Expected Number of People 3 0 0.004096 4 4 1 0.010322 10 5 2 0.017341 17 6 3 0.024277 24 7 4 0.030589 30 8 5 0.035973 35 9 6 0.040290 40 10 7 0.043513 43 11 8 0.045688 45 12 9 0.046907 46 13 10 0.047282 47 14 11 0.046938 46 15 12 0.045999 45 16 13 0.044584 44 17 14 0.042801 42 18 15 0.040746 40 19 16 0.038505 38 20 17 0.036150 36 21 18 0.033740 33 22 19 0.031325 31 23 20 0.028944 28 24 21 0.026628 26 25 22 0.024401 24 26 23 0.022279 22 27 24 0.020274 20 28 25 0.018393 18 29 26 0.016638 16 30 27 0.015012 15 31 28 0.013510 13 32 29 0.012131 12 33 30 0.010870 10 34 31 0.009720 9 35 32 0.008675 8 36 33 0.007728 7 37 34 0.006874 6 38 35 0.006104 6 39 36 0.005412 5 40 37 0.004792 4 41 38 0.004237 4 42 39 0.003742 3 43 40 0.003300 3 44 41 0.002907 2 45 42 0.002558 2 46 43 0.002249 2 47 44 0.001975 1 48 45 0.001733 1 49 46 0.001519 1 50 47 0.001330 1 51 48 0.001164 1 52 49 0.001018 1
Also read: How to rearrange positive and negative numbers with constant extra space in an array using C++
Leave a Reply