Statistikk og Simulering

Veke 5. Feilsannsyn og binomialfordeling

Måndag (førelesing)

5.2. Måndag (førelesing)

5.2.1. 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 c før han vert sendt på kanalen. Det mottekne signalet r som kjem ut frå kanalen er sjelden identisk med c, men når me dekodar so får me eit estimat m̂ for den opprinnelege meldinga m. Det store spørsmålet, som me ofte treng statistikk for å svara på, kva er feilsannsynet P(mm̂)?

Definisjon 11 (Binary Symmetric Channel)

pict


Figur 2: The binary symmetric channel.

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

Den binærsymmetriske kanalen (BSC), dvs. at s, r, og e er binære (vektorar over GF(2) = {0, 1}), og addisjon er modulo 2. På BSC er feilvektoren 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 2 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 3 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 12 (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 4 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 B(n,p).

Oppgåve 5.1 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 5.2 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?

5.2.2. Binomialfordelinga

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

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

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

5.2.3. Forventingsverdi og varians

Oppgåve 5.6 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 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)?

Lat

X = X1 + X2 + + Xn

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

E(X) = E(X1) + E(X2) + + E(Xn).

Lat

X = X1 + X2 + + Xn

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

var(X) = var(X1) + var(X2) + + var(Xn).

Når me sender eit n-bits ord over BSC(p) er feiltalet X B(n,p) binomialfordelt med n forsøk og suksessannsyn p. Merk at X er summen av n uavhengige forsøk,

X = X1 + X2 + + Xn,

der kvar Xi er fordelt som Z B(1,p) i oppgåva over. Då kan me bruka desse to satsane.

Oppgåve 5.7 Tenk deg at du sender eit n-bits ord over BSC(p). Lat X 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 5.6 og dei to satsane over for å koma fram til svaret.

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