5.4 Avansert kombinatorikk

Stikkprøven som avgjør hele partiet

På et mottakslager står en innkjøpsansvarlig foran et parti på 20 elektronikkenheter fra en ny leverandør. Å teste alle ville tatt en hel dag, så bedriften har en fast rutine: trekk 5 tilfeldige enheter, og send hele partiet i retur hvis noen av dem er defekte. Men hvor god er egentlig denne rutinen? Hvis 3 av de 20 enhetene faktisk er defekte — hvor sannsynlig er det at stikkprøven avslører det?

Spørsmålet har en presis matematisk form. Vi har en populasjon med to kategorier (defekt/ok), vi trekker et utvalg uten tilbakelegging — en enhet som er plukket ut, legges ikke tilbake — og vi spør hvor mange av den ene kategorien vi får. Akkurat denne situasjonen beskrives av den hypergeometriske fordelingen.

Mønsteret går igjen overalt i samfunnet: Mattilsynet som trekker matvarer fra et vareparti, en valgkomité som trekker et utvalg fra et medlemsregister med to fløyer, en biolog som fanger inn fisk fra en merket bestand. Felles for alle er urnemodellen: en «urne» med kuler i to farger, og en hånd som trekker uten å legge tilbake. I dette kapittelet setter vi formelen på plass, regner på både kuler og kvalitetskontroll, og lærer det viktigste trikset av alle: komplementregelen for «minst én».

Formelen — telle gunstige delt på mulige

La oss bygge formelen med kombinatorikken fra tidligere. Vi innfører tre tall: $N$ er totalt antall objekter, $M$ er antallet med den egenskapen vi ser etter, og $n$ er antallet vi trekker. Den stokastiske variabelen $X$ teller hvor mange med egenskapen som havner i utvalget.

Hvor mange utvalg gir nøyaktig $k$ «spesielle»? Vi må velge $k$ av de $M$ spesielle — det kan gjøres på $\binom{M}{k}$ måter — og de resterende $n-k$ fra de $N-M$ vanlige, på $\binom{N-M}{n-k}$ måter. Multiplikasjonsprinsippet ganger disse sammen. Totalt antall mulige utvalg er $\binom{N}{n}$, og siden alle er like sannsynlige:

$$P(X = k) = \frac{\binom{M}{k} \cdot \binom{N-M}{n-k}}{\binom{N}{n}}, \qquad k = 0, 1, \ldots, \min(n, M)$$

Prøv den på en klassisk urne: 12 kuler, hvorav 5 røde og 7 blå, og vi trekker 4. Sannsynligheten for nøyaktig 2 røde blir

$$P(X = 2) = \frac{\binom{5}{2} \cdot \binom{7}{2}}{\binom{12}{4}} = \frac{10 \cdot 21}{495} = \frac{210}{495} \approx 0{,}424$$

altså rundt 42 %. Fordelingen har også en bemerkelsesverdig enkel forventningsverdi: $\displaystyle E(X) = n \cdot \frac{M}{N}$ — du forventer samme andel spesielle i utvalget som i populasjonen. Variansen er $\displaystyle \text{Var}(X) = n \cdot \frac{M}{N} \cdot \frac{N-M}{N} \cdot \frac{N-n}{N-1}$, der den siste faktoren krymper spredningen fordi trekningene uten tilbakelegging henger sammen.

Kvalitetskontrollen — og «minst én»-trikset

Tilbake til mottakslageret. Partiet har $N = 20$ enheter, $M = 3$ av dem er defekte, og vi trekker $n = 5$. Rutinen slår alarm hvis vi finner minst én defekt — så vi trenger $P(X \geq 1)$.

Her kunne vi summere $P(X=1) + P(X=2) + P(X=3)$, men det finnes en raskere vei. Hendelsen «minst én defekt» er komplementet til «ingen defekte», så

$$P(X \geq 1) = 1 - P(X = 0)$$

Vi regner ut den ene sannsynligheten vi trenger — at alle 5 trukne er feilfrie:

$$P(X = 0) = \frac{\binom{3}{0} \cdot \binom{17}{5}}{\binom{20}{5}} = \frac{1 \cdot 6188}{15\,504} \approx 0{,}399$$

Dermed er $P(X \geq 1) = 1 - 0{,}399 = 0{,}601$. Stikkprøven avslører altså et slikt parti i bare ca. 60 % av tilfellene — fire av ti dårlige partier slipper gjennom! For innkjøpsansvarlig er dette gull verdt å vite: vil bedriften ha bedre beskyttelse, må stikkprøven økes, og formelen lar oss regne ut nøyaktig hvor mye.

Dette er hypergeometrisk fordeling i sitt rette element: kvalitetskontroll og stikkprøver, der populasjonen er endelig og hvert trekk endrer det som er igjen. Legg merke til kontrasten med trekning med tilbakelegging, der sannsynligheten er lik i hvert trekk — den situasjonen får sin egen fordeling (den binomiske) i neste hovedkapittel. Huskeregelen er enkel: endelig populasjon og uten tilbakelegging → hypergeometrisk; konstant sannsynlighet i hvert forsøk → binomisk.

Oppsummering: urnemodellen i arbeidslivet

Stikkprøverutinen fra mottakslageret fikk sin dom: med 5 av 20 enheter kontrollert oppdages et parti med 3 defekte bare i ca. 60 % av tilfellene. Verktøyet som ga svaret, var den hypergeometriske fordelingen — modellen for trekning uten tilbakelegging fra en populasjon med to typer.

Oppskriften er ren kombinatorikk. Med $N$ objekter totalt, $M$ spesielle og et utvalg på $n$, er sannsynligheten for nøyaktig $k$ spesielle

$$P(X = k) = \frac{\binom{M}{k} \cdot \binom{N-M}{n-k}}{\binom{N}{n}}$$

— velg de spesielle med én binomialkoeffisient, resten med en annen, og del på alle mulige utvalg. Forventningsverdien er like intuitiv som den er enkel: $\displaystyle E(X) = n \cdot \frac{M}{N}$, utvalget speiler i gjennomsnitt andelen i populasjonen.

To arbeidsvaner er verdt å ta med videre. For det første: spørsmål om «minst én» løses nesten alltid raskest med komplementet, $P(X \geq 1) = 1 - P(X = 0)$. For det andre: sjekk alltid om trekningen skjer med eller uten tilbakelegging. Uten tilbakelegging er trekkene avhengige og fordelingen hypergeometrisk; med tilbakelegging (eller konstant sannsynlighet) er vi i binomisk territorium — fordelingen vi skal utforske grundig i neste hovedkapittel. Urnemodellen du nå behersker, er den samme enten «kulene» er elektronikkenheter på et lager, matvarer hos Mattilsynet eller respondenter i et register.