Probability
Department of Mathematics
The Chinese University of Hong Kong
HSMMC Math Modelling Advanced Training Workshop
June 27, 2026
1 Permutations and Combinations
Two core counting techniques are permutations and combinations. A permutation counts the number of distinct arrangements where the order of selection matters.
1.1 Illustrative Example: Ordered Selection of 3 Cards from 5
We have five distinct cards labeled \(1, 2, 3, 4, 5\). We select three cards, and the sequence/order of selection is important.
\[ 5 \times 4 \times 3 = 60 \]
\[ \begin{array}{ccc} \bf \fbox{1} & \fbox{2} & \fbox{3} \\ \textrm{(1 of 5 cards)} & \textrm{(1 of 4 remaining cards)} & \textrm{(1 of 3 remaining cards)} \end{array} \]
1.2 Step-by-Step Logical Reasoning:
We place the three selected cards into ordered positions 1, 2, 3:
- Position \(\bf 1\): There are 5 available numbers: \(1,2,3,4,5\) (5 total choices).
- Position \(\bf 2\): One card is already used for position \(\bf 1\), leaving 4 unused cards (4 total choices).
- Position \(\bf 3\): Two cards are already used for positions \(\bf 1\) and \(\bf 2\), leaving only 3 unused cards (3 total choices).
By the multiplication principle of counting, multiply the number of choices for each position: \[ \text{Total ordered outcomes} = 5 \times 4 \times 3 = \boldsymbol{60} \]
1.3 General Permutation Definition and Formula
When selecting \(k\) distinct items from a set of \(n\) distinct items with order preserved, this count is called a permutation, denoted \(\boldsymbol{{}_n P_k}\).
Base product form (finite descending product): \[ {}_n P_k = n\,(n-1)\,(n-2)\cdots(n-k+1), \quad \text{for } k \le n \]
If we select all \(n\) items (\(k=n\)): \[ {}_n P_n = n\,(n-1)\,(n-2)\cdots 2 \cdot 1 \] This product is defined as the of \(n\), written \(n!\) (read ``\(n\) factorial’’).
1.4 Factorial Equivalent Derivation (Step-by-Step Algebra):
Multiply numerator and denominator by the trailing product \((n-k)(n-k-1)\cdots 2\cdot 1 = (n-k)!\): \[ \begin{aligned} {}_n P_k &= n\,(n-1)\cdots(n-k+1) \\ &= \frac{\big[n\,(n-1)\cdots(n-k+1)\big] \cdot \big[(n-k)\cdots 2\cdot 1\big]}{(n-k)\cdots 2\cdot 1} \\ &= \frac{n!}{(n-k)!} \end{aligned} \]
1.5 Example 1: Numerical Verification for the Card Example (\(n=5,\,k=3\))
\[\begin{align*} {}_5 P_3 &= \frac{5!}{(5-3)!} = \frac{5!}{2!} \\ 5! &= 5\times4\times3\times2\times1 = 120 \\ 2! &= 2\times1 = 2 \\ {}_5 P_3 &= \frac{120}{2} = \boldsymbol{60} \end{align*}\] Matches the direct product calculation result, confirming correctness.
def compute_factorial(x):
"""Calculate factorial and print expansion steps"""
if x == 0 or x == 1:
print(f"{x}! = 1 (standard factorial definition)")
return 1
running_product = 1
term_list = []
for val in range(x, 0, -1):
term_list.append(str(val))
running_product *= val
expansion_str = " × ".join(term_list)
print(f"{x}! = {expansion_str} = {running_product}")
return running_product
def permutation(n, k):
"""Compute _nP_k = n!/(n−k)! with full printed steps"""
print(f"\n=== Calculating Permutation _nP_k for n={n}, k={k} ===")
print(f"Formula: _nP_k = {n}! / ({n} - {k})! = {n}! / {n - k}!")
n_fact = compute_factorial(n)
nk_fact = compute_factorial(n - k)
perm_result = n_fact // nk_fact
print(f"\nDivision step: {n_fact} ÷ {nk_fact} = {perm_result}")
return perm_result
# Test the 5 cards choose 3 example from the text
result = permutation(n=5, k=3)##
## === Calculating Permutation _nP_k for n=5, k=3 ===
## Formula: _nP_k = 5! / (5 - 3)! = 5! / 2!
## 5! = 5 × 4 × 3 × 2 × 1 = 120
## 2! = 2 × 1 = 2
##
## Division step: 120 ÷ 2 = 60##
## Final total ordered card arrangements: 60import math
def perm(n, k):
# Integer division for whole-number permutation counts
return math.factorial(n) // math.factorial(n - k)
# Evaluate textbook example
card_arrangements = perm(5, 3)
print(f"Permutation P(5,3) = {card_arrangements}")## Permutation P(5,3) = 602 Combination Definition and Formula
A combination counts the number of ways to select items where the order of selection does not matter.
2.1 Illustrative Example: Select 3 unordered cards from 5 cards labeled \(1,2,3,4,5\)
Direct computation: \[ \frac{5 \times 4 \times 3}{3!} = 10 \]
2.2 Step 1: Explain order equivalence
Suppose the selected values are \(1,2,3\).
If order matters (permutation), there are \(3! = 3\times2\times1 = 6\) distinct ordered arrangements: \[(1,2,3),\;(1,3,2),\;(2,1,3),\;(2,3,1),\;(3,1,2),\;(3,2,1)\]
For combinations, all 6 ordered groupings count as one identical unordered group. To eliminate redundant permutations of the \(k\) selected items, we divide the total permutation count by \(k!\).
2.3 Step 2: Rewrite numerator using factorials
The numerator \(5\times4\times3\) is the permutation \({}_5 P_3 = \frac{5!}{(5-3)!} = \frac{5!}{2!}\). Expand factorial definitions: \[ 5! = 5\times4\times3\times2\times1,\quad 2! = 2\times1 \] Canceling \(2!\) from numerator and denominator leaves \(5\times4\times3\). Substitute back into the combination expression: \[ \frac{5\times4\times3}{3!} = \frac{\dfrac{5!}{2!}}{3!} = \frac{5!}{3!\cdot 2!} \]
2.4 Step 3: Verify numerical value step-by-step
\[\begin{align*} 3! &= 3\times2\times1 = 6 \\ 5\times4\times3 &= 60 \\ \frac{60}{6} &= \boldsymbol{10} \end{align*}\]
2.5 General Combination Formula
When choosing \(k\) items from \(n\) distinct items with no regard to order, the combination count is denoted \({}_n C_k\) (also written binomial coefficient \(\dbinom{n}{k}\)). \[ {}_n C_k = \frac{{}_n P_k}{k!} = \frac{n!}{(n-k)!\,k!} = \binom{n}{k},\quad \text{for } k\le n \]
2.6 Example 2: Choose 5 ties out of 500 ties
Problem: Find the number of unordered ways to pick 5 ties from 500 total ties. By combination formula, \(n=500,\;k=5\): \[ \binom{500}{5} = \frac{500!}{5!\cdot (500-5)!} = \frac{500!}{5!\cdot 495!} \]
2.6.1 Simplify the fraction for manual computation (cancel \(495!\)):
\[ \begin{aligned} \binom{500}{5} &= \frac{500 \times 499 \times 498 \times 497 \times 496 \times 495!}{5! \times 495!} \\ &= \frac{500 \times 499 \times 498 \times 497 \times 496}{5\times4\times3\times2\times1} \end{aligned} \]
2.6.2 Full arithmetic calculation step-by-step:
Numerator product: \[ 500 \times 499 = 249500,\quad 249500 \times 498 = 124251000,\quad 124251000 \times 497 = 61752747000,\quad 61752747000 \times 496 = 30629362512000 \] Denominator \(5! = 120\) \[ \binom{500}{5} = \frac{30629362512000}{120} = \boldsymbol{255244687600} \]
def factorial(x):
"""Compute factorial and print expansion steps"""
if x == 0 or x == 1:
print(f"{x}! = 1")
return 1
prod = 1
terms = []
for num in range(x, 0, -1):
terms.append(str(num))
prod *= num
expr = " × ".join(terms)
print(f"{x}! = {expr} = {prod}")
return prod
def combination(n, k):
"""Calculate C(n,k) = n!/(k!*(n-k)!) with printed breakdown"""
print(f"\n=== Calculating Combination C({n}, {k}) ===")
print(f"Formula: C(n,k) = {n}! / ( {k}! × ({n}-{k})! ) = {n}! / ( {k}! × {n-k}! )")
n_fact = factorial(n)
k_fact = factorial(k)
nk_fact = factorial(n - k)
comb_val = n_fact // (k_fact * nk_fact)
print(f"\nFinal division: {n_fact} ÷ ({k_fact} × {nk_fact}) = {comb_val}")
return comb_val
# Test 1: Card example n=5, k=3
print("===== Test 1: Pick 3 unordered cards from 5 =====")## ===== Test 1: Pick 3 unordered cards from 5 =====##
## === Calculating Combination C(5, 3) ===
## Formula: C(n,k) = 5! / ( 3! × (5-3)! ) = 5! / ( 3! × 2! )
## 5! = 5 × 4 × 3 × 2 × 1 = 120
## 3! = 3 × 2 × 1 = 6
## 2! = 2 × 1 = 2
##
## Final division: 120 ÷ (6 × 2) = 10## Answer (unordered card groups): 10## ===== Test 2: Pick 5 unordered ties from 500 =====##
## === Calculating Combination C(500, 5) ===
## Formula: C(n,k) = 500! / ( 5! × (500-5)! ) = 500! / ( 5! × 495! )
## 500! = 500 × 499 × 498 × 497 × 496 × 495 × 494 × 493 × 492 × 491 × 490 × 489 × 488 × 487 × 486 × 485 × 484 × 483 × 482 × 481 × 480 × 479 × 478 × 477 × 476 × 475 × 474 × 473 × 472 × 471 × 470 × 469 × 468 × 467 × 466 × 465 × 464 × 463 × 462 × 461 × 460 × 459 × 458 × 457 × 456 × 455 × 454 × 453 × 452 × 451 × 450 × 449 × 448 × 447 × 446 × 445 × 444 × 443 × 442 × 441 × 440 × 439 × 438 × 437 × 436 × 435 × 434 × 433 × 432 × 431 × 430 × 429 × 428 × 427 × 426 × 425 × 424 × 423 × 422 × 421 × 420 × 419 × 418 × 417 × 416 × 415 × 414 × 413 × 412 × 411 × 410 × 409 × 408 × 407 × 406 × 405 × 404 × 403 × 402 × 401 × 400 × 399 × 398 × 397 × 396 × 395 × 394 × 393 × 392 × 391 × 390 × 389 × 388 × 387 × 386 × 385 × 384 × 383 × 382 × 381 × 380 × 379 × 378 × 377 × 376 × 375 × 374 × 373 × 372 × 371 × 370 × 369 × 368 × 367 × 366 × 365 × 364 × 363 × 362 × 361 × 360 × 359 × 358 × 357 × 356 × 355 × 354 × 353 × 352 × 351 × 350 × 349 × 348 × 347 × 346 × 345 × 344 × 343 × 342 × 341 × 340 × 339 × 338 × 337 × 336 × 335 × 334 × 333 × 332 × 331 × 330 × 329 × 328 × 327 × 326 × 325 × 324 × 323 × 322 × 321 × 320 × 319 × 318 × 317 × 316 × 315 × 314 × 313 × 312 × 311 × 310 × 309 × 308 × 307 × 306 × 305 × 304 × 303 × 302 × 301 × 300 × 299 × 298 × 297 × 296 × 295 × 294 × 293 × 292 × 291 × 290 × 289 × 288 × 287 × 286 × 285 × 284 × 283 × 282 × 281 × 280 × 279 × 278 × 277 × 276 × 275 × 274 × 273 × 272 × 271 × 270 × 269 × 268 × 267 × 266 × 265 × 264 × 263 × 262 × 261 × 260 × 259 × 258 × 257 × 256 × 255 × 254 × 253 × 252 × 251 × 250 × 249 × 248 × 247 × 246 × 245 × 244 × 243 × 242 × 241 × 240 × 239 × 238 × 237 × 236 × 235 × 234 × 233 × 232 × 231 × 230 × 229 × 228 × 227 × 226 × 225 × 224 × 223 × 222 × 221 × 220 × 219 × 218 × 217 × 216 × 215 × 214 × 213 × 212 × 211 × 210 × 209 × 208 × 207 × 206 × 205 × 204 × 203 × 202 × 201 × 200 × 199 × 198 × 197 × 196 × 195 × 194 × 193 × 192 × 191 × 190 × 189 × 188 × 187 × 186 × 185 × 184 × 183 × 182 × 181 × 180 × 179 × 178 × 177 × 176 × 175 × 174 × 173 × 172 × 171 × 170 × 169 × 168 × 167 × 166 × 165 × 164 × 163 × 162 × 161 × 160 × 159 × 158 × 157 × 156 × 155 × 154 × 153 × 152 × 151 × 150 × 149 × 148 × 147 × 146 × 145 × 144 × 143 × 142 × 141 × 140 × 139 × 138 × 137 × 136 × 135 × 134 × 133 × 132 × 131 × 130 × 129 × 128 × 127 × 126 × 125 × 124 × 123 × 122 × 121 × 120 × 119 × 118 × 117 × 116 × 115 × 114 × 113 × 112 × 111 × 110 × 109 × 108 × 107 × 106 × 105 × 104 × 103 × 102 × 101 × 100 × 99 × 98 × 97 × 96 × 95 × 94 × 93 × 92 × 91 × 90 × 89 × 88 × 87 × 86 × 85 × 84 × 83 × 82 × 81 × 80 × 79 × 78 × 77 × 76 × 75 × 74 × 73 × 72 × 71 × 70 × 69 × 68 × 67 × 66 × 65 × 64 × 63 × 62 × 61 × 60 × 59 × 58 × 57 × 56 × 55 × 54 × 53 × 52 × 51 × 50 × 49 × 48 × 47 × 46 × 45 × 44 × 43 × 42 × 41 × 40 × 39 × 38 × 37 × 36 × 35 × 34 × 33 × 32 × 31 × 30 × 29 × 28 × 27 × 26 × 25 × 24 × 23 × 22 × 21 × 20 × 19 × 18 × 17 × 16 × 15 × 14 × 13 × 12 × 11 × 10 × 9 × 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1 = 1220136825991110068701238785423046926253574342803192842192413588385845373153881997605496447502203281863013616477148203584163378722078177200480785205159329285477907571939330603772960859086270429174547882424912726344305670173270769461062802310452644218878789465754777149863494367781037644274033827365397471386477878495438489595537537990423241061271326984327745715546309977202781014561081188373709531016356324432987029563896628911658974769572087926928871281780070265174507768410719624390394322536422605234945850129918571501248706961568141625359056693423813008856249246891564126775654481886506593847951775360894005745238940335798476363944905313062323749066445048824665075946735862074637925184200459369692981022263971952597190945217823331756934581508552332820762820023402626907898342451712006207714640979456116127629145951237229913340169552363850942885592018727433795173014586357570828355780158735432768888680120399882384702151467605445407663535984174430480128938313896881639487469658817504506926365338175055478128640000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
## 5! = 5 × 4 × 3 × 2 × 1 = 120
## 495! = 495 × 494 × 493 × 492 × 491 × 490 × 489 × 488 × 487 × 486 × 485 × 484 × 483 × 482 × 481 × 480 × 479 × 478 × 477 × 476 × 475 × 474 × 473 × 472 × 471 × 470 × 469 × 468 × 467 × 466 × 465 × 464 × 463 × 462 × 461 × 460 × 459 × 458 × 457 × 456 × 455 × 454 × 453 × 452 × 451 × 450 × 449 × 448 × 447 × 446 × 445 × 444 × 443 × 442 × 441 × 440 × 439 × 438 × 437 × 436 × 435 × 434 × 433 × 432 × 431 × 430 × 429 × 428 × 427 × 426 × 425 × 424 × 423 × 422 × 421 × 420 × 419 × 418 × 417 × 416 × 415 × 414 × 413 × 412 × 411 × 410 × 409 × 408 × 407 × 406 × 405 × 404 × 403 × 402 × 401 × 400 × 399 × 398 × 397 × 396 × 395 × 394 × 393 × 392 × 391 × 390 × 389 × 388 × 387 × 386 × 385 × 384 × 383 × 382 × 381 × 380 × 379 × 378 × 377 × 376 × 375 × 374 × 373 × 372 × 371 × 370 × 369 × 368 × 367 × 366 × 365 × 364 × 363 × 362 × 361 × 360 × 359 × 358 × 357 × 356 × 355 × 354 × 353 × 352 × 351 × 350 × 349 × 348 × 347 × 346 × 345 × 344 × 343 × 342 × 341 × 340 × 339 × 338 × 337 × 336 × 335 × 334 × 333 × 332 × 331 × 330 × 329 × 328 × 327 × 326 × 325 × 324 × 323 × 322 × 321 × 320 × 319 × 318 × 317 × 316 × 315 × 314 × 313 × 312 × 311 × 310 × 309 × 308 × 307 × 306 × 305 × 304 × 303 × 302 × 301 × 300 × 299 × 298 × 297 × 296 × 295 × 294 × 293 × 292 × 291 × 290 × 289 × 288 × 287 × 286 × 285 × 284 × 283 × 282 × 281 × 280 × 279 × 278 × 277 × 276 × 275 × 274 × 273 × 272 × 271 × 270 × 269 × 268 × 267 × 266 × 265 × 264 × 263 × 262 × 261 × 260 × 259 × 258 × 257 × 256 × 255 × 254 × 253 × 252 × 251 × 250 × 249 × 248 × 247 × 246 × 245 × 244 × 243 × 242 × 241 × 240 × 239 × 238 × 237 × 236 × 235 × 234 × 233 × 232 × 231 × 230 × 229 × 228 × 227 × 226 × 225 × 224 × 223 × 222 × 221 × 220 × 219 × 218 × 217 × 216 × 215 × 214 × 213 × 212 × 211 × 210 × 209 × 208 × 207 × 206 × 205 × 204 × 203 × 202 × 201 × 200 × 199 × 198 × 197 × 196 × 195 × 194 × 193 × 192 × 191 × 190 × 189 × 188 × 187 × 186 × 185 × 184 × 183 × 182 × 181 × 180 × 179 × 178 × 177 × 176 × 175 × 174 × 173 × 172 × 171 × 170 × 169 × 168 × 167 × 166 × 165 × 164 × 163 × 162 × 161 × 160 × 159 × 158 × 157 × 156 × 155 × 154 × 153 × 152 × 151 × 150 × 149 × 148 × 147 × 146 × 145 × 144 × 143 × 142 × 141 × 140 × 139 × 138 × 137 × 136 × 135 × 134 × 133 × 132 × 131 × 130 × 129 × 128 × 127 × 126 × 125 × 124 × 123 × 122 × 121 × 120 × 119 × 118 × 117 × 116 × 115 × 114 × 113 × 112 × 111 × 110 × 109 × 108 × 107 × 106 × 105 × 104 × 103 × 102 × 101 × 100 × 99 × 98 × 97 × 96 × 95 × 94 × 93 × 92 × 91 × 90 × 89 × 88 × 87 × 86 × 85 × 84 × 83 × 82 × 81 × 80 × 79 × 78 × 77 × 76 × 75 × 74 × 73 × 72 × 71 × 70 × 69 × 68 × 67 × 66 × 65 × 64 × 63 × 62 × 61 × 60 × 59 × 58 × 57 × 56 × 55 × 54 × 53 × 52 × 51 × 50 × 49 × 48 × 47 × 46 × 45 × 44 × 43 × 42 × 41 × 40 × 39 × 38 × 37 × 36 × 35 × 34 × 33 × 32 × 31 × 30 × 29 × 28 × 27 × 26 × 25 × 24 × 23 × 22 × 21 × 20 × 19 × 18 × 17 × 16 × 15 × 14 × 13 × 12 × 11 × 10 × 9 × 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1 = 39835527935427442653307246390889133574455058929474360918831440169865373173062205245987407819877230158625954248105449553737789484754202879130453683311034798251040647448239996323595729529242460558022987116647853214200309640883549364452499131740748918231314884434143823158375186224673641496062809972380056937780444997576203214305328732152335729333031277824713798129156112852590636201781658170402000138642530440170821847233900697242790032037350027852544137918297862391191896981741518799468846174738258138349655578686063236119130723929973173232037676743659319972210894275877710333185091850615091699690800778651674399080909618893555520041340693021809886928098043362394126080750337167664977655745225761742519841258652832147366990072007520590506718330245094485979644081447888376081078472943701147302371285456158635432103502841496876705880085878159883750361223277928135652117374579120356599205611267455058317952893096761242338655156781065342979004276319051014016381377369519365969606362756724961345364788510720000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
##
## Final division: 1220136825991110068701238785423046926253574342803192842192413588385845373153881997605496447502203281863013616477148203584163378722078177200480785205159329285477907571939330603772960859086270429174547882424912726344305670173270769461062802310452644218878789465754777149863494367781037644274033827365397471386477878495438489595537537990423241061271326984327745715546309977202781014561081188373709531016356324432987029563896628911658974769572087926928871281780070265174507768410719624390394322536422605234945850129918571501248706961568141625359056693423813008856249246891564126775654481886506593847951775360894005745238940335798476363944905313062323749066445048824665075946735862074637925184200459369692981022263971952597190945217823331756934581508552332820762820023402626907898342451712006207714640979456116127629145951237229913340169552363850942885592018727433795173014586357570828355780158735432768888680120399882384702151467605445407663535984174430480128938313896881639487469658817504506926365338175055478128640000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 ÷ (120 × 39835527935427442653307246390889133574455058929474360918831440169865373173062205245987407819877230158625954248105449553737789484754202879130453683311034798251040647448239996323595729529242460558022987116647853214200309640883549364452499131740748918231314884434143823158375186224673641496062809972380056937780444997576203214305328732152335729333031277824713798129156112852590636201781658170402000138642530440170821847233900697242790032037350027852544137918297862391191896981741518799468846174738258138349655578686063236119130723929973173232037676743659319972210894275877710333185091850615091699690800778651674399080909618893555520041340693021809886928098043362394126080750337167664977655745225761742519841258652832147366990072007520590506718330245094485979644081447888376081078472943701147302371285456158635432103502841496876705880085878159883750361223277928135652117374579120356599205611267455058317952893096761242338655156781065342979004276319051014016381377369519365969606362756724961345364788510720000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000) = 255244687600## Answer (unordered tie selections): 255244687600import math
def comb(n, k):
return math.factorial(n) // (math.factorial(k) * math.factorial(n - k))
# Evaluate examples
card_groups = comb(5, 3)
tie_choices = comb(500, 5)
print(f"C(5,3) (card groups) = {card_groups}")## C(5,3) (card groups) = 10## C(500,5) (tie selections) = 2552446876003 Permutations and Combinations with Repetition
Mathematically, this expression represents the binomial coefficient: \[ \binom{500}{5} \]
Calculations may also be performed using R built-in
command for binomial coefficients:
## binomial(500,5) = 255244687600Up to this point, we have covered counting problems with no repeated selections. When repetition of items is permitted, we use separate formulas for permutations and combinations with repetition.
3.1 1) Permutations with Repetition (Repeated Permutation): Symbol \(\boldsymbol{{}_n \Pi_k}\)
\({}_n \Pi_k\) denotes ordered selection of \(k\) items from \(n\) distinct types, where items may be reused (repetition allowed). \[ \boldsymbol{{}_n \Pi_k = n^k} \]
3.2 2) Combinations with Repetition (Repeated Combination): Symbol \(\boldsymbol{{}_n H_k}\)
\({}_n H_k\) denotes unordered selection of \(k\) items from \(n\) distinct types, where items may be reused (repetition allowed). The formula transforms to a standard binomial coefficient: \[ \boldsymbol{{}_n H_k = \binom{n+k-1}{k}} \]
3.3 Example 3
Select three numbers from \(\{1,2,3,4,5\}\), arrange them sequentially to form three-digit natural numbers (repetition permitted). Find how many such three-digit numbers are multiples of \(5\).
3.3.1 Step-by-Step Solution Reasoning:
A natural number is a multiple of \(5\) if its units digit equals \(0\) or \(5\). Our available digits are only \(1,2,3,4,5\), so the units digit must be fixed as \(5\).
Position 3 (units place): Only 1 valid choice (\(5\))
Positions 1 (hundreds) and 2 (tens): We select 2 digits from \(\{1,2,3,4,5\}\) with repetition allowed (\(n=5,\ k=2\))
This is a permutation-with-repetition problem for the first two digits: \({}_n \Pi_k = n^k\)
\[\begin{align*} n &= 5,\quad k=2 \\ {}_5 \Pi_2 &= 5^2 \\ 5^2 &= 5 \times 5 = \boldsymbol{25} \end{align*}\] Total valid three-digit multiples of 5: \(\boldsymbol{25}\)
3.4 Example 4
Four people cast anonymous votes for one of three candidates: A, B, C. Find the total number of distinct vote outcome distributions.
3.4.1 Step-by-Step Solution Reasoning:
Votes are anonymous, so only the count of votes for each candidate matters (order of voters does not matter). This is a combination-with-repetition scenario:
\(n = 3\) distinct candidate types (A,B,C)
\(k = 4\) total votes to distribute
Formula: \({}_n H_k = \binom{n+k-1}{k}\)
\[\begin{align*} {}_3 H_4 &= \binom{3+4-1}{4} = \binom{6}{4} \end{align*}\] Binomial coefficient simplification: \(\dbinom{6}{4} = \dbinom{6}{2}\) \[\begin{align*} \binom{6}{2} &= \frac{6!}{2!\,(6-2)!} = \frac{6!}{2!\,4!} \\ 6! &= 6 \times 5 \times 4! \\ \binom{6}{2} &= \frac{6 \times 5 \times 4!}{(2\times1) \times 4!} = \frac{30}{2} = \boldsymbol{15} \end{align*}\] Total unique anonymous vote distributions: \(\boldsymbol{15}\)
import math
def factorial(x):
"""Compute factorial and print expansion steps"""
if x == 0 or x == 1:
print(f"{x}! = 1")
return 1
product = 1
terms = []
for val in range(x, 0, -1):
terms.append(str(val))
product *= val
exp_str = " × ".join(terms)
print(f"{x}! = {exp_str} = {product}")
return product
def perm_repeat(n, k):
"""Permutation with repetition: n^k"""
print(f"\nPermutation with repetition _{n}Î _{k} = {n}^{k}")
res = n ** k
print(f"{n} × {n} × ... ({k} times) = {res}")
return res
def comb_repeat(n, k):
"""Combination with repetition: binomial(n+k-1, k)"""
upper = n + k - 1
print(f"\nCombination with repetition _{n}H_{k} = binom({upper}, {k})")
numer = factorial(upper)
denom = factorial(k) * factorial(upper - k)
res = numer // denom
print(f"binom({upper},{k}) = {numer} ÷ ({factorial(k)} × {factorial(upper - k)}) = {res}")
return res
# 1. SageMath binomial reference test (C(500,5))
print("=== SageMath binomial(500,5) Equivalent ===")## === SageMath binomial(500,5) Equivalent ===c500_5 = math.factorial(500) // (math.factorial(5)*math.factorial(495))
print(f"C(500,5) = {c500_5}\n")## C(500,5) = 255244687600# Example 3: 3-digit multiple of 5, digits {1,2,3,4,5}, repetition allowed
print("===== Example 3: Three-digit multiples of 5 =====")## ===== Example 3: Three-digit multiples of 5 =====##
## Permutation with repetition _5Î _2 = 5^2
## 5 × 5 × ... (2 times) = 25## Total valid numbers = 25# Example 4: 4 votes for 3 candidates (anonymous)
print("===== Example 4: Anonymous vote distributions =====")## ===== Example 4: Anonymous vote distributions =====##
## Combination with repetition _3H_4 = binom(6, 4)
## 6! = 6 × 5 × 4 × 3 × 2 × 1 = 720
## 4! = 4 × 3 × 2 × 1 = 24
## 2! = 2 × 1 = 2
## 4! = 4 × 3 × 2 × 1 = 24
## 2! = 2 × 1 = 2
## binom(6,4) = 720 ÷ (24 × 2) = 15## Total unique vote outcomes = 15import math
# Permutation with repetition: n^k
def perm_rep(n, k):
return n ** k
# Combination with repetition: C(n+k-1, k)
def comb_rep(n, k):
return math.comb(n + k - 1, k)
# Test all cases
print(f"Sage binomial(500,5) = {math.comb(500,5)}")## Sage binomial(500,5) = 255244687600## Example3 (3-digit multiples of 5): 25## Example4 (4 votes,3 candidates): 154 Probability
The probability that a specific event occurs takes a value in the interval \([0,1]\). For example, flipping a fair coin has a probability of \(\frac12\) for landing on heads.
When flipping a coin, only two outcomes exist: heads or tails. There are \(2\) total possible outcomes, and exactly \(1\) favorable outcome for heads.
A probability value of \(0\) means the event is impossible (can never happen).
A probability value of \(1\) means the event is certain (must happen).
To compute probability mathematically, we first define the full set of all possible outcomes.
Coin flip sample space: \(S=\{\text{head},\text{tail}\}\)
Standard six-sided die sample space: \(S=\{1,2,3,4,5,6\}\)
This complete collection of all possible outcomes is called the sample space, denoted \(S\).
4.1 Formal Classical Probability Definition
Let:
\(n(S) =\) total number of distinct possible outcomes in sample space \(S\)
\(n(A) =\) number of favorable outcomes for a specific event \(A\)
The classical probability of event \(A\), written \(P(A)\), is defined as: \[ P(A) = \frac{\text{number of favorable outcomes for }A}{\text{total number of possible outcomes}} = \boldsymbol{\frac{n(A)}{n(S)}} \]
4.2 Geometric Probability Definition
For geometric problems where \(S\) represents a total region/area, and \(A\subset S\) (event region lies entirely within sample space region): \[ P(A) = \boldsymbol{\frac{\text{Area of region }A}{\text{Area of region }S}} \]
4.3 Statistical Probability & Law of Large Numbers
In practical experimental trials:
Suppose an identical trial is repeated \(n\) total times, and event \(A\) is observed to occur \(k\) of those times. The relative frequency (statistical probability) of event \(A\) is: \[ \frac{k}{n} \]
As the number of trials \(n\) grows infinitely large, the relative frequency converges to a fixed constant value \(\mathcal{P}\), called the mathematical probability \(P(A)\).
This convergence property is the Law of Large Numbers, expressed formally with a limit: \[ \boldsymbol{\lim_{n\to\infty} \frac{k}{n} = P(A)} \]
4.4 Fundamental Probability Axioms & Properties
Let \(A\) be any event within sample space \(S\):
Bounded range: \(\boldsymbol{0 \le P(A) \le 1}\) for any valid event \(A\subseteq S\)
Certainty of full sample space: \(\boldsymbol{P(S) = 1}\)
Impossible empty event: \(\boldsymbol{P(\emptyset) = 0}\) (\(\emptyset\) = empty set, no outcomes)
Additivity for mutually exclusive events: If \(A\) and \(B\) cannot happen simultaneously (disjoint, \(A\cap B=\emptyset\)): \[ \boldsymbol{P(A\cup B) = P(A) + P(B)} \]
Complement rule: Let \(A^c\) (also written \(\overline{A}\)) denote the complement event (all outcomes where \(A\) occur): \[ \boldsymbol{P(A^c) = 1 - P(A)} \]
4.4.1 Step-by-Step Example Calculation (Coin Flip Heads)
\[\begin{align*} S &= \{\text{head},\text{tail}\} \implies n(S)=2 \\ A &= \{\text{head}\} \implies n(A)=1 \\ P(\text{head}) &= \frac{n(A)}{n(S)} = \frac{1}{2} = \boldsymbol{0.5} \end{align*}\]
4.4.2 Step-by-Step Example Calculation (Die Roll, Event = Roll a 3)
\[\begin{align*} S &= \{1,2,3,4,5,6\} \implies n(S)=6 \\ A &= \{3\} \implies n(A)=1 \\ P(\text{roll }3) &= \frac{1}{6} \approx \boldsymbol{0.1667} \end{align*}\]
def classical_probability(favorable, total):
"""
Classical probability P(A) = n(A)/n(S)
favorable: n(A), total: n(S)
"""
print(f"\nClassical Probability Calculation:")
print(f"n(A) (favorable outcomes) = {favorable}")
print(f"n(S) (total sample space outcomes) = {total}")
prob = favorable / total
print(f"P(A) = {favorable} / {total} = {prob:.4f}")
return prob
def complement_prob(p_a):
"""Complement rule P(A^c) = 1 - P(A)"""
p_ac = 1 - p_a
print(f"\nComplement Event Calculation:")
print(f"P(A) = {p_a:.4f}, so P(A^c) = 1 - {p_a:.4f} = {p_ac:.4f}")
return p_ac
def geometric_prob(area_a, area_s):
"""Geometric probability P(A) = Area(A)/Area(S)"""
prob = area_a / area_s
print(f"\nGeometric Probability Calculation:")
print(f"Area(A) = {area_a}, Area(S) = {area_s}")
print(f"P(A) = {area_a}/{area_s} = {prob:.4f}")
return prob
# ---------------- Test Case 1: Coin flip heads ----------------
print("===== Test 1: Fair Coin, Event = Heads =====")## ===== Test 1: Fair Coin, Event = Heads =====##
## Classical Probability Calculation:
## n(A) (favorable outcomes) = 1
## n(S) (total sample space outcomes) = 2
## P(A) = 1 / 2 = 0.5000##
## Complement Event Calculation:
## P(A) = 0.5000, so P(A^c) = 1 - 0.5000 = 0.5000# ---------------- Test Case 2: Die roll a 3 ----------------
print("\n===== Test 2: 6-sided Die, Event = Roll 3 =====")##
## ===== Test 2: 6-sided Die, Event = Roll 3 =====##
## Classical Probability Calculation:
## n(A) (favorable outcomes) = 1
## n(S) (total sample space outcomes) = 6
## P(A) = 1 / 6 = 0.1667##
## Complement Event Calculation:
## P(A) = 0.1667, so P(A^c) = 1 - 0.1667 = 0.8333# ---------------- Test Case 3: Sample Geometric Probability ----------------
print("\n===== Test 3: Geometric Probability Example =====")##
## ===== Test 3: Geometric Probability Example =====# Suppose total square area = 100, shaded event area = 25
geo_p = geometric_prob(area_a=25, area_s=100)##
## Geometric Probability Calculation:
## Area(A) = 25, Area(S) = 100
## P(A) = 25/100 = 0.2500# Core probability formulas
def prob_classical(nA, nS):
return nA / nS
def prob_complement(pA):
return 1 - pA
def prob_geo(areaA, areaS):
return areaA / areaS
# Run examples
coin_head = prob_classical(1,2)
die_three = prob_classical(1,6)
geo_sample = prob_geo(25,100)
print(f"P(Coin Heads) = {coin_head}")## P(Coin Heads) = 0.5## P(Die roll 3) = 0.1667## P(Geometric shaded region) = 0.254.5 Example 5: Probability of Drawing Two Same-Colored Balls
Problem Statement: A pocket contains 3 black balls, 2 white balls, and 1 red ball (total of \(3+2+1=6\) balls). Two balls are drawn simultaneously at random. Calculate the probability that the two selected balls share the same color.
4.5.1 Step 1: Compute total number of unordered ways to pick 2 balls from 6
Drawing two balls at once is an unordered selection, so we use combinations \(\binom{n}{k}={}_n C_k\). Total sample space outcomes: \[ n(S) = \binom{6}{2} \] Expand and calculate step-by-step: \[\begin{align*} \binom{6}{2} &= \frac{6!}{2!\,(6-2)!} = \frac{6!}{2!\cdot 4!} \\ 6! &= 6\times5\times4! \\ \binom{6}{2} &= \frac{6\times5\times4!}{(2\times1)\times4!} = \frac{30}{2} = \boldsymbol{15} \end{align*}\]
4.5.2 Step 2: Count favorable outcomes (two balls of identical color)
Only black and white colors have at least two balls; there is only 1 red ball, so two red balls cannot be drawn.
Ways to pick 2 black balls from 3 black balls: \(\binom{3}{2}\) \[\begin{align*} \binom{3}{2} &= \frac{3!}{2!\cdot1!} = \frac{3\times2!}{2!\times1} = \boldsymbol{3} \end{align*}\]
Ways to pick 2 white balls from 2 white balls: \(\binom{2}{2}\) \[\begin{align*} \binom{2}{2} &= \frac{2!}{2!\cdot0!} = \frac{2!}{2!\times1} = \boldsymbol{1} \quad (\text{by definition }0!=1) \end{align*}\]
Total favorable outcomes \(n(A)\) = black pairs + white pairs: \[ n(A) = \binom{3}{2} + \binom{2}{2} = 3 + 1 = \boldsymbol{4} \]
\[ P(\text{same color}) = \frac{n(A)}{n(S)} = \frac{4}{15} \]
4.5.3 The mathematical expression above corresponds to:
\[ \frac{\binom{3}{2} + \binom{2}{2}}{\binom{6}{2}} \]
4.6 Example 6: Coin Flip Simulation with Python Code
We simulate repeated coin flips using the R programming language to observe relative frequency (statistical probability).
The table(coin) function outputs a frequency count showing how many times heads and tails appear across all simulated flips. As trial count increases, relative frequency \(\frac{\text{heads}}{n}\) converges to mathematical probability \(P(\text{head})=\frac12\) (Law of Large Numbers).
import math
def binom(n, k):
"""Binomial coefficient C(n,k) = n!/(k!*(n-k)!)"""
return math.factorial(n) // (math.factorial(k) * math.factorial(n - k))
# Step 1: Total ways to pick 2 balls from 6
total = binom(6, 2)
print(f"Total unordered pairs C(6,2) = {total}")## Total unordered pairs C(6,2) = 15# Step 2: Favorable same-color pairs
black_pairs = binom(3, 2)
white_pairs = binom(2, 2)
favorable = black_pairs + white_pairs
print(f"Black pairs C(3,2) = {black_pairs}")## Black pairs C(3,2) = 3## White pairs C(2,2) = 1## Total favorable same-color pairs = 4# Step3: Probability
prob = favorable / total
print(f"\nProbability(two same color) = {favorable}/{total} = {prob:.4f}")##
## Probability(two same color) = 4/15 = 0.2667# SageMath equivalent one-line calculation
sage_eq = (binom(3,2)+binom(2,2))/binom(6,2)
print(f"SageMath command result match: {sage_eq:.4f}")## SageMath command result match: 0.2667import random
import collections
def flip_coins(num_trials):
# Simulate coin flips: 0=Head, 1=Tail
outcomes = random.choices(["head", "tail"], k=num_trials)
count = collections.Counter(outcomes)
heads = count.get("head", 0)
tails = count.get("tail", 0)
freq_head = heads / num_trials
print(f"\n--- {num_trials} Coin Flips Simulation ---")
print(f"Heads count: {heads}, Tails count: {tails}")
print(f"Relative frequency of Heads = {freq_head:.4f}")
return outcomes, count
# Match R Task1: 10 flips
flip_coins(10)##
## --- 10 Coin Flips Simulation ---
## Heads count: 3, Tails count: 7
## Relative frequency of Heads = 0.3000
## (['head', 'tail', 'tail', 'tail', 'head', 'tail', 'tail', 'tail', 'tail', 'head'], Counter({'tail': 7, 'head': 3}))##
## --- 100 Coin Flips Simulation ---
## Heads count: 51, Tails count: 49
## Relative frequency of Heads = 0.5100
## (['head', 'tail', 'tail', 'head', 'head', 'head', 'head', 'tail', 'tail', 'head', 'tail', 'head', 'tail', 'tail', 'tail', 'tail', 'head', 'tail', 'tail', 'head', 'tail', 'head', 'head', 'tail', 'head', 'head', 'tail', 'tail', 'head', 'head', 'tail', 'head', 'head', 'head', 'tail', 'head', 'head', 'tail', 'head', 'head', 'head', 'head', 'head', 'tail', 'tail', 'tail', 'tail', 'tail', 'tail', 'tail', 'head', 'head', 'head', 'head', 'head', 'head', 'tail', 'head', 'head', 'head', 'tail', 'tail', 'head', 'tail', 'head', 'head', 'tail', 'tail', 'tail', 'head', 'head', 'tail', 'head', 'tail', 'tail', 'tail', 'head', 'tail', 'tail', 'head', 'tail', 'head', 'head', 'head', 'head', 'head', 'tail', 'tail', 'head', 'tail', 'head', 'tail', 'tail', 'tail', 'head', 'tail', 'tail', 'tail', 'tail', 'head'], Counter({'head': 51, 'tail': 49}))4.7 Example 7: Hypergeometric Probability for Defective Products
Problem Setup:
Total products: \(1000\)
Defective products: \(3\)
Normal (non-defective) products: \(1000 - 3 = 997\)
We randomly select \(10\) products without replacement. Compute two probabilities:
Probability that none of the 10 selected items are defective.
Probability that at least one selected item is defective.
4.7.1 Step 1: Total number of ways to pick 10 items from 1000
This is an unordered combination selection: \[ n(S) = \binom{1000}{10} \]
4.7.2 Part (1): Zero defective items in the 10 selected
To have zero defective units, we select all \(10\) units from the \(997\) normal products, and select \(0\) defective units from the \(3\) defective ones.
Number of favorable outcomes for event \(A_0\) (0 defectives): \[ n(A_0) = \binom{997}{10} \times \binom{3}{0} \] By classical probability formula: \[ P(A_0) = \frac{\dbinom{997}{10}\dbinom{3}{0}}{\dbinom{1000}{10}} \] Recall \(\dbinom{m}{0}=1\) for any integer \(m\ge0\), so \(\dbinom{3}{0}=1\), simplifying: \[ P(A_0) = \frac{\dbinom{997}{10}}{\dbinom{1000}{10}} \]
## [1] 0.97026954.7.3 Step-by-Step Numerical Simplification for \(P(A_0)\)
Expand binomial ratios to avoid huge factorial values: \[ \begin{aligned} \frac{\dbinom{997}{10}}{\dbinom{1000}{10}} &= \frac{\dfrac{997!}{10!\cdot 987!}}{\dfrac{1000!}{10!\cdot 990!}} \\ &= \frac{997! \cdot 990!}{987! \cdot 1000!} \\ &= \frac{990 \times 989 \times 988}{1000 \times 999 \times 998} \end{aligned} \] Compute step arithmetic:
\[ 990 \times 989 \times 988 = 967360680,\quad 1000 \times 999 \times 998 = 997002000 \] \[ P(\text{0 defective}) = \frac{967360680}{997002000} \approx \boldsymbol{0.9702695} \]
4.7.4 Part (2): At least one defective item selected
Let event \(B\) = at least one defective unit.
The complement of \(B\) is exactly event \(A_0\) (zero defective units). By complement probability rule: \[ P(B) = 1 - P(A_0) \] Formula written with binomial coefficients: \[ P(\text{at least 1 defective}) = 1 - \frac{\dbinom{997}{10}\dbinom{3}{0}}{\dbinom{1000}{10}} \]
## [1] 0.029730454.7.5 Numerical Calculation for Part (2)
\[ P(\text{at least 1 defective}) = 1 - 0.9702695 = \boldsymbol{0.0297305} \]
import math
def binom(n, k):
"""Binomial coefficient C(n,k) = n!/(k! (n-k)!)"""
if k < 0 or k > n:
return 0
return math.factorial(n) // (math.factorial(k) * math.factorial(n - k))
# Given parameters
total = 1000
defective_total = 3
normal_total = total - defective_total
sample_size = 10
# Part 1: Probability zero defective
fav_0_def = binom(normal_total, sample_size) * binom(defective_total, 0)
total_ways = binom(total, sample_size)
p0 = fav_0_def / total_ways
print("=== Part 1: Probability of 0 defective products ===")## === Part 1: Probability of 0 defective products ===## C(997,10) = 255578275196030318119016## C(3,0) = 1## C(1000,10) = 263409560461970212832400## P(0 defective) = (C(997,10)*C(3,0)) / C(1000,10) = 0.9702695# Part 2: Probability at least one defective (complement rule)
p_at_least_1 = 1 - p0
print("=== Part 2: Probability of at least 1 defective product ===")## === Part 2: Probability of at least 1 defective product ===## P(at least 1 defective) = 1 - P(0 defective) = 0.0297305# One-line Sage/R equivalent computation
sage_line = (binom(997,10)*binom(3,0))/binom(1000,10)
print(f"\nSage one-line calculation match value: {sage_line:.7f}")##
## Sage one-line calculation match value: 0.97026955 Conditional Probability
Conditional probability is a foundational concept in data analysis. It denotes the probability that event \(B\) occurs, given the prior condition that event \(A\) has already occurred. This conditional probability is written \(\boldsymbol{P(B \mid A)}\).
5.1 Formal Definition
\[ \boldsymbol{P(B \mid A) = \frac{P(A \cap B)}{P(A)} = \frac{P(B \cap A)}{P(A)}},\quad \text{valid only when } P(A) > 0 \] The notation \(P_A(B)\) shown in the diagram is an equivalent shorthand for \(P(B\mid A)\).
5.2 Product Rule Derived from Definition
Rearranging the conditional probability formula yields the product rule for joint probability: \[ \boldsymbol{P(A \cap B) = P(A)\,P(B \mid A) = P(B)\,P(A \mid B) = P(B \cap A)} \]
5.3 Generalized Product Rule for \(n\) Events \(A_1,A_2,\dots,A_n\)
\[ \begin{aligned} &P(A_1)\,P(A_2 \mid A_1)\,P(A_3 \mid A_1 \cap A_2)\cdots P(A_n \mid A_1 \cap A_2 \cap \dots \cap A_{n-1}) \\ =\ &P(A_1)\cdot \frac{P(A_1\cap A_2)}{P(A_1)} \cdot \frac{P(A_1\cap A_2\cap A_3)}{P(A_1\cap A_2)} \cdots \frac{P(A_1\cap A_2\cap\dots\cap A_n)}{P(A_1\cap A_2\cap\dots\cap A_{n-1})} \\ =\ &\boldsymbol{P(A_1 \cap A_2 \cap \dots \cap A_n)} \end{aligned} \]
5.4 Complement Partition Identity for Event \(A\)
For any event \(A\), the disjoint partition holds: \[ A = (A\cap B) \cup (A\cap B^c),\quad (A\cap B)\cap(A\cap B^c)=\emptyset \] By additivity of probability for disjoint sets: \[ P(A) = P(A\cap B) + P(A\cap B^c) \] Rearranged: \[ \boldsymbol{P(A\cap B) = P(A) - P(A\cap B^c)} \]
5.5 Example 8
Given values: \[ P(A) = \frac{21}{25},\quad P(A\cap B^c) = \frac15 \]
Goal: Compute \(P(B \mid A)\)
5.6 Step 1: Substitute partition identity into conditional formula
\[ P(B\mid A) = \frac{P(A\cap B)}{P(A)} = \frac{P(A) - P(A\cap B^c)}{P(A)} \]
5.7 tep 2: Substitute numerical fractions step-by-step
First convert \(\frac15\) to denominator \(25\) for uniform subtraction: \[ \frac15 = \frac{1\times 5}{5\times 5} = \frac{5}{25} \] Plug values into numerator: \[ P(A)-P(A\cap B^c) = \frac{21}{25} - \frac{5}{25} = \frac{21-5}{25} = \frac{16}{25} \]
5.8 Step 3: Divide numerator by \(P(A)\)
\[ P(B\mid A) = \frac{\;\dfrac{16}{25}\;}{\dfrac{21}{25}} \] The common denominator \(25\) cancels out: \[ P(B\mid A) = \boldsymbol{\frac{16}{21}} \]
# Given input probabilities
P_A = 21 / 25
P_A_intersect_Bcomp = 1 / 5
# Step 1: Compute P(A ∩ B) using partition identity
P_A_intersect_B = P_A - P_A_intersect_Bcomp
print(f"Step 1: P(A ∩ B) = P(A) - P(A ∩ B^c) = {P_A:.4f} - {P_A_intersect_Bcomp:.4f} = {P_A_intersect_B:.4f}")## Step 1: P(A ∩ B) = P(A) - P(A ∩ B^c) = 0.8400 - 0.2000 = 0.6400# Step 2: Conditional probability formula P(B|A) = P(A∩B)/P(A)
P_B_given_A = P_A_intersect_B / P_A
print(f"Step 2: P(B|A) = P(A∩B) / P(A) = {P_A_intersect_B:.4f} / {P_A:.4f} = {P_B_given_A:.4f}")## Step 2: P(B|A) = P(A∩B) / P(A) = 0.6400 / 0.8400 = 0.7619# Exact fractional form output
from fractions import Fraction
frac_PA = Fraction(21,25)
frac_PA_Bc = Fraction(1,5)
frac_PA_B = frac_PA - frac_PA_Bc
frac_result = frac_PA_B / frac_PA
print(f"\nExact fractional answer: P(B|A) = {frac_result}")##
## Exact fractional answer: P(B|A) = 16/216 1Bayes’ Theorem
Bayes’ theorem calculates the probability of an event by incorporating prior knowledge of related conditional conditions.
This tool is vital for mathematical decision-making under uncertainty, and it is widely used to value invisible, intangible assets such as information.
6.1 Key Terminology Definitions
Prior Probability: \(P(A)\) — probability of event \(A\) calculated before observing new data or evidence.
Posterior Probability: \(P(A\mid B)\) — revised, updated probability of event \(A\) after new evidence/event \(B\) is observed to occur. In \(P(A\mid B)\), event \(B\) is the observed condition, and \(P(A\mid B)\) updates our belief about \(A\) after seeing \(B\).
Bayes’ Theorem derives posterior probabilities by combining known prior probabilities and conditional likelihoods from observed events.
6.2 Partition of Sample Space and Law of Total Probability
Let sample space \(S\) be partitioned into disjoint events \(A_1,A_2,\dots,A_n\): \[ A_i \cap A_j = \emptyset \quad (i\neq j), \qquad S = A_1 \cup A_2 \cup \dots \cup A_n \] For any arbitrary event \(B \subseteq S\): \[ B = S \cap B = \big(A_1\cup A_2\cup\dots\cup A_n\big)\cap B = (A_1\cap B)\cup(A_2\cap B)\cup\dots\cup(A_n\cap B) \] All sets \(A_i\cap B\) are mutually exclusive, so by finite additivity of probability: \[ P(B) = P(A_1\cap B)+P(A_2\cap B)+\dots+P(A_n\cap B) \] Apply the probability product rule \(P(A_i\cap B)=P(A_i)\,P(B\mid A_i)\) to get the : \[ \boldsymbol{P(B) = \sum_{i=1}^n P(A_i)\,P(B\mid A_i)} = P(A_1)P(B\mid A_1)+P(A_2)P(B\mid A_2)+\dots+P(A_n)P(B\mid A_n) \]
6.3 Bayes’ Theorem Formula
From conditional probability definition: \[ P(A_j \mid B) = \frac{P(A_j \cap B)}{P(B)} \] Substitute product rule \(P(A_j\cap B)=P(A_j)P(B\mid A_j)\) and total probability for \(P(B)\): \[ \boldsymbol{ P(A_j \mid B) = \frac{P(A_j)\,P(B\mid A_j)} {\displaystyle\sum_{i=1}^n P(A_i)\,P(B\mid A_i)} } \]
\(P(A_j)\): prior probability of partition event \(A_j\)
\(P(A_j\mid B)\): posterior probability of \(A_j\) given observed event \(B\)
6.4 Example 9
Problem Setup:
Three factory machines \(A,B,C\) produce \(50\%,\;30\%,\;20\%\) of total output respectively.
Defect rates: \(P(\text{Defect}\mid A)=0.04,\ P(\text{Defect}\mid B)=0.03,\ P(\text{Defect}\mid C)=0.02\).
Find total probability a randomly selected product is defective (\(P(X)\), where \(X=\) defective item).
Find posterior probability a defective product was made by machine \(C\) (\(P(C\mid X)\)).
6.4.1 Step 1: Define Prior Probabilities
\[ P(A)=0.5,\quad P(B)=0.3,\quad P(C)=0.2 \] Conditional defect likelihoods: \[ P(X\mid A)=0.04,\quad P(X\mid B)=0.03,\quad P(X\mid C)=0.02 \]
6.4.2 Step 2: Law of Total Probability for \(P(X)\)
\[ \begin{aligned} P(X) &= P(A)P(X\mid A)+P(B)P(X\mid B)+P(C)P(X\mid C) \\ &= (0.5 \times 0.04) + (0.3 \times 0.03) + (0.2 \times 0.02) \\ &= 0.02 + 0.009 + 0.004 \\ &= \boldsymbol{0.033} \end{aligned} \]
6.4.3 Step 3: Bayes’ Theorem for Posterior \(P(C\mid X)\)
\[ \begin{aligned} P(C\mid X) &= \frac{P(C)\,P(X\mid C)}{P(A)P(X\mid A)+P(B)P(X\mid B)+P(C)P(X\mid C)} \\ &= \frac{0.2 \times 0.02}{0.033} \\ &= \frac{0.004}{0.033} = \boldsymbol{\frac{4}{33}} \approx 0.1212 \end{aligned} \]
# Use exact fractional inputs to avoid float → Fraction conversion errors
from fractions import Fraction
# 1. Prior probabilities as exact fractions
P_A = Fraction(50, 100) # 0.5
P_B = Fraction(30, 100) # 0.3
P_C = Fraction(20, 100) # 0.2
# 2. Conditional defect rates as exact fractions
P_X_given_A = Fraction(4, 100) # 0.04
P_X_given_B = Fraction(3, 100) # 0.03
P_X_given_C = Fraction(2, 100) # 0.02
# Step 1: Law of Total Probability for P(X)
term_A = P_A * P_X_given_A
term_B = P_B * P_X_given_B
term_C = P_C * P_X_given_C
P_X = term_A + term_B + term_C
print("=== Step 1: Total Probability of Defective Product P(X) ===")## === Step 1: Total Probability of Defective Product P(X) ===## P(A)·P(X|A) = 0.5 × 0.04 = 0.02## P(B)·P(X|B) = 0.3 × 0.03 = 0.009## P(C)·P(X|C) = 0.2 × 0.02 = 0.004## P(X) = 0.02 + 0.009 + 0.004 = 0.0330# Step 2: Bayes' Theorem Posterior P(C|X)
P_C_given_X = term_C / P_X
frac_result = P_C_given_X # Already exact Fraction object
print("=== Step 2: Bayes' Theorem P(C|X) ===")## === Step 2: Bayes' Theorem P(C|X) ===print(f"P(C|X) = [P(C)·P(X|C)] / P(X) = {float(term_C)} / {float(P_X):.4f} = {float(P_C_given_X):.4f}")## P(C|X) = [P(C)·P(X|C)] / P(X) = 0.004 / 0.0330 = 0.1212## Exact fractional value = 4/337 Random Variables
Consider the experiment of flipping two fair coins. The sample space of all distinct outcomes is: \[ S = \{\,(\text{Head},\text{Head}),\; (\text{Head},\text{Tail}),\; (\text{Tail},\text{Head}),\; (\text{Tail},\text{Tail})\,\} \] For a fair coin flip, every outcome in this sample space is equally likely, so the probability of each single outcome equals \(\boldsymbol{\dfrac14}\).
Define \(X\) as the count of tails observed in the two coin tosses. The random variable \(X\) maps each sample outcome to a real numerical value:
Outcome \((\text{Head},\text{Head}) \mapsto X = 0\) tails
Outcomes \((\text{Head},\text{Tail}),\; (\text{Tail},\text{Head}) \mapsto X = 1\) tail
Outcome \((\text{Tail},\text{Tail}) \mapsto X = 2\) tails
This mapping function \(X\) is defined as a random variable.
7.1 Concept Definition of a Random Variable
A random variable behaves analogously to a variable in computer programming, except its realized value is determined by probabilistic chance rather than fixed assignment.
Formally, a random variable is a function that maps every outcome (sample point) from the sample space \(S\) to a real number on the real line \(\mathbb{R}\).
Using random variables converts qualitative probabilistic events into quantitative numerical values, which simplifies calculation, comparison, and statistical analysis of random experiments.
Notation convention:
Uppercase letters (e.g., \(X,Y,Z\)): denote the random variable function itself
Lowercase letters (e.g., \(x,y,z\)): denote specific numerical values the random variable may take
7.1.1 Step-by-Step Probability Mass Calculation for \(X\) (Number of Tails in 2 Coin Flips)
Total equally-likely sample outcomes: \(n(S)=4\), each with probability \(\frac14\).7.1.2 Verification of Total Probability Sum to 1
All mutually exclusive possible values of \(X\) cover the full sample space: \[ P(X=0)+P(X=1)+P(X=2) = \frac14 + \frac12 + \frac14 = \frac{1+2+1}{4} = \frac44 = \boldsymbol{1} \]
# Sample space for two coin flips
sample_space = [("H","H"), ("H","T"), ("T","H"), ("T","T")]
total_outcomes = len(sample_space)
# Define random variable X: count number of tails per outcome
def count_tails(outcome):
return outcome.count("T")
# Calculate probability mass for each possible X value (0,1,2)
pmf = {0:0, 1:0, 2:0}
for outcome in sample_space:
x_val = count_tails(outcome)
pmf[x_val] += 1
# Convert counts to probabilities
for x in pmf:
pmf[x] = pmf[x] / total_outcomes
# Print step-by-step breakdown
print("=== Random Variable X = Number of Tails in 2 Coin Flips ===")## === Random Variable X = Number of Tails in 2 Coin Flips ===## Total sample outcomes = 4for x in sorted(pmf.keys()):
count = pmf[x] * total_outcomes
prob = pmf[x]
print(f"X = {x}: {count} favorable outcomes, P(X={x}) = {count}/{total_outcomes} = {prob:.2f}")## X = 0: 1.0 favorable outcomes, P(X=0) = 1.0/4 = 0.25
## X = 1: 2.0 favorable outcomes, P(X=1) = 2.0/4 = 0.50
## X = 2: 1.0 favorable outcomes, P(X=2) = 1.0/4 = 0.25# Verify total probability sums to 1
total_prob = sum(pmf.values())
print(f"\nTotal sum of all probabilities = {total_prob}")##
## Total sum of all probabilities = 1.0# 2. Monte Carlo Simulation (empirical test of the random variable distribution)
import random
def flip_two_coins():
coin1 = random.choice(["H","T"])
coin2 = random.choice(["H","T"])
return (coin1, coin2)
simulation_trials = 10000
sim_counts = {0:0,1:0,2:0}
for _ in range(simulation_trials):
res = flip_two_coins()
sim_x = count_tails(res)
sim_counts[sim_x] += 1
print(f"\n=== Monte Carlo Simulation ({simulation_trials} trials) ===")##
## === Monte Carlo Simulation (10000 trials) ===for x in sorted(sim_counts.keys()):
sim_prob = sim_counts[x] / simulation_trials
print(f"Simulated P(X={x}) ≈ {sim_prob:.4f}")## Simulated P(X=0) ≈ 0.2415
## Simulated P(X=1) ≈ 0.5035
## Simulated P(X=2) ≈ 0.25508 Discrete Probability Distributions
A discrete random variable \(X\) is a random variable that may only take a countable set of distinct real values \(x_1,\,x_2,\,\dots,\,x_n\).
A discrete probability distribution fully specifies the probability \(P(X=x_i)\) for every possible value \(x_i\) of the discrete random variable \(X\).
8.1 Tabular Format for Discrete Distribution
\[ \begin{array}{l|cccc|c} X & x_1 & x_2 & \dots & x_n & \textrm{Sum} \\ \hline \textrm{Probability} & P(X=x_1) & P(X=x_2) & \dots & P(X=x_n) & 1 \end{array} \]
8.2 Illustrative Example: Two Coin Tosses (Count Tails \(X\))
Experiment: Flip two fair coins simultaneously. \(X\) = number of tails observed.
Sample space: \(S=\{(H,H),(H,T),(T,H),(T,T)\}\), each outcome equally likely with probability \(\tfrac14\).
Step-by-step mapping and probability calculation:8.3 Probability Mass Function (PMF) Definition
The function \(f(x)\) that assigns the probability value \(P(X=x_i)\) to each possible discrete value \(x_i\) of \(X\) is called the of \(X\): \[ f(x) = \begin{cases} P(X=x_i) & \text{for } x = x_1,\,x_2,\,\dots,\,x_n \\ 0 & \text{for all other real } x \end{cases} \]
8.3.1 Three Fundamental PMF Properties
8.3.2 Verification for Two-Coin Example PMF
PMF values: \(f(0)=\tfrac14,\ f(1)=\tfrac12,\ f(2)=\tfrac14\)
Bounds check: \(0<\tfrac14<1,\ 0<\tfrac12<1,\ 0<\tfrac14<1\) (satisfies property 1)
Total sum: \[ f(0)+f(1)+f(2) = \frac14+\frac12+\frac14 = \frac{1+2+1}{4} = \frac44 = \boldsymbol{1} \]
Example interval calculation: \(P(0\le X \le 1)\) \[ P(0\le X \le 1) = f(0)+f(1) = \frac14+\frac12 = \frac34 \]
# Discrete random variable X: number of tails in two coin flips
# Define possible x values and their pmf f(x)
x_values = [0, 1, 2]
pmf_vals = [1/4, 1/2, 1/4]
# Store as dictionary for easy lookup
pmf = dict(zip(x_values, pmf_vals))
print("=== Discrete PMF for X = Number of Tails (2 coin tosses) ===")## === Discrete PMF for X = Number of Tails (2 coin tosses) ===## f(0) = P(X=0) = 0.25
## f(1) = P(X=1) = 0.50
## f(2) = P(X=2) = 0.25# Property 1: Check 0 ≤ f(x) ≤ 1 for all x
print("\n--- Property 1 Check (0 ≤ f(x) ≤ 1) ---")##
## --- Property 1 Check (0 ≤ f(x) ≤ 1) ---prop1_ok = True
for x, fx in pmf.items():
if not (0 <= fx <= 1):
prop1_ok = False
print(f"ERROR: f({x}) = {fx} out of bounds")
if prop1_ok:
print("All pmf values satisfy 0 ≤ f(x) ≤ 1")## All pmf values satisfy 0 ≤ f(x) ≤ 1# Property 2: Sum f(x) = 1
total_mass = sum(pmf_vals)
print(f"\n--- Property 2 Check (Total sum = 1) ---")##
## --- Property 2 Check (Total sum = 1) ---## Sum f(x) = 1.0# Property3: Compute interval probability P(a ≤ X ≤ b)
def prob_interval(a, b, pmf_dict):
total = 0.0
for x, fx in pmf_dict.items():
if a <= x <= b:
total += fx
return total
p_0to1 = prob_interval(0, 1, pmf)
print(f"\n--- Property3 Example: P(0 ≤ X ≤ 1) = {p_0to1:.2f}")##
## --- Property3 Example: P(0 ≤ X ≤ 1) = 0.75# Part2: Monte Carlo Simulation to approximate PMF
import random
def flip_two():
c1 = random.choice(["H","T"])
c2 = random.choice(["H","T"])
return (c1,c2)
def count_tails(outcome):
return outcome.count("T")
trials = 20000
sim_counts = {0:0,1:0,2:0}
for _ in range(trials):
res = flip_two()
x_sim = count_tails(res)
sim_counts[x_sim] +=1
print(f"\n=== Monte Carlo Simulation ({trials} trials) ===")##
## === Monte Carlo Simulation (20000 trials) ===for x in sorted(sim_counts.keys()):
sim_prob = sim_counts[x] / trials
print(f"Simulated f({x}) ≈ {sim_prob:.4f}, Theoretical f({x}) = {pmf[x]:.2f}")## Simulated f(0) ≈ 0.2402, Theoretical f(0) = 0.25
## Simulated f(1) ≈ 0.5049, Theoretical f(1) = 0.50
## Simulated f(2) ≈ 0.2549, Theoretical f(2) = 0.259 1Continuous Probability Distributions
A continuous random variable \(X\) is a random variable that can take an uncountably infinite set of real values.
For any continuous random variable, the probability that \(X\) equals a single exact point value \(x\) is always zero: \[ \boldsymbol{P(X = x) = 0} \] Because point probabilities are zero, the discrete probability mass function (pmf) cannot describe a continuous distribution. Instead we introduce the probability density function (pdf), denoted \(f(x)\), to model continuous probability behavior.
The pdf \(f(x)\) is the continuous analog of the discrete pmf. A function \(f(x)\) qualifies as a valid probability density function for continuous random variable \(X\) if it satisfies three core properties:
9.1 Graphical Interpretation of Interval Probability
Probability \(P(a\le X\le b)\) corresponds geometrically to the area under the pdf curve \(y=f(x)\) between vertical lines \(x=a\) and \(x=b\).9.2 Note: Etymology of Density in PDF
We interpret probability as mass, and interval length as a one-dimensional volume:
Ratio: \(\dfrac{\text{Probability}}{\text{Interval Length}} = \dfrac{\text{Mass}}{\text{Volume}}\)
The ratio \(\frac{\text{mass}}{\text{volume}}\) is the standard definition of physical density.
Rearranged relation: \[ \left(\frac{\text{Probability}}{\text{Interval Length}}\right) \times (\text{Interval Length}) = \text{Probability} \] Multiplying density (probability per unit length) by interval length yields total probability for that segment. This relationship gives the name probability density function.
9.3 Step Verification Example (Uniform Continuous Distribution Test)
Take uniform pdf over \([0,2]\): \[ f(x) = \begin{cases} \frac12 & 0 \le x \le 2 \\ 0 & \text{otherwise} \end{cases} \]
Property 1 check: \(f(x)\ge0\) for all real \(x\) (\(\tfrac12>0\) on support, \(0\) outside)
Property 2 total integral: \[ \int_{-\infty}^{\infty}f(x)dx = \int_0^2 \frac12 dx = \frac12 \big[x\big]_0^2 = \frac12(2-0) = \boldsymbol{1} \]
Interval probability example: \(P(0.5 \le X \le 1.5)\) \[ P(0.5\le X\le1.5) = \int_{0.5}^{1.5}\frac12 dx = \frac12(1.5-0.5) = \boldsymbol{0.5} \] Also confirm \(P(X=1)=0\) (single point integral \(\displaystyle \int_1^1 \tfrac12 dx =0\))
import sympy as sp
import scipy.integrate as spi
import numpy as np
# Symbolic variable
x = sp.Symbol('x', real=True)
# Define uniform pdf f(x) = 1/2 for 0<=x<=2, else 0
def f_sym(x_val):
if 0 <= x_val <= 2:
return sp.Rational(1,2)
else:
return 0
# Convert to piecewise sympy expression
f = sp.Piecewise((sp.Rational(1,2), (x >= 0) & (x <= 2)), (0, True))
print("=== Step 1: Verify PDF Property 1 (f(x) ≥ 0 for all real x) ===")## === Step 1: Verify PDF Property 1 (f(x) ≥ 0 for all real x) ===# Test sample points inside and outside support
test_points = [-1, 0, 1, 2, 3]
for xi in test_points:
fx_val = float(f.subs(x, xi))
print(f"f({xi}) = {fx_val}, non-negative? {fx_val >= 0}")## f(-1) = 0.0, non-negative? True
## f(0) = 0.5, non-negative? True
## f(1) = 0.5, non-negative? True
## f(2) = 0.5, non-negative? True
## f(3) = 0.0, non-negative? True# FIX 1: Remove ALL Unicode ∞, use plain ASCII "inf" text only
print("\n=== Step 2: Verify PDF Property 2 (Integral from -inf to inf = 1) ===")##
## === Step 2: Verify PDF Property 2 (Integral from -inf to inf = 1) ===total_integral = sp.integrate(f, (x, -sp.oo, sp.oo))
print(f"Integral from -inf to inf of f(x) dx = {total_integral}")## Integral from -inf to inf of f(x) dx = 1##
## === Step3: Verify Interval Probability P(0.5 ≤ X ≤1.5) ===interval_int = sp.integrate(f, (x, 0.5, 1.5))
print(f"P(0.5 ≤ X ≤1.5) = Integral from 0.5 to 1.5 of f(x) dx = {float(interval_int)}")## P(0.5 ≤ X ≤1.5) = Integral from 0.5 to 1.5 of f(x) dx = 0.5# Verify single point probability P(X=1)=0
point_int = sp.integrate(f, (x, 1, 1))
print(f"\nSingle point integral P(X=1) = Integral from 1 to 1 of f(x) dx = {point_int}")##
## Single point integral P(X=1) = Integral from 1 to 1 of f(x) dx = 0# 2. Numerical Integration for General Continuous PDFs
def pdf_uniform(x_num):
return 0.5 if (0 <= x_num <=2) else 0
num_total, err_total = spi.quad(pdf_uniform, -np.inf, np.inf)
num_interval, err_int = spi.quad(pdf_uniform, 0.5, 1.5)
print("\n=== Numerical Integration Confirmation ===")##
## === Numerical Integration Confirmation ===## Numerical total integral = 1.0000## Numerical P(0.5 ≤ X ≤1.5) = 0.5000# 3. Plot PDF curve and shaded interval area
import matplotlib.pyplot as plt
xs = np.linspace(-0.5, 2.5, 1000)
ys = np.array([pdf_uniform(t) for t in xs])
plt.figure(figsize=(8,4))## <Figure size 800x400 with 0 Axes># FIX 2: Replace LaTeX \frac with plain ASCII text labels to avoid parse error
plt.plot(xs, ys, color='darkblue', linewidth=2, label='f(x)=1/2, 0 ≤ x ≤ 2')## [<matplotlib.lines.Line2D object at 0x000002663F5A3350>]# Shade 0.5 to1.5
x_fill = np.linspace(0.5,1.5,500)
y_fill = np.array([pdf_uniform(t) for t in x_fill])
plt.fill_between(x_fill, y_fill, color='cyan', alpha=0.4, label='P(0.5 ≤ X ≤ 1.5)')## <matplotlib.collections.FillBetweenPolyCollection object at 0x000002663F4B2F60>## <matplotlib.lines.Line2D object at 0x000002663F63B9B0>## <matplotlib.lines.Line2D object at 0x000002663F7699A0>## Text(0.5, 0, 'x')## Text(0, 0.5, 'f(x)')## <matplotlib.legend.Legend object at 0x000002663F63C7D0>## Text(0.5, 1.0, 'Uniform Continuous Probability Density Function')