negative _binomial_distribution in C++ with examples

In 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.  

=  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)
311
419
524

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

Your email address will not be published. Required fields are marked *