Statistikk og Simulering

Statistikk

Veke 5. Feilsannsyn og binomialfordeling

3.4. Veke 5. Feilsannsyn og binomialfordeling

  3.4.1 Lesestoff
  3.4.2 Onsdag (førelesing)
  Bernoulli-fordelinga
  Binomialfordelinga
  Lineærkombinasjonar
  PDF og CDF
  3.4.3 Utvida døme: Kommunikasjonssystem
  Ein kommunikasjonsmodell eller to
  3.4.4 Fredag (rekneøving)

Målet denne veka er å forstå binomialfordelinga, og korleis ho kan brukast til å modellera feilsannsyn i t.d. kommunikasjonssystem.

Merk at me berre går gjennom nokre få fordelingar i denne omgangen. Foruten den uniforme fordelinga ser me på éi diskret fordeling denne veka – binomialfordelinga – og éi kontinuerleg fordeling – normalfordelinga – neste veke. Der er fleire fordelingar i kapittel 7–8, og me vil koma tilbake til nokre av dei seinare.

Ein kan sjå statistikkpensumet som to delar som på mange måtar er uavhengige av kvarandre.

Sannsynsfordelingar (eller modellar)
Metodar (estimering, hypotesetest, regresjon)

Metodane er det viktig å læra og forstå. Det krev litt tid og modning å læra å tolka resultata rett. Ein må ha ei fordeling å bruka metoden på, men ein må ofte slå opp nye fordelingar når ein møtar nye problem i praksis. Det er derimot enklare enn å læra metodane. Difor går me i gang med metodane so snart me har nokre få fordelingar å bruka dei på.

3.4.1. Lesestoff

Les 7 (Repetisjon) Frå Frisvold og Moe: Kapittel 7.1 (med intro)

Les 8 (Binomialfordelinga) Frå Frisvold og Moe: Kapittel 7.4–7.5

3.4.2. Onsdag (førelesing)

Bernoulli-fordelinga

Døme 2 Mobiltelefonen sender éi datapakke til basestasjonen. Der er alltid støy på lina, og det mottekne signalet er aldri heilt identisk med det som vart sendt, men systemet bruker feilrettande kodar slik at basestasjonen sannsynlegvis kan rekonstruera pakka.

Der er like fullt to moglege utfall: korrekt overføring eller feil. Me kan tala om eit feilsannsyn $π$ .

Dette er eit døme på eit Bernoulli-forsøk.

Andre døme:

Mynt og kron
Du sender éin bit på ein kommunikasjonskanal. Bitten vert overført anten rett eller feil.
Produksjonsfeil. Kvar eining produsert har eit sannsyn $π$ for å vera defekt.

Oppgåve 3.41 Lat 0 og 1 vera utfalla i ei Bernoulli-fordeling med punktsannsyn $π = P (X = 1)$ . Finn $μ$ og $σ^{2}$ .

Binomialfordelinga

Døme 3 I løpet av ei telefonsamtale må mobiltelefonen senda $N$ pakker til basestasjonen. Lat oss gå ut frå at pakkene representerer uavhengige Bernoulli-forsøk med sannsyn $π$ for feil. Lat $Y$ vera talet på feil over $N$ pakker.

Den stokastiske variabelen $Y$ er no binomialfordelt med $N$ forsøk og punktsannsyn $π$ .

Andre døme

$N$ myntkast
Produksjonsfeil. Kor mange einingar må kasserast når fabrikken lagar $N$ stk.?
Kor mange bitfeil får du når du sender eit ord med $N$ bits over ein kanal (t.d. BSC $(p)$ )

Oppgåve 3.42 Du kastar mynt og kron fire gongar. Kva er sannsynet for å få mynt eksakt ein gong (og kron ein gong)?

Oppgåve 3.43 Du kastar mynt og kron fire gongar. Kva er sannsynet for å få mynt eksakt to gongar (og kron to gongar)?

Oppgåve 3.44 Du kastar mynt og kron $n$ gongar. Kva er sannsynet for å få mynt eksakt $k$ gongar?

Lineærkombinasjonar

Lat

X = X_{1} + X_{2} + \dots + X_{n}

vera summen av $n$ uavhengige stokastiske variablar. Forventingsverdien er då gjeve som

E (X) = E (X_{1}) + E (X_{2}) + \dots + E (X_{n}) .

Lat

X = X_{1} + X_{2} + \dots + X_{n}

vera summen av $n$ uavhengige stokastiske variablar. Variansen er då gjeve som

var (X) = var (X_{1}) + var (X_{2}) + \dots + var (X_{n}) .

Lat $X = b \cdot X_{1}$ vera resultatet av å observera $X_{1}$ éin gong og ganga med skalaren $b$ . Forventingsverdien er då gjeve som

E (X) = b E (X_{1}) .

Lat $X = b \cdot X_{1}$ vera resultatet av å observera $X_{1}$ éin gong og ganga med skalaren $b$ . Variansen er då gjeve som

var (X) = b^{2} var (X_{1}) .

Når me sender eit

n

-bits ord over BSC

(p)

er feiltalet

X \sim B (n, p)

binomialfordelt med

n

forsøk og suksessannsyn

p

. Merk at

X

er summen av

n

uavhengige forsøk,

X = X_{1} + X_{2} + \dots + X_{n},

der kvar $X_{i}$ er fordelt som $Z \sim B (1, p)$ i oppgåva over. Då kan me bruka desse to satsane.

Oppgåve 3.45 Tenk deg at du sender eit $n$ -bits ord over BSC $(p)$ . Lat $X \sim B (n, p)$ vera talet på bitfeil.

1.: Kva er forventingsverdien (populasjonsgjennomsnittet) $E (X)$ ?
2.: Kva er variansen $var (X)$ ?

Bruk resultatet ditt frå oppgåve 3.56 og dei to satsane over for å koma fram til svaret.

Oppgåve 3.46 Lat $X \sim B (n, p)$ vera fordelt som i oppgåva over. Finn standardavviket $σ$ for $X$ . Bruk svaret frå oppgåva over.

Somme tider ser me på $Y^{'} = Y ∕ N \in [0, 1]$ heller enn på $Y$ .

PDF og CDF For store verdiar av $N$ vert utfallsrommet so stort at ein i praksis reknar som om $Y$ er kontinuerleg.

Det vert òg upraktisk å rekna ut punktsannsyn, og me går over til å bruka CDF og tabellar.

3.4.3. Utvida døme: Kommunikasjonssystem

Ein kommunikasjonsmodell eller to

pict

Figur 1: Communication system.

All digital kommunikasjon er offer for støy. Dvs. at det mottekne signalet ikkje er identisk med det sendte signalet. Kodeteori er løysinga på dette problemet. Ved å koda meldingane er det som regel råd å finna (estimera) den korrekte bodskapen, sjølv om der er feil i overføringa.

Figuren viser dette. Meldinga vert koda som kodeordet $\vec{c}$ før han vert sendt på kanalen. Det mottekne signalet $\vec{r}$ som kjem ut frå kanalen er sjelden identisk med $\vec{c}$ , men når me dekodar so får me eit estimat $\hat{\vec{m}}$ for den opprinnelege meldinga $\vec{m}$ . Det store spørsmålet, som me ofte treng statistikk for å svara på, kva er feilsannsynet $P (\vec{m} \neq \hat{\vec{m}})$ ?

Definisjon 8 (Binary Symmetric Channel)

pict

Figur 2: The binary symmetric channel.

Mange kanalar vert modellert additivt. Dvs. at det mottekne signalet $\vec{r}$ er summen av det sendte signale $\vec{s}$ og ein feilvektor $\vec{e}$ .

Den binærsymmetriske kanalen (BSC), dvs. at $\vec{s}$ , $\vec{r}$ , og $\vec{e}$ er binære (vektorar over $GF (2) = {0, 1}$ ), og addisjon er modulo 2. På BSC er feilvektoren $\vec{e}$ generert tilfeldig, med uavhengige bits, der kvar bit $X$ har sannsyn $P (X = 1) = p$ for feil, og $P (X = 0) = 1 - p$ for korrekt overføring. Me skriv gjerne BSC $(p)$ for ein binærsymmetrisk kanal med feilsannsyn $p$ .

Figuren viser dette skjematisk. PRNG står for «Pseudo-Random Number Generator», dvs. slumptalsgenerator.

Døme 4 Når me sender éin bit over BSC har me to moglege utfall: feil eller ikkje feil. Alle bits som vert sende er uavhengige av kvarandre.

Dette er eit døme på eit Bernoulli-forsøk.

Døme 5 Mynt og kron har mykje til felles med dømet over. Der er to utfall mynt eller kron, og kasta er uavhengige av kvarandre. Dette er òg eit Bernoulli-forsøk.

Sjølv om mynten er skeiv, og eit utfall vert meir sannsynleg enn det andre, so er det eit Bernoulli-forsøk; det er bare sannsynsfordelinga som er endra.

Definisjon 9 (Bernoulli-forsøk) Eit Bernoulli-forsøk er eit eksperiment som har to moglege utfall, me kaller dei gjerne suksess (suksess) og mislukka (failure), og der eksperimenta er uavhengige av kvarandre. Me skriv gjerne $p$ for suksess-sannsynet.

Det er forvirrande, men det som er bitfeilsannsynet

p

på BSC, vert gjerne kalt suksessannsynet

p

når me studerer Bernoulli-forsøket. Ein skal hugsa at namna suksess og mislukka er vilkårlege. Poenget er at der er to utfall. Suksess viser gjerne til det utfallet som me vel å fokusera på, og dermed gjerne til feil i kodeteori.

Døme 6 Lat $Z$ vera talet på bitfeil, når me sender $n$ bits over BSC $(p)$ . Dvs. at me gjer $n$ Bernoulli-forsøk med suksessannsyn $p$ og tel suksessane. Me seier at $Z$ er binomialfordelt med $n$ forsøk og punktsannsyn $p$ , og me kan skriva $Z \sim B (n, p)$ .

Oppgåve 3.47 Lat $X$ vera talet på mynt når du kastar mynt og kron $n$ gongar med ein rettferdig mynt. Kva fordeling har $X$ ?

Oppgåve 3.48 Sett at mynten er bøyd og har 40% sannsyn for å visa mynt. Lat $X$ vera talet på mynt når du kastar mynt og kron $n$ gongar. Kva fordeling har $X$ ?

3.4.4. Fredag (rekneøving)

Oppgåve 3.49 Tenk deg at du sender eit $4$ -bits ord på BSC $(p)$ med feilsannsyn $p = 0,1$ . Me kaller talet for feil for $Z$ .

1.: Kva er sannsynet $P (Z = 0)$ for å få ingen feil?
2.: Kva er sannsynet $P (Z = 4)$ for å få berre feil?
3.: Kva er sannsynet $P (Z = 1)$ for å nøyaktig éin feil?
4.: Kva er sannsynet $P (Z = 2)$ ?
5.: Kva er sannsynet $P (Z = 3)$ ?

Set opp sannsynsfordelinga i ein tabell, og bruk gjerne same tabell til dei to neste oppgåvene.

Oppgåve 3.50 Sjå vidare på sannsynsfordeling frå Oppgåve 3.49. Finn forventingsverdien $E (Z)$ .

Oppgåve 3.51 Sjå vidare på sannsynsfordeling frå Oppgåve 3.49. Finn variansen $σ^{2} = var (Z)$ og standardavviket $σ$ .

Oppgåve 3.52 Tenk deg at du sender eit $4$ -bits ord på BSC $(p)$ for ein vilkårleg verdi av $p$ . Me kaller talet for feil for $Z$ .

Finn sannsynet $P (Z = z)$ for $z = 0, 1, 2, 3, 4$ .

Oppgåve 3.53 Sjå vidare på sannsynsfordeling frå Oppgåve 3.52. Finn eit uttrykk for forventingsverdien $E (Z)$ .

Oppgåve 3.54 Sjå vidare på sannsynsfordeling frå Oppgåve 3.52. Finn uttrykk for variansen $σ^{2} = var (Z)$ og standardavviket $σ$ .

Oppgåve 3.55 Oppgåve 7.8 og 7.10–7.12 i Frisvold og Moe.

Oppgåve 3.56 (Ekstra) Tenk deg at du sender éin einskild bit over BSC $(p)$ . Lat $Z = 1$ indikera ein bitfeil, og $Z = 0$ null feil. No er $Z \sim B (1, p)$ , dvs. binomialfordelt med eitt forsøk og suksessannsyn $p$ .

1.: Lag ein tabell som viser (den diskrete) sannsynsfordelinga for $Z$ .
2.: Kva er forventingsverdien (populasjonsgjennomsnittet) $E (Z)$ ?
3.: Kva er variansen $var (Z)$ ?

Oppgåve 3.57 (Ekstra) Tenk deg at du sender eit $n$ -bits ord på BSC $(p)$ for ein vilkårlege verdiar av $n$ og $p$ . Me kaller talet for feil for $Z$ .

Finn sannsynet $P (Z = z)$ for $z = 0, 1, \dots, n$ .