Litt sannsynlighet

Her kan brukere av forum utfordre hverandre med morsomme oppgaver og nøtter man ønsker å dele med andre. Dette er altså ikke et sted for desperate skrik om hjelp, de kan man poste i de andre forumene, men et sted for problemløsing på tvers av trinn og fag.

Moderatorer: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa

Svar
sEirik
Guru
Guru
Innlegg: 1551
Registrert: 12/06-2006 21:30
Sted: Oslo

Vi har ei eske med n baller i.
Hver ball har ett unikt nummer.
Vi trekker en ball, skriver ned nummeret til ballen på ei liste, og legger den tilbake i eska.
Vi trekker en ball til, skriver ned nummeret til denne ballen på lista, og legger den tilbake.
Slik fortsetter vi å trekke én og én ball helt inntil vi trekker en ball som vi allerede har trukket.
Vi lar X være antall forsøk som kreves for å finne en ball vi allerede har trukket. X må da være minst 2 og høyest n+1.

a) Finn sannsynlighetsfunksjonen [tex]f(x) = P(X = x)[/tex].

Vi ser på et tilfelle der vi har 50 baller i esken.

b) Finn forventningsverdi og standardavvik til antall forsøk som kreves.

Vi har en hash-funksjon md5(x) som gis et hvilket som helst naturlig tall, og returnerer en tekststreng som er 32 tegn lang, og som kan inneholde tegnene 0-9 og a-f. Denne funksjonen kan da ta [tex]16^32[/tex] ulike verdier.
Vi lager en algoritme som kjører ved å begynne med i = 1, skrive med md5(1), så i = 2, skrive ned md5(2) osv. inntil den har funnet to x-verdier som gir samme tekststreng.

c) Hvor mange forsøk kan man forvente at algoritmen krever? Og hvor stort blir standardavviket? (Her må man nok bruke litt tilnærming)
Solar Plexsus
Over-Guru
Over-Guru
Innlegg: 1685
Registrert: 03/10-2005 12:09

a) Når du trekker ball nummer [tex]i\,<\,x[/tex], skal du unngå å trekke en blant de [tex]i-1[/tex] første du trakk. Sannsynligheten for at dette skjer er [tex]\frac{n-(i-1)}{n}.[/tex] Når du til slutt trekker ball nummer [tex]x[/tex], er sannsynligheten for å trekke en av de [tex]x-1[/tex] tidligere uttrukne ballene lik [tex]\frac{x-1}{n}.[/tex]. Alt i alt betyr dette at

[tex]P(X=x) \:=\: \frac{n}{n} \: \cdot \: \frac{n-1}{n} \: \cdot \: \frac{n-2}{n} \: \cdots \: \frac{n-(x-2)}{n} \: \cdot \: \frac{x-1}{n} \;=\; \frac{n!(x-1)}{(n-(x-1))! \, n^x}.[/tex]


b)

[tex]E(X=50) \;=\; \sum_{x=2}^{51} \frac{50!(x-1)x}{(51-x)! \, 50^x} \; \approx \; 9,5[/tex]

og

[tex]SD(X=50) \;=\; \sqrt{Var(X=50)} \; = \; \sqrt{-\.[E(X=50)]^2 \;+\; \sum_{x=2}^{51} \frac{50!(x-1)x^2}{(51-x)! \, 50^x}}\;,[/tex]

dvs. at

[tex]SD(X=50) \; \approx \; 4,3.[/tex]


c) Dette problemet tilsvarer åpenbart "ballproblemet" i oppgaven ovenfor med [tex]n = 16^{32}.[/tex] Her kommer jo kalkulatoren til kort. En mulig løsningsmåte er å finne tilnærminger for forventningsverdien og standardavviket eller å finne eksplisitte uttrykk for seriene som gir E(X=x) og SD(X=x). I farten kan jeg ikke finne noe av delene. Kanskje andre har noen konstruktive forslag?
arildno
Abel
Abel
Innlegg: 684
Registrert: 17/03-2007 17:19

Kanskje Stirlings formel kan være grei for å finne en god tilnærming.
Burde iallefall føre til noe forenklinger, men jeg har den ikke foran meg nå..
sEirik
Guru
Guru
Innlegg: 1551
Registrert: 12/06-2006 21:30
Sted: Oslo

Fint arbeid :)
Bare noe som skurrer litt med notasjonen der.
Man kan snakke om [tex]P(X=x)[/tex], men jeg har da aldri hørt om at man kan snakke om [tex]E(X=50)[/tex] og [tex]SD(X=50)[/tex]? Man snakker om [tex]E(X)[/tex] og [tex]SD(X)[/tex] når [tex]n=50[/tex].

Her er fasiten min:

a) [tex]{\rm P} (X=k) = \frac{(k-1)n!}{(n-k+1)! \cdot n^k} = \frac{k-1}{n^k} \cdot \ _ n {\rm P}_{k-1}[/tex]

b) Generelt:

[tex]E(X) = \sum_{k=2}^{n+1} k \cdot {\rm P}(X = k) = \sum_{k=2}^{n+1} k \cdot \frac{k-1}{n^k} \cdot \ _ n {\rm P}_{k-1} = \sum_{k=2}^{n+1} \frac{k^2-k}{n^k} \cdot \ _ n {\rm P}_{k-1}[/tex]

[tex]Var(X) = \sum_{k=2}^{n+1} (k-\mu)^2 \cdot {\rm P}(X = k) = \sum_{k=2}^{n+1} (k-\mu)^2 \cdot \frac{k-1}{n^k} \cdot \ _ n {\rm P}_{k-1}[/tex]

(Blir veldig tungvint å regne med nøyaktige tall her, så vi kjører desimaltall. Men da kan vi i hvert fall ha med så mange desimaler som mulig.)
Når n = 50 er [tex]E(X) = \sum_{k=2}^{51} \frac{k^2 - k}{50^k} \cdot \ _{50}{\rm P}_{k-1} \approx 9.543127039[/tex]

[tex]Var(X) \approx \sum_{k=2}^{51} (k-9.543127039)^2 \cdot \frac{k - 1}{50^k} \cdot \ _{50}{\rm P}_{k-1} \approx 18.47185335[/tex]

[tex]SD(X) = \sqrt{Var(X)} \approx 4.297889406[/tex]

Vi ser at vi får forventningsverdi ca. 9.5 og standardavvik ca. 4.3.

c) Har ikke laget fasit til denne. Må nesten finne en passelig tilnærming selv før jeg kan gjøre den. :P
Svar