matematikk.net

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)

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?

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å..

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.