COMB operation can be used also for computing probabilities related to
a given multinomial distribution as shown by the following examples.
........................................................................
Example 1:
Assume that in a random experiment there are 3 alternatives with
probabilities PROB=1/2,1/4,1/4 (ratios of integers are permitted)
and we want to compute the probability that 12 observations are distributed
among these 3 alternatives so that frequencies are within limits given
by min.values MIN=3,4,1 and max.values MAX=5,5,5
The permitted combinations are computed by
COMB D,CUR+1 / D=DISTRIBUTIONS,12,3
Distributions of 12 elements into 3 cells: N[D]=6 P=0.170511245727539
3 4 5 1.321792602539068e-002 (sum of prob.s)
3 5 4 1.321792602539068e-002
4 4 4 3.304481506347660e-002
4 5 3 2.643585205078131e-002
5 4 3 5.287170410156262e-002
5 5 2 3.172302246093759e-002
f(n):=fact(n) Checking the first case:
f(12)/(f(3)*f(4)*f(5))*(1/2)^3*(1/4)^4*(1/4)^5=0.01321792602539
................................................................................
................................................................................
Example 2:
If there is no need to list various alternatives, it is much faster
to compute probabilities as follows:
MIN=0 MAX=10000 (Thus all possible combinations)
TIME COUNT START
COMB M,CUR+2 / M=MULTIN_PROB,10000,6
TIME COUNT END 250.410 (on 700 MHz Pentium)
Distributions of 10000 elements into 6 cells: P[M]=0.999999999606738
................................................................................
Similarly:
MIN=900 MAX=1100
TIME COUNT START
COMB M,CUR+2 / M=MULTIN_PROB,6000,6
TIME COUNT END 0.450
Distributions of 6000 elements into 6 cells: P[M]=0.997014290654646
................................................................................
Computation method on the next page!
Assume n trials with m equiprobable outcomes.
Let P(n,m,min,max) be the probability of getting all frequencies
within the interval [min,max].
Then P(n,m)=P(n,m,min,max) is obtained from the recurrence
max
P(n,m) = SUM C(n,i)*(1/m)^i(1-1/m)^(n-i)*P(n-i,m-1)
i=min
with initial conditions P(n,m) = 0, if m*min>n or m*max<n,
P(n,1) = 1.
If probabilities of m alternatives p1,p2,...,pm are not the same,
max
P(n,k) = SUM C(n,i)*qi^i(1-qi)^(n-i)*P(n-i,k-1)
i=min
where qi=pi/(p1+p2+...+pk).
Example of this more general case on the next page!
................................................................................
Example 3:
PROB=1/5,1/5,1/5,0.21,0.19
MIN=900 MAX=1100
TIME COUNT START
COMB M,CUR+2 / M=MULTIN_PROB,5000,5
TIME COUNT END 0.230
Distributions of 5000 elements into 5 cells: P[M]=0.928764087453283
................................................................................
MIN=900,900,900,900,900 MAX=1100,1100,1100,1100,1100
PROB=1/5,1/5,1/5,0.21,0.19
TIME COUNT START
COMB D,CUR+2 / D=DISTRIBUTIONS,5000,5 RESULTS=0
TIME COUNT END 789.195
Distributions of 5000 elements into 5 cells: P=0.928764087453838
N[D]=977654751
Thus the recursive algorithm is almost 25000 times faster in this case!
................................................................................
................................................................................
Example 4:
What is the probability that in 600 tosses of an unbiased dice all
frequencies of numbers 1,2,3,4,5,6 remain within the interval [90,110]?
MIN=90,90,90,90,90,90
MAX=110,110,110,110,110,110
PROB=1/6,1/6,1/6,1/6,1/6,1/6
COMB D,CUR+1 / D=DISTRIBUTIONS,600,6 RESULTS=0
Distributions of 600 elements into 6 cells: N[D]=2248575 P=0.215946634850144
........................................................................
When the distribution is discrete uniform, it is simpler and faster
to compute the probability (by using a MULTIN specification) by:
COMB P,CUR+1 / P=PARTITIONS,600,6 MIN=90 MAX=110 MULTIN=2 RESULTS=0
Restricted partitions of 600: N[P]=5444 P=0.215946634850137 NM=2248575
NM=N[D] (due to MULTIN=2) is also computed. See also Partitions!
........................................................................
The fastest solution is:
COMB M,CUR+1 / M=MULTIN_PROB,600,6 MIN=90 MAX=110
Distributions of 600 elements into 6 cells: P[M]=0.215946634850135
................................................................................
................................................................................
Example 5: Varying limits and probabilities
MIN=450,180,100,50,44
MAX=560,270,170,80,88
PROB=1/2,1/4,1/8,1/16,1/16
TIME COUNT START
COMB M,CUR+2 / M=MULTIN_PROB,1024,5
TIME COUNT END 0.440 (366 MHz)
Distributions of 1024 elements into 5 cells: P[M]=0.808004563373524
................................................................................
MIN=450,180,100,50,44
MAX=560,270,170,80,88
PROB=1/2,1/4,1/8,1/16,1/16
TIME COUNT START
COMB M,CUR+2 / M=DISTRIBUTIONS,1024,5 RESULTS=0
TIME COUNT END 11.810
Distributions of 1024 elements into 5 cells: N[M]=6784690 P=0.808004563373562
C = Other forms of COMB
Help System (web edition)