PROBABILITY AND RANDOM PROCESSES

By WILLIAM LEE

CONTENTS CHAPTER SETS, FIELDS, AND EVENTS, SET DE?NITIONS, SET OPERATIONS, SET ALGEBRAS, FIELDS, AND EVENTS, CHAPTER PROBABILITY SPACE AND AXIOMS, PROBABILITY SPACE, CONDITIONAL PROBABILITY, INDEPENDENCE, TOTAL PROBABILITY AND BAYES’ THEOREM, BASIC COMBINATORICS, BASIC COUNTING PRINCIPLES, PERMUTATIONS, COMBINATIONS, DISCRETE DISTRIBUTIONS, BERNOULLI TRIALS, BINOMIAL DISTRIBUTION, MULTINOMIAL DISTRIBUTION, GEOMETRIC DISTRIBUTION, NEGATIVE BINOMIAL DISTRIBUTION, HYPERGEOMETRIC DISTRIBUTION, POISSON DISTRIBUTION, LOGARITHMIC DISTRIBUTION, SUMMARY OF DISCRETE DISTRIBUTIONS, RANDOM VARIABLES, DE?NITION OF RANDOM VARIABLES, DETERMINATION OF DISTRIBUTION AND DENSITY FUNCTIONS, PROPERTIES OF DISTRIBUTION AND DENSITY FUNCTIONS, DISTRIBUTION FUNCTIONS FROM DENSITY FUNCTIONS, CONTINUOUS RANDOM VARIABLES AND BASIC DISTRIBUTIONS, INTRODUCTION, UNIFORM DISTRIBUTION, EXPONENTIAL DISTRIBUTION, NORMAL OR GAUSSIAN DISTRIBUTION, OTHER CONTINUOUS DISTRIBUTIONS, TRIANGULAR DISTRIBUTION, LAPLACE DISTRIBUTION, ERLANG DISTRIBUTION, GAMMA DISTRIBUTION, WEIBULL DISTRIBUTION, CHI-SQUARE DISTRIBUTION, CHI AND OTHER ALLIED DISTRIBUTIONS, STUDENT-T DENSITY, SNEDECOR F DISTRIBUTION, LOGNORMAL DISTRIBUTION, BETA DISTRIBUTION, CAUCHY DISTRIBUTION, PARETO DISTRIBUTION, GIBBS DISTRIBUTION, MIXED DISTRIBUTIONS, SUMMARY OF DISTRIBUTIONS OF CONTINUOUS RANDOM VARIABLES, CONDITIONAL DENSITIES AND DISTRIBUTIONS, CONDITIONAL DISTRIBUTION AND DENSITY FOR P(A)= 0, CONDITIONAL DISTRIBUTION AND DENSITY FOR P(A) ¼ 0, TOTAL PROBABILITY AND BAYES’ THEOREM FOR DENSITIES, JOINT DENSITIES AND DISTRIBUTIONS, JOINT DISCRETE DISTRIBUTION FUNCTIONS, JOINT CONTINUOUS DISTRIBUTION FUNCTIONS, BIVARIATE GAUSSIAN DISTRIBUTIONS, MOMENTS AND CONDITIONAL MOMENTS, EXPECTATIONS, VARIANCE, MEANS AND VARIANCES OF SOME DISTRIBUTIONS, HIGHER-ORDER MOMENTS, BIVARIATE GAUSSIAN, CHARACTERISTIC FUNCTIONS AND GENERATING FUNCTIONS, CHARACTERISTIC FUNCTIONS, EXAMPLES OF CHARACTERISTIC FUNCTIONS, GENERATING FUNCTIONS, EXAMPLES OF GENERATING FUNCTIONS, MOMENT GENERATING FUNCTIONS, CUMULANT GENERATING FUNCTIONS, TABLE OF MEANS AND VARIANCES, FUNCTIONS OF A SINGLE RANDOM VARIABLE, RANDOM VARIABLE G(X), DISTRIBUTION OF Y ¼ G(X ), DIRECT DETERMINATION OF DENSITY FY ( Y) FROM FX(X), INVERSE PROBLEM: FINDING G(X) GIVEN FX(X) AND FY ( Y), MOMENTS OF A FUNCTION OF A RANDOM VARIABLE, FUNCTIONS OF MULTIPLE RANDOM VARIABLES, FUNCTION OF TWO RANDOM VARIABLES, Z ¼ G(X,Y ), TWO FUNCTIONS OF TWO RANDOM VARIABLES, Z ¼ G(X,Y), W ¼ H(X,Y), DIRECT DETERMINATION OF JOINT DENSITY FZW(Z,W ) FROM FXY(X,Y ), SOLVING Z ¼ G(X,Y) USING AN AUXILIARY RANDOM VARIABLE, MULTIPLE FUNCTIONS OF RANDOM VARIABLES, INEQUALITIES, CONVERGENCES, AND LIMIT THEOREMS, DEGENERATE RANDOM VARIABLES, CHEBYSHEV AND ALLIED INEQUALITIES, MARKOV INEQUALITY, CHERNOFF BOUND, CAUCHY–SCHWARTZ INEQUALITY, JENSEN’S INEQUALITY, CONVERGENCE CONCEPTS, LIMIT THEOREMS, COMPUTER METHODS FOR GENERATING RANDOM VARIATES, UNIFORM-DISTRIBUTION RANDOM VARIATES, HISTOGRAMS, INVERSE TRANSFORMATION TECHNIQUES, CONVOLUTION TECHNIQUES, ACCEPTANCE–REJECTION TECHNIQUES, ELEMENTS OF MATRIX ALGEBRA, BASIC THEORY OF MATRICES, EIGENVALUES AND EIGENVECTORS OF MATRICES, VECTORS AND MATRIX DIFFERENTIATIONS, BLOCK MATRICES, RANDOM VECTORS AND MEAN-SQUARE ESTIMATION, DISTRIBUTIONS AND DENSITIES, MOMENTS OF RANDOM VECTORS, VECTOR GAUSSIAN RANDOM VARIABLES, DIAGONALIZATION OF COVARIANCE MATRICES, SIMULTANEOUS DIAGONALIZATION OF COVARIANCE MATRICES, LINEAR ESTIMATION OF VECTOR VARIABLES, ESTIMATION THEORY, CRITERIA OF ESTIMATORS, ESTIMATION OF RANDOM VARIABLES, ESTIMATION OF PARAMETERS (POINT ESTIMATION), INTERVAL ESTIMATION (CON?DENCE INTERVALS), HYPOTHESIS TESTING (BINARY), BAYESIAN ESTIMATION, RANDOM PROCESSES, BASIC DE?NITIONS, STATIONARY RANDOM PROCESSES, ERGODIC PROCESSES, ESTIMATION OF PARAMETERS OF RANDOM PROCESSES, POWER SPECTRAL DENSITY, CLASSI?CATION OF RANDOM PROCESSES, SPECI?CATIONS OF RANDOM PROCESSES, POISSON PROCESS, BINOMIAL PROCESS, INDEPENDENT INCREMENT PROCESS, RANDOM-WALK PROCESS, GAUSSIAN PROCESS, WIENER PROCESS (BROWNIAN MOTION), MARKOV PROCESS, MARKOV CHAIN, MARTINGALE PROCESS, PERIODIC RANDOM PROCESS, APERIODIC RANDOM PROCESS (KARHUNEN–LOEVE EXPANSION), RANDOM PROCESSES AND LINEAR SYSTEMS, REVIEW OF LINEAR SYSTEMS, RANDOM PROCESSES THROUGH LINEAR SYSTEMS, LINEAR FILTERS, BANDPASS STATIONARY RANDOM PROCESSES, WEINER AND KALMAN FILTERS, REVIEW OF ORTHOGONALITY PRINCIPLE, WIENER FILTERING, DISCRETE KALMAN FILTER, CONTINUOUS KALMAN FILTER, PROBABILISTIC METHODS IN TRANSMISSION TOMOGRAPHY, STOCHASTIC MODEL, STOCHASTIC ESTIMATION ALGORITHM, PRIOR DISTRIBUTION PFMG, COMPUTER SIMULATION, RESULTS AND CONCLUSIONS, DISCUSSION OF RESULTS, REFERENCES FOR CHAPTER 23, THE SET R OF ALL REAL NUMBERS IS WRITTEN AS R ¼ {X : X IS REAL}: UNCOUNTABLY INFINITE SET SET OPERATIONS THE INTERSECTION OF THE SETS A AND B IN EXAMPLE 1 2 1 IS THE SET C ¼ F2,3G EXAMPLES 1 2 1 AND 1 2 2 ARE SHOWN IN THE VENN DIAGRAM OF FIG 1 2 1 MUTUALLY EXCLUSIVE SETS TWO SETS A AND B ARE CALLED MUTUALLY EXCLUSIVE IF THEIR INTERSECTION IS EMPTY MUTUALLY EXCLUSIVE SETS ARE ALSO CALLED DISJOINT A > B ¼ NUMBERS IN BRACKETS REFER TO BIBLIOGRAPHIC ENTRIES IN THE REFERENCES SECTION AT THE END OF THE BOOK TABLE OF SET PROPERTIES PROPERTY EQUATION IDENTITY A < 1 ¼ A A > S ¼ A DOMINATION A > 1 ¼ A < S ¼ S IDEMPOTENT A > A ¼ A A < A ¼ A COMPLEMENTATION A ¼ ¼ A COMMUTATIVE A < B ¼ B < A A > B ¼ B > A ASSOCIATIVE A < (B < C) ¼ (A < B) < C A > (B > C) ¼ (A > B) > C DISTRIBUTIVE A > (B < C) ¼ (A > B) < (A > C) A < (B > C) ¼ (A < B) > (A < C) NONCOMMUTATIVE A 2 B = B 2 A DE MORGAN’S LAW A < B ¼ A > B A > B ¼ A < B N AI [ F LET US SEE THE CONSEQUENCES OF THESE CONDITIONS BEING SATIS?ED IF A1 [ F AND A1F, THEN A1 < A1 ¼ S [ F IF S [ F, THEN S ¼ 1 [ F IF A1 < A2 [ F, THEN BY CONDITION SET ALGEBRAS, FIELDS, AND EVENTS THE SET OF ALL REAL NUMBERS X AND Y SUCH THAT X IS BETWEEN 0 AND 1 AND Y IS BETWEEN 1 AND 2 IS GIVEN BY S ¼ FX, Y : 0 X 1, 1 Y 2G THE CONTINUOUS SAMPLE SPACE GIVEN IN EXAMPLES 2 1 4 AND 2 1 5 IS SHOWN IN FIG 2 1 1 FIELD F A ?ELD HAS ALREADY BEEN DE?NED IN SECTION 1 3 WE SHALL ASSUME THAT A PROPER BOREL S ?ELD CAN BE DE?NED FOR ALL DISCRETE AND CONTINUOUS SAMPLE SPACES PROBABILITY MEASURE P A PROBABILITY MEASURE IS DE?NED ON THE ?ELD F OF EVENTS OF THE SAMPLE SPACE S IT IS A MAPPING OF THE SAMPLE SPACE TO THE REAL LINE BETWEEN 0 AND 1 SUCH THAT IT SATIS?ES THE FOLLOWING THREE KOLMOGOROV AXIOMS FOR ALL EVENTS BELONGING TO THE ?ELD F: AXIOM 1: IF A BELONGS TO F; THEN P(A) 0: NONNEGATIVITY: (2:1:1) AXIOM 2: THE PROBABILITY OF THE SAMPLE SPACE EQUALS 1 P(S) ¼ 1: NORMALIZATION: (2:1:2) AXIOM 3A: IF A AND B ARE DISJOINT SETS BELONGING TO F, THAT IS, A > B ¼ 1, THEN P{A < B} ¼ P(A) Þ P(B): BOOLEN ADDITIVITY: (2:1:3) AXIOM 3B: IF FA1, A2, G IS A SEQUENCE OF SETS BELONGING TO THE ?ELD 1 SUCH THAT AI > AJ ¼ 1 FOR ALL I = J, THEN P A1 < A2 < < AI < F G ¼ X PROBABILITY SPACE A FAIR COIN IS TOSSED 3 TIMES SINCE EACH TOSS IS A FUNCTIONALLY INDEPENDENT TRIAL AND FORMS A CARTESIAN PRODUCT, THE CARDINALITY OF THE THREE TOSSES IS 2 2 2 ¼ AND THE SAMPLE SPACE CONSISTS OF THE FOLLOWING 8 EVENTS: S ¼ {½HHH, ½HHT, ½HTT, ½HTH, ½THH, ½TTH, ½THT, ½TTT} IN THIS SAMPLE SPACE P{2 HEADS} ¼ P{½HHH, ½HHT, ½HTH, ½THH} ¼ P{BOTH HEADS AND TAILS} ¼ {½HHT, ½HTT, ½HTH, ½THH, ½TTH, ½THT} ¼ A TELEPHONE CALL OCCURS AT RANDOM BETWEEN 9:00 A M AND 11:00 A M HENCE THE PROBABILITY THAT THE TELEPHONE CALL OCCURS IN THE INTERVAL 0 , T T0 IS GIVEN BY T0=120 THUS THE PROBABILITY THAT THE CALL OCCURS BETWEEN 9:30 A M AND 10:45 A M IS GIVEN BY: P{30 , T 105} ¼ 105 120 ¼ CONDITIONAL PROBABILITY THE CONDITIONAL PROBABILITY OF AN EVENT B CONDITIONED ON THE OCCURRENCE OF ANOTHER EVENT B IS DE?NED BY P{B J A} ¼ P{B > A} P{A} P{B > A} ¼ P{B J A}P{A} >= >; IF P{A} = IN THE TOSSING OF A FAIR DIE, WE SHALL CALCULATE THE PROBABILITY THAT 3 HAS OCCURRED CONDITIONED ON THE TOSS BEING ODD WE SHALL DE?NE THE FOLLOWING EVENTS: A ¼ {ODD NUMBER}: B ¼ P{A} ¼ 2 AND P{B} ¼ 6 AND THE EVENT A > B ¼ {3} AND HENCE P{3 J ODD} ¼ P{3} P{ODD} ¼ NOTE THAT P{2 J ODD} ¼ 0 SINCE 2 IS AN IMPOSSIBLE EVENT GIVEN THAT AN ODD NUMBER HAS OCCURRED ALSO NOTE THAT P{3 J 3} ¼ 1 THE CONDITIONAL PROBABILITY OF 3 OCCURRING, GIVEN THAT 3 HAS OCCURRED IS OBVIOUSLY EQUAL TO 1 WE CAN ALSO ?ND THE SOLUTION USING THE CONCEPT OF REDUCED SAMPLE SPACE SINCE WE ARE GIVEN THAT AN ODD NUMBER HAS OCCURRED, WE CAN REDUCE THE SAMPLE SPACE FROM S ¼ {1,2,3,4,5,6} TO S1 ¼ {1,3,5} AS SHOWN IN FIG 2 2 1 THE PROBABILITY OF 3 IN THIS REDUCED SAMPLE SPACE IS CONSIDER A FAMILY OF EXACTLY TWO CHILDREN WE WILL ?ND THE PROBABILITIES (1) THAT BOTH ARE GIRLS, (2) BOTH ARE GIRLS GIVEN THAT ONE OF THEM IS A GIRL, (3) BOTH ARE GIRLS GIVEN THAT THE ELDER CHILD IS A GIRL, AND (4) BOTH ARE GIRLS GIVEN THAT BOTH ARE GIRLS THE SAMPLE SPACE S HAS 4 POINTS {GG, GB, BG, BB}, WHERE G IS GIRL AND B IS BOY THE EVENT B ¼ FBOTH CHILDREN ARE GIRLSG THE CONDITIONING EVENT A WILL DEPEND ON THE FOLLOWING FOUR CASES: 1 THE EVENT A ¼ S HENCE P{B} ¼ 4 2 THE EVENT A ¼ FONE CHILD IS A GIRLG THE REDUCED SAMPLE SPACE IS S1 ¼ FGG, GB, BGG AND THE CONDITIONAL PROBABILITY P{B J A} ¼ 3 3 THE EVENT A ¼ FELDER CHILD IS A GIRLG IN THIS CASE, THE REDUCED SAMPLE SPACE IS S2 ¼ {GG, GB} AND P{B J A} ¼ CONDITIONAL PROBABILITY THE GAME OF CRAPS AS PLAYED IN LAS VEGAS HAS THE FOLLOWING RULES A PLAYER ROLLS TWO DICE HE WINS ON THE ?RST ROLL IF HE THROWS A 7 OR A 11 HE LOSES IF THE ?RST THROW IS A 2, 3, OR 12 IF THE ?RST THROW IS A 4, 5, 6, 8, 9, OR 10, IT IS CALLED A POINT AND THE GAME CONTINUES HE GOES ON ROLLING UNTIL HE THROWS THE POINT FOR A WIN OR A 7 FOR A LOSS WE HAVE TO ?ND THE PROBABILITY OF THE PLAYER WINNING WE WILL SOLVE THIS PROBLEM BOTH FROM THE DE?NITION OF CONDITIONAL PROBABILITY AND THE REDUCED SAMPLE SPACE FIGURE 2 2 2 SHOWS THE NUMBER OF WAYS THE SUMS OF THE PIPS ON THE TWO DICE CAN EQUAL 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, AND THEIR PROBABILITIES SOLUTION USING DE?NITION OF CONDITIONAL PROBABILITY THE PROBABILITY OF WINNING IN THE ?RST THROW IS P{7} Þ P{11} ¼ 36 Þ 36 ¼ THE PROBABILITY OF LOSING IN THE ?RST THROW IS P{2} Þ P{3} Þ P{12} ¼ TO CALCULATE THE PROBABILITY OF WINNING IN THE SECOND THROW, WE SHALL ASSUME THAT I IS THE POINT WITH PROBABILITY P THE PROBABILITY OF NOT WINNING IN ANY GIVEN THROW AFTER THE ?RST IS GIVEN BY R ¼ P{NOT I AND NOT 7} ¼ 1 P 6 WE COMPUTE THE CON- DITIONAL PROBABILITY P{WIN J I IN FIRST THROW} ¼ P Þ RP Þ R2P Þ ¼ P 1 R ¼ P P Þ P Þ PROBABILITY SPACE AND AXIOMS THUS, FOR I ¼ 4,5,6, WE OBTAIN P{WIN AFTER POINT I ¼ 4} ¼ P{WIN AFTER POINT I ¼ 5} ¼ P{WIN AFTER POINT I ¼ 6} ¼ WITH SIMILAR PROBABILITIES FOR 8,9,10 THUS THE PROBABILITY OF WINNING IN CRAPS IS P{WIN} ¼ P{WIN IN ROLL 1} Þ P{WIN IN ROLL 2,3, } ¼ 36 Þ 2 45 Þ SOLUTION USING REDUCED SAMPLE SPACE WE CAN NOW USE THE REDUCED SAMPLE SPACE TO ARRIVE AT THE SAME RESULT IN A SIMPLER MANNER AFTER THE POINT I HAS BEEN ROLLED IN THE ?RST THROW, THE REDUCED SAMPLE SPACE CONSISTS OF (I 2 1 Þ 6) POINTS FOR I ¼ 4,5,6 AND (13 2 I Þ 6) POINTS FOR I ¼ 8,9,10 IN WHICH THE GAME WILL TERMINATE WE CAN SEE FROM THE ?GURE THAT THERE ARE 6 WAYS OF ROLLING 7 FOR A LOSS, (I 2 1, I ¼ 4,5,6) WAYS OF ROLLING THE POINT FOR A WIN, AND (13 2 I, I ¼ 8,9,10) WAYS OF ROLLING THE POINT FOR A WIN THUS P{WIN IN ROLL 2,3, J I IN ROLL 1} ¼ P{W J I} ¼ I >< >: THUS, P{W J 4} ¼ 9 , P{W J 5} ¼ 10 , P{W J 6} ¼ 11 , P{W J 8} ¼ 11 , P{W J 9} ¼ 10 , P{W J 10} ¼ 9 HENCE PROBABILITY OF A WIN AFTER THE ?RST ROLL IS P{W J I} P{I}: HENCE P{WIN AFTER FIRST ROLL} ¼ 2 P{WIN} ¼ 2 495 Þ THE REQUIRED CONDITIONAL PROBABILITY EQUALS THE NUMBER OF PERSONS WHO DIE BET- WEEN THE AGES 70 AND 80 DIVIDED BY THE NUMBER OF PERSONS WHO HAVE LIVED UPTO THE AGE 70: P{B J A} ¼ P{70 , T 80 AND T 70} P{T 70} ¼ P{70 , T 80} P{T 70} ¼ Ð 70 3 109T2(100 T2)DT Ð THE PROBABILITY OF AN ACE ON THE THROW OF A DIE IS 6 THE PROBABILITY OF A HEAD ON THE THROW OF A COIN IS 2 SINCE THE THROW OF A DIE IS NOT DEPENDENT ON THE THROW OF A COIN, WE HAVE FUNCTIONAL INDEPENDENCE AND THE COMBINED SAMPLE SPACE IS THE CARTESIAN PRODUCT WITH 12 ELEMENTS AS SHOWN IN TABLE 2 3 1 PROBABILITY SPACE AND AXIOMS WE ASSUME AS USUAL THAT ALL THE 12 ELEMENTS ARE EQUIPROBABLE EVENTS AND THE PROBABILITY OF ACE AND HEAD IS 12 SINCE THERE IS ONLY ONE OCCURRENCE OF F1, HG AMONG THE 12 POINTS AS SEEN IN THE ?RST ROW AND ?RST COLUMN IN TABLE 2 3 1 USING EQ (2 3 1), WE HAVE P{1, H} ¼ P{1} P{H} ¼ 2 ¼ TWO DICE, ONE RED AND THE OTHER BLUE, ARE TOSSED THESE TOSSES ARE FUNC- TIONALLY INDEPENDENT, AND WE HAVE THE CARTESIAN PRODUCT OF 6 6 ¼ 36 ELEMENTARY EVENTS IN THE COMBINED SAMPLE SPACE, WHERE EACH EVENT IS EQUIPROBABLE WE SEEK THE PROBABILITY THAT AN EVENT B DE?NED BY THE SUM OF THE NUMBERS SHOWING ON THE DICE EQUALS 9 THERE ARE FOUR POINTS {(6,3), (5,4), (4,5), (3,6)}, AND HENCE P{B} ¼ 9 WE NOW CONDITION THE EVENT B WITH AN EVENT A DE?NED AS THE RED DIE SHOWS ODD NUMBERS THE PROBABILITY OF THE EVENT A IS P{A} ¼ 2 WE WANT TO DETERMINE WHETHER THE EVENTS A AND B ARE STAT- ISTICALLY INDEPENDENT THESE EVENTS ARE SHOWN IN FIG 2 3 1, WHERE THE ?RST NUMBER IS FOR THE RED DIE AND THE SECOND NUMBER IS FOR THE BLUE DIE FROM FIG 2 3 1 P{A > B} ¼ P{(3,6), (5,4)} ¼ 18 AND ¼ P{A} P{B} ¼ 9 ¼ 18 SHOWING STATISTICAL INDEPENDENCE WE COMPUTE P{B J A} FROM THE POINT OF VIEW OF REDUCED SAMPLE SPACE THE CONDITIONING EVENT REDUCES THE SAMPLE SPACE FROM 36 POINTS TO EQUIPROBABLE POINTS AND THE EVENT {B J A} ¼ {(3,6), (5,4)} HENCE P{B J A} ¼ 18 ¼ 9 ¼ P{B}, OR, THE CONDITIONING EVENT HAS NO IN?UENCE ON B HERE, EVEN THOUGH THE EVENTS A AND B ARE FUNCTIONALLY DEPENDENT, THEY ARE STATISTICALLY INDEPENDENT HOWEVER, IF ANOTHER SET C IS DE?NED BY THE SUM BEING EQUAL TO 8 AS SHOWN IN FIG 2 3 2, THEN P{C} ¼ 36 HERE THE EVENTS C AND A ARE NOT STATISTICALLY INDEPENDENT BECAUSE P{C} P{A} ¼ 72 = P{C > A} ¼ P{(3,5), (5,3)} ¼ INDEPENDENCE TOTAL PROBABILITY AND BAYES’ THEOREM PROBABILITY SPACE AND AXIOMS PROBABILITY OF WINNING THE CAR IS IMPROVED IF SHE SWITCHES OR IT IS IMMATERIAL WHETHER SHE SWITCHES OR NOT THE ANSWER IS COUNTERINTUITIVE IN THE SENSE THAT ONE MAY BE MISLED INTO THINKING THAT IT IS IMMATERIAL WHETHER ONE SWITCHES OR NOT WE WILL ANALYZE THIS PROBLEM IN TWO DIFFERENT WAYS MATHEMATICAL ANALYSIS LET US ANALYZE THIS PROBLEM FROM THE POINT OF VIEW OF BAYES’ THEOREM WE SHALL ?RST ASSUME THAT THE HOST HAS PRIOR KNOWLEDGE OF THE DOOR BEHIND WHICH THE CAR IS LOCATED LET US ALSO ASSUME THAT THE HOST OPENS DOOR B GIVEN THAT THE CONTESTANT’S CHOICE IS DOOR A THE A PRIORI PROBABILITIES OF A CAR BEHIND THE DOORS A, B, AND C ARE P{A} ¼ 3 ; P{B} ¼ 3 ; P{C} ¼ WE CAN MAKE THE FOLLOWING OBSERVATIONS IF THE CONTESTANT’S CHOICE IS DOOR A AND THE CAR IS BEHIND DOOR A, THEN THE HOST WILL OPEN THE DOOR B WITH PROBABILITY OF 2 (SINCE SHE HAS A CHOICE BETWEEN B AND C) ON THE OTHER HAND, IF THE CAR IS BEHIND DOOR B, THEN THERE IS ZERO PROBABILITY THAT SHE WILL OPEN DOOR B BECAUSE OF HER PRIOR KNOWL- EDGE IF THE CAR IS BEHIND DOOR C, THEN SHE WILL OPEN DOOR B WITH PROBABILITY 1 THUS WE CAN WRITE THE FOLLOWING CONDITIONAL PROBABILITIES FOR THE HOST OPENING DOOR B: P{B J A} ¼ 2 ; P{B J B} ¼ 0; P{B J C} ¼ WE CAN NOW CALCULATE THE TOTAL PROBABILITY P(B) OF THE HOST OPENING DOOR B P{B} ¼ P{B J A}P{A} Þ P{B J B}P{B} Þ P{B J C}P{C} ¼ 3 Þ 0 3 Þ 1 3 ¼ USING BAYES’ THEOREM [EQ (2 4 4)] WE CAN NOW ?ND THE A POSTERIORI PROBABILITIES OF THE CAR BEHIND THE DOORS A OR C (B HAS ALREADY BEEN OPENED BY THE HOST) CONDITIONED ON B: P{A J B} ¼ P{BA} P{B} ¼ P{B J A}P{A} P{B} ¼ P{C J B} ¼ P{BC} P{B} ¼ P{B J C}P{C} P{B} ¼ 1 FIRST CHOICE HOST OPENS SECOND CHOICE PROBABILITY A B A P{B} ¼ A C A P{C} ¼ B C B P{C} ¼ 1 C B B P{B} ¼ 1 HEURISTIC ANALYSIS IN THIS CASE WE SHALL ENUMERATE ALL THE POSSIBILITIES AND DETERMINE WHICH POSSIBILITY GIVES A BETTER CHANCE ASSUME THAT THE CAR IS BEHIND DOOR A THE PROBABILITIES OF A,B,C ARE ONCE AGAIN P{A} ¼ CONDITIONED ON THE CONTESTANT CHOOSING DOOR A, THE HOST HAS TWO EQUIPROBABLE CHOICES OF OPENING EITHER DOOR B OR DOOR C HOWEVER, CONDITIONED ON THE CONTESTANT CHOOS- ING B OR C, THE HOST HAS ONLY ONE CHOICE OF EITHER OPENING C OR B THUS P{B J A} ¼ 2 ; P{C J A} ¼ 2 ; P{C J B} ¼ 1; P{B J C} ¼ FROM THESE CONDITIONAL PROBABILITIES WE CAN EVALUATE THE UNCONDITIONAL PROBABILITIES AS SHOWN IN TABLE 2 4 1 WE CAN NOW ENUMERATE THE VARIOUS WIN OR LOSS POSSIBILITIES FOR NOT SWITCHING AND FOR SWITCHING IN TABLES 2 4 2 AND 2 4 3 FROM THE TABLE 2 4 2 WE CAN SEE THAT THE PROBABILITY OF WINNING THE CAR BY NOT SWITCHING IS 6 Þ 6 ¼ 3 FROM TABLE 2 4 3 WE CAN SEE THAT THE PROBABILITY OF WINNING THE CAR BY SWITCHING IS 3 Þ FOR SWITCHING FIRST CHOICE HOST OPENS SECOND CHOICE WIN OR LOSS PROBABILITY A B C LOSS P{B} ¼ A C B LOSS P{C} ¼ B C A WIN P{C} ¼ 1 C B A WIN P{B} ¼ 1 FOR NOT SWITCHING FIRST CHOICE HOST OPENS SECOND CHOICE WIN OR LOSS PROBABILITY A B A WIN P{B} ¼ A C A WIN P{C} ¼ B C B LOSS P{C} ¼ 1 C B B LOSS P{B} ¼ 1 PROBABILITY SPACE AND AXIOMS CHAPTER AN ENGINEERING STUDENT UNDERTAKING A CAPSTONE PROJECT T HAS A CHOICE OF 4 PROFESSORS A,B,C,D WHO CAN GIVE HIM A LIST OF PROJECTS FROM WHICH HE CAN CHOOSE ONE A HAS 5 PROJECTS, B HAS 7 PROJECTS, C HAS 6 PROJECTS, AND D HAS 2 PROJECTS SINCE THE STUDENT CAN NOT TAKE ANY OTHER PROJECT ONCE HE HAS CHOSEN A PROJECT, THE NUMBER OF CHOICES HE HAS IS N(T) ¼ N(A) Þ N(B) Þ N(C) Þ N(D) ¼ 5 Þ 7 Þ 6 Þ 2 ¼ THE MULTIPLICATION RULE A TASK A CONSISTS OF M SEQUENTIAL SUBTASKS A1, A2, , AM THAT CAN BE PERFORMED ONLY AFTER THE PREVIOUS ONE IS COMPLETED THE NUMBERS OF WAYS N(A1), N(A2), , N(AM) OF PERFORMING THE SUBTASKS ARE FUNCTIONALLY INDEPENDENT; THAT IS, N(A2) WAYS ARE NEEDED FOR THE SECOND STEP REGARDLESS OF N(A1) OF THE ?RST STEP THE NUMBER OF WAYS N(A) OF PERFORMING THE TASK A IS N(A) ¼ N(A1) N(A2) N(AM) (3:1:2) THE NUMBER OF DISTINCT ORDERED WAYS WE CAN DRAW 2 BALLS FROM AN URN CONTAINING 4 BALLS NUMBERED FROM 1 TO 4 IS OBTAINED AS FOLLOWS THE CELLS CORRESPOND TO N ¼ 4, THE TOTAL NUMBER OF BALLS THE BALLS CORRESPOND TO R ¼ 2 THE NUMBER OF WAYS BASIC COMBINATORICS N DIFFERENT WAYS SINCE ONE OF THE CELLS IS OCCUPIED, THE SECOND BALL CAN BE PLACED ONLY IN (N – 1) WAYS THE RTH BALL CAN BE PLACED IN (N – R Þ 1) WAYS SINCE PLACEMENTS OF THE BALLS ARE AGAIN FUNCTIONALLY INDEPENDENT, WE HAVE NUMBER OF DISTINCT R-TUPLES ¼ N(N 1) (N R Þ 1) (3:2:2) THESE WILL BE CALLED R-PERMUTATIONS AND WILL BE DE?NED BY (N)R OR NPR USING THE FACTORIAL NOTATION, WE CAN WRITE (N)R ¼ N! (N R)! (3:2:3) WE CANNOT PLACE 5 BALLS INTO 2 CELLS WITHOUT REPLACEMENT BECAUSE AT LEAST SOME CELLS WILL HAVE MORE THAN 1 BALL, VIOLATING THE NONREPLACEMENT CONDITION HENCE WE DE?NE (N)R ¼ PERMUTATIONS # PROBABILITY # PROBABILITY # PROBABILITY BASIC COMBINATORICS SAMPLING WITHOUT REPLACEMENT AND WITHOUT ORDERING WE NOW DISCUSS THE CASE WHERE WE WANT TO OBTAIN A SAMPLE OF R BALLS FROM N BALLS WITHOUT REPLACEMENT AND WITHOUT ORDERING WE HAVE ALREADY SEEN THAT THE NUMBER OF WAYS TO GET R BALLS FROM N BALLS WITH ORDERING IS (N)R IF WE DISREGARD ORDERING, THEN THE NUMBER OF WAYS IS CALLED THE R-COMBINATION FROM THE N BALLS WE CAN DE?NE THIS QUANTITY AS {R-COMBINATION FROM N BALLS} ¼ N R (3:3:1) BY ORDERING THE ELEMENTS IN EACH R-COMBINATION, WE CAN OBTAIN FROM N R THE R- PERMUTATIONS (N)R THIS CAN BE DONE IN R! WAYS HENCE WE CAN DETERMINE N R FROM EITHER OF THE FOLLOWING FORMULAS: N R R! ¼ (N)R N R ¼ (N)R R! ¼ N! R!(N R)! (3:3:2) THE QUANTITY N R IS ALSO CALLED THE BINOMIAL COEF?CIENT SINCE IT OCCURS AS THE COEF?CIENT OF THE BINOMIAL EXPANSION, GIVEN BY (A Þ B)N ¼ N AN Þ N AN1B Þ Þ N R ANRBR Þ Þ N N BN PROPERTIES OF BINOMIAL COEF?CIENTS 1 N R ¼ N N R (3:3:3) EXPANDING THE RIGHTHAND SIDE OF EQ (3 3 3), WE OBTAIN N N R ¼ N! (N R)!½N (N R)! ¼ N! (N R)!R! ¼ N R 2 PASCAL’S IDENTITY: N Þ R ¼ N R Þ N R (3:3:4) EXPANDING THE RIGHTHAND SIDE OF EQ (3 3 4), WE OBTAIN N R Þ N R ¼ N! (R 1)!(N R Þ 1)! Þ N! R!(N R)! ¼ N! R!(N R)! R N R Þ 1 Þ ¼ N! R!(N R)! N Þ N R Þ ¼ (N Þ 1)! R!(N R Þ 1)! ¼ N Þ COMBINATIONS N R ¼ 2N (3:3:5) SUBSTITUTING IN THE BINOMIAL EXPANSION (1 Þ X)N ¼ 1 Þ N X Þ N 1 A COMMITTEE OF 3 WOMEN AND 4 MEN MUST BE FORMED FROM A GROUP OF 6 WOMEN AND 8 MEN THE NUMBER OF WAYS 3 WOMEN CAN BE CHOSEN FROM 6 WOMEN IS FROM EQ (3 2 2) AND THE NUMBER OF WAYS 4 MEN CAN BE CHOSEN FROM 8 MEN IS SINCE THESE CHOICES ARE FUNCTIONALLY INDEPENDENT, THE TOTAL NUMBER OF WAYS THE COMMITTEE CAN BE FORMED IS ¼ 1400 2 WE MODIFY THE PROBLEM ABOVE BY HAVING 2 PARTICULAR MEN BE ALWAYS ON THE COMMITTEE IN THIS CASE WE HAVE A CHOICE OF ONLY 2 MEN FROM THE 6 MEN AFTER TAKING OUT THE 2 REQUIRED MEN THUS, THERE ARE ¼ 300 WAYS 3 WE AGAIN MODIFY THE PROBLEM BY REQUIRING THAT TWO PARTICULAR WOMEN SHOULD NOT BE ON THE COMMITTEE IN THIS CASE, WE CALCULATE THE NUMBER OF WAYS THAT THE TWO WOMEN WILL BE TOGETHER AND SUBTRACT IT FROM THE TOTAL NUMBER OF WAYS THERE ARE ¼ 350 WAYS THAT THE TWO WOMEN WILL BE TOGETHER, AND HENCE THERE ARE ¼ 1400 350 ¼ 1050 WAYS IN WHICH TWO GIVEN WOMEN WILL NOT BE TOGETHER EXAMPLE 3 3 3 (CATALAN NUMBERS) THERE ARE N OBJECTS TO BE PLACED IN COMPUTER STACKS IN THE FOLLOWING WAY THESE OBJECTS ARE ?RST STORED AND DELETED LATER WITH THE RESULT THAT WHEN ALL THE N OBJECTS ARE DELETED, THE STACK IS EMPTY HENCE, THE OPERATION STORE (S) HAS TO PRECEDE THE OPERATION DELETE (D), AND AT ANY POINT ALONG THE STACK THE NUMBER OF STORES SHOULD ALWAYS BE MORE THAN OR EQUAL TO THE NUMBER OF DELETES FINALLY, THE STACK SHOULD BEGIN WITH STORE AND END WITH DELETE WE NEED TO ?ND THE NUMBER C(N) OF OPERATIONS REQUIRED FOR N OBJECTS FOR EXAMPLE, IF THERE ARE N ¼ OBJECTS, THE NUMBER OF WAYS OF ORDERING THE STORE AND DELETE OPERATIONS ARE 2 3 ¼ 6 GIVEN BY SSSDDD, SDSDSD, SSDDSD, SDSSDD, SSDSDD, SDSDSSD THUS, THE OPERATION STARTS WITH AN S AND ENDS IN A D, AND AT NO POINT ALONG THE CHAIN CAN THE NUMBER OF D OPERATIONS EXCEED THE S OPERATIONS WE WILL SHOW THAT THE NUMBER C(N) IS GIVEN BY C(N) ¼ 2N N , WHICH IS THE DESIRED RESULT THE CATALAN NUMBERS ARE TABULATED IN TABLE 3 3 2 FOR N ¼ 1 TO 20 SAMPLING WITH REPLACEMENT AND WITHOUT ORDERING WE SHALL NOW CONSIDER FORMING R-COMBINATIONS WITH REPLACEMENT AND WITHOUT ORDER- ING IN THIS CASE WE PICK R BALLS WITH REPLACEMENT FROM BALLS IN N DISTINCT CATEGORIES SUCH AS RED, BLUE, GREEN, AND BROWN WE DO NOT DISTINGUISH AMONG BALLS OF THE SAME COLOR, AND THE DISTINCTION IS AMONG DIFFERENT COLORS FOR EXAMPLE, IF WE ARE PICKING 6 BALLS FROM THE COLOR CATEGORIES, THEN IT CAN BE ARRANGED AS SHOWN IN FIGURE 3 3 3 THERE ARE NOW 2 RED BALLS, 1 BLUE BALL, NO GREEN BALLS, AND 3 BROWN BALLS THE BAR SYMBOL | SEPARATES THE FOUR CATEGORIES THE ARRANGEMENT CANNOT START WITH A BAR OR END WITH A BAR; HENCE WE HAVE 4 2 1 ¼ 3 BARS WE NOW HAVE TO CHOOSE 6 BALLS FROM 6 BALLS AND 3 BARS WITHOUT REPLACEMENT AND WITHOUT ORDERING THERE ARE THEN ¼ 9 8 3 2 1 ¼ # STACKS # STACKS # STACKS AN URN CONTAINS RED, BLUE, GREEN, YELLOW, WHITE, AND BLACK BALLS IN HOW MANY WAYS CAN WE CHOOSE 1 10 BALLS? THIS IS A DIRECT APPLICATION OF EQ (3 3 7) WITH N ¼ 6, R ¼ 10 AND THE NUMBER OF WAYS IS 6 1 Þ 2 20 BALLS WITH LEAST 2 COLORS EACH? IF WE DRAW 2 BALLS OF EACH COLOR, THEN WE HAVE DRAWN 12 BALLS, LEAVING US TO DRAW 20–12 ¼ 8 BALLS TO BE DRAWN WITHOUT RESTRICTION HENCE, APPLYING EQ (3 2 7) WITH N ¼ 6 AND R ¼ 8, WE OBTAIN THE NUMBER OF WAYS AS 6 1 Þ 3 20 BALLS WITH NO MORE THAN 3 BLUE BALLS? WE ?RST CALCULATE THE NUMBER OF UNREST- RICTED WAYS OF DRAWING 20 BALLS AS 6 1 Þ WE NEXT DRAW AT LEAST 4 BLUE BALLS OUT OF 20 BALLS HAVING DRAWN THE 4 BLUE BALLS, THE NUMBER OF WAYS TO DRAW THE REMAINING 16 BALLS IS 6 1 Þ THUS THE NUMBER OF WAYS OF DRAWING 20 BALLS WITH NO MORE THAN 3 BLUE BALLS IS 53,130 2 20,349 ¼ 32,781 4 20 BALLS WITH AT LEAST 4 RED BALLS, AT LEAST 2 GREEN BALLS, AT LEAST 6 WHITE BALLS, AND NO MORE THAN 3 BROWN BALLS? WE ?RST DRAW THE LOWER BOUNDED BALLS, NAMELY, 4 Þ 2 Þ 6 ¼ 12, BEFORE WE GO TO THE UPPER-BOUNDED BROWN BALLS WE THEN DRAW THE REMAINING 8 BALLS IN AN UNRESTRICTED MANNER, AND THE NUMBER OF WAYS IS 6 1 Þ WE HAVE TO SUBTRACT FROM THIS NUMBER THE NUMBER OF WAYS 4 BROWN BALLS CAN BE PICKED FROM THE 6 COLORS THIS NUMBER IS 6 1 Þ WE TACKLE A DIFFERENT KIND OF A PROBLEM HOW MANY SOLUTIONS ARE THERE TO THE EQUATION X1 Þ X2 Þ X3 Þ X4 Þ X5 Þ X6 ¼ 1 XK 2 FOR ALL K? WE NEED XK 3 FOR ALL K THIS TAKES UP 6 3 ¼ 18 OF THE REQUIRED TOTAL OF 24, LEAVING US TO SOLVE THE EQUATION X1 Þ X2 Þ X3 Þ X4 Þ X5 Þ X6 ¼ IN AN UNRESTRICTED MANNER HERE WE IDENTIFY, IN EQ (3 2 7), N ¼ 6 CORRESPONDING TO THE NUMBER OF XK VALUES AND R ¼ 6 CORRESPONDING TO THE RIGHTHAND SIDE OF THE EQUATION HENCE THE NUMBER OF SOLUTIONS IS 6 1 Þ 2 X1 2, X2 1, X3 3, X4 4, X5 2, AND X6 2? USING X1 3, X3 4, X5 3, THE NUMBER OF RESTRICTIONS ADD UPTO 3 Þ 1 Þ 4 Þ 4 Þ 3 Þ 2 ¼ 17 THIS LEAVES 24 2 17 ¼ 7 UNRESTRICTED CHOICES HENCE THE NUMBER OF SOLUTIONS IS 6 1 Þ 3 X2 , 5, X3 10? THE NUMBER OF BALLS THAT CAN BE DRAWN WITH THE RESTRICTION X3 11 CORRESPONDING TO N ¼ 6 AND R ¼ (24 2 11) ¼ 13 IS GIVEN BY 6 1 Þ THE NUMBER OF DRAWS THAT VIOLATE THE ADDITIONAL RESTRICTION X2 , 5 IS OBTAINED BY ?RST ?NDING THE NUMBER OF DRAWS WITH THE ADDITIONAL RESTRICTION X2 6 THE NUMBER OF WAYS CORRESPONDING TO N ¼ 6 AND R ¼ (24 2 11 2 6) ¼ 7 IS GIVEN BY 6 1 Þ HERE IS AN INTERESTING EXAMPLE TO ILLUSTRATE THE VERSATILITY OF THE FORMULA IN EQ (3 2 7) FOUR DICE, EACH WITH ONLY 4 FACES MARKED 1,2,3,4, ARE TOSSED WE HAVE TO CALCULATE THE NUMBER OF WAYS IN WHICH THE TOSSES WILL RESULT IN EXACTLY 1 QUADRUPLE DIGIT BASIC COMBINATORICS WE CAN SEE FROM TABLE 3 3 3 THAT THERE ARE 4 SINGLE DIGITS, 18 DOUBLE DIGITS, 12 TRIPLE DIGITS, AND 1 QUADRUPLE DIGIT TOTALING 35 ARRANGEMENTS WITHOUT REGARD TO ORDER AND WITH REPLACEMENT THE PROBLEM CAN BE STATED AS FOLLOWS FOUR DICE EACH WITH 4 FACES ARE TOSSED WITHOUT REGARD TO ORDER AND WITH REPLACEMENT FIND THE NUMBER OF WAYS IN WHICH 1 THIS CAN BE ACHIEVED WITH N ¼ 4 AND R ¼ 4 IN EQ (3 2 7), THE NUMBER OF WAYS IS 4 1 Þ WHICH AGREES WITH THE TOTAL NUMBER IN THE TABLE 2 EXACTLY ONE DIGIT IS PRESENT WITH N ¼ 4 AND R ¼ 1, THE NUMBER OF WAYS IS 4 1 Þ WHICH AGREES WITH THE TABLE 3 EXACTLY 2 DIGITS ARE PRESENT THE NUMBER OF WAYS 2 DIGITS CAN BE DRAWN FROM DIGITS IS ¼ 3 THE TOTAL NUMBER USING ALL THE COMBINATIONS ARE ¼ 6 3 ¼ 18 WAYS THIS AGREES WITH THE TABLE 4 EXACTLY 3 DIGITS ARE PRESENT THE NUMBER OF WAYS 3 DIGITS CAN BE DRAWN FROM ¼ 4 WAYS THE NUMBER OF WAYS 3 DIGITS CAN BE ARRANGED IN 4 SLOTS SUCH THAT ALL THE THREE DIGITS ARE PRESENT IS AGAIN GIVEN BY THE RESTRICTION FORMULA EQ (3 2 7) 31Þ(43) ¼ 3 HENCE THE TOTAL NUMBER OF WAYS IS WAYS, AGREEING WITH THE TABLE 5 EXACTLY 4 DIGITS ARE PRESENT THE NUMBER OF WAYS 4 DIGITS WILL BE PRESENT IS OBTAINED FROM THE ARGUMENT IN ITEM 3 ABOVE, GIVING 41Þ(4Þ4) GENERALIZATION THE RESULT IN EXAMPLE 3 3 6 CAN BE GENERALIZED TO THE TOSSING OF N N-SIDED DICE THE TOTAL NUMBER OF SAMPLE POINTS WITHOUT REGARD TO ORDER AND WITH REPLACEMENT IS, FROM EQ (3 2 7) N 1 Þ N N ¼ 2N N (3:3:8) OUT OF THESE, THE NUMBER OF WAYS EXACTLY R DIGITS WILL OCCUR CAN BE DERIVED AS FOLLOWS: THE NUMBER OF WAYS R DIGITS CAN BE CHOSEN FROM N IS N R , AND IF ANY PARTICULAR SEQUENCE OF R DIGITS HAS TO ?LL N SLOTS, THEN THE NUMBER OF WAYS THIS CAN BE DONE IS OBTAINED BY SUBSTITUTING R ¼ (N 2 R) IN EQ (3 2 7), YIELDING R 1 Þ (N R) N R ¼ N SINCE ALL THE N R SEQUENCES ARE FUNCTIONALLY INDEPENDENT, THE NUMBER OF WAYS N(N,R) IS AS FOLLOWS, FROM EQ (3 1 2): N(N,R) ¼ N R ¼ N N R (3:3:10) USING EQ (3 3 10), N(N,R) TABULATED FOR N ¼ 1, , 8 AND R ¼ 1, , 8 IN FIG 3 3 4 IN ADDITION, WE HAVE THE FOLLOWING INTERESTING IDENTITY COMBINING EQS (3 3 8) AND (3 3 9), WE HAVE 2N N R N N K M R K ¼ N Þ N N K N BASIC COMBINATORICS CHAPTER TOSSING A DIE 5 TIMES CAN BE CONSIDERED BERNOULLI TRIALS IF WE DE?NE GETTING AN ACE AS SUCCESS, S WITH PFSG ¼ 6 AND NOT GETTING AN ACE AS FAILURE, F WITH PF FG ¼ 6 THE RESULTING SAMPLE SPACE S IS THE CARTESIAN PRODUCT WITH ORDERED QUINTUPLES WITH NUMBER OF POINTS EQUALING THE CARDINALITY 25 ¼ 32 BERNOULLI DISTRIBUTION BERNOULLI DISTRIBUTION IS THE SIMPLEST OF A DISCRETE DISTRIBUTION A SINGLE EVENT IS BERNOULLI DISTRIBUTED IF THE PROBABILITY OF SUCCESS IS P AND PROBABILITY OF FAILURE IS Q WITH P Þ Q ¼ 1 A SINGLE DIE IS THROWN THE PROBABILITY OF GETTING AN ACE IS P ¼ 6 AND THE PROBABILITY OF NOT GETTING AN ACE IS Q ¼ N K PKQNK ¼ (P Þ Q)N ¼ N K PKQNK (4:2:4) AND THE PROBABILITY OF GETTING AT LEAST R SUCCESSES IS GIVEN BY P{NUMBER OF SUCCESSES R} ¼ X N K¼R B(K;N,P) ¼ X N K¼R N K PKQNK (4:2:5) DISCRETE DISTRIBUTIONS SINCE N! GROWS VERY RAPIDLY WITH N, COMPUTATIONAL DIF?CULTIES IN CALCULATING B(K;N,P) CAN BE AVOIDED BY USING THE RECURSIVE FORMULA SHOWN BELOW WITH STARTING VALUE B(0;N,P) B(K Þ 1;N,P) ¼ N K Þ A FAIR DIE IS ROLLED 10 TIMES, AND WE WILL CALCULATE 1 THE PROBABILITY THAT AN ACE COMES UP EXACTLY 4 TIMES SUBSTITUTING P ¼ 6 AND Q ¼ 6, N ¼ 10, AND K ¼ 4 IN EQ (4 2 3), WE OBTAIN P{6 ACES IN 10 TRIALS} ¼ 10! 6!4! 2 THE PROBABILITY THAT UTMOST 4 ACES SHOW UP IN PROBABILITY 1 (ABOVE) WE WANTED EXACTLY 4 ACES COMING UP NOW WE ARE LOOKING INTO THE POSSIBILITY OF 4 OR FEWER ACES SHOWING UP THIS PROBABILITY IS OBTAINED AS FOLLOWS: P{NUMBER OF ACES 4} ¼ X 10! K!(10 K)! 3 THE PROBABILITY THAT THE NUMBER OF ACES SHOWING IS BETWEEN 2 AND 6 INCLUSIVE HERE WE HAVE TO SUM B(K: 10, 6) BETWEEN 2 AND 6 PERFORMING THE INDICATED SUMMATION, WE HAVE P{2 NUMBER OF ACES 6} ¼ X THE GRAPH OF THE PROBABILITY MASS FUNCTION I ( 6 )K( BINOMIAL DISTRIBUTION WE SHALL USE THE RECURSIVE FORM [EQ (4 2 6)] TO COMPUTE THE BINOMIAL COEF?CIENTS IN EXAMPLE 4 2 1 WITH INITIAL CONDITION B(0;N,P) ¼ 0 161506 THESE VALUES ARE SUBSTITUTED IN EQ (4 2 4), AND THE ?RST FOUR STEPS ARE SHOWN: B 0; 10, B 1; 10, B 2; 10, B 3; 10, B(K;N,P) K COMPUTED CALCULATED K COMPUTED CALCULATED DISCRETE DISTRIBUTIONS THE PROBABILITY OF GETTING ONE OR MORE