Tilfeldige tall

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
mrcreosote
Guru
Guru
Innlegg: 1995
Registrert: 10/10-2006 20:58

Vi trekker tilfeldige tall uniformt fordelt på intervallet [0,1]. Hva er forventningsverdien for antall trekk vi trenger før vi når en sum på minst 1?
arildno
Abel
Abel
Innlegg: 684
Registrert: 17/03-2007 17:19

Okei, jeg hopper i baret; stopp meg hvis jeg beveger meg ut på ville veier!

1. Forutsatt normalfordeling, vil forventingsverdien for å trekke ett tall mellom 0 og 1 være 1/2, standardavviket skulle bli [tex]\sigma=\frac{1}{2\sqrt{3}[/tex], eller noe sånt.

2. Hvis [tex]\mu_{n},\sigma_{1}[/tex] betegner forventningsverdi&standardavvik for summen av n tilfeldig trukne tall, burde vi ha:
[tex]\mu_{n}=\frac{n}{2},\sigma_{n}=\frac{\sqrt{n}}{2\sqrt{3}}[/tex]

3. Spesielt betyr dette at sannsynligheten for at en n-sum konvergerer mot et eller annet tall, (for eksempel mindre enn 1) når n går mot uendelig, vil gå mot 0

4. Jeg velger meg som utfallsrom alle uendelige summer hvor hvert ledd ligger mellom 0 og 1; sannsynligheten for at noen av disse summene konvergerer er derfor 0.

5. Dette betyr at hver slik sum for en eller annen endelig delsum oversteg verdien 1, og vi kan derfor splitte opp utfallsrommet vårt i disjunkte, utfyllende delmengder utifra på hvilken n-te delsum de oversteg 1.

6 Vi skal altså finne forventningsverdien for n, dvs hvilken n'te delsum vi i gjennomsnitt kan si overstiger 1 for elementene i utfallsrommet.

Håper jeg foreløpig ikke har gjort noe feil..
arildno
Abel
Abel
Innlegg: 684
Registrert: 17/03-2007 17:19

7. Oppdelingen i utfallsrommet vårt gir oss derfor sannsynlighetsfordelingen:
[tex]\sum_{n=1}^{\infty}P(s_{n+1}\geq{1}\cap{s}_{n}\leq{1})=1[/tex]

8. Videre har vi:
[tex]P(s_{n+1}\geq{1}\cap{s}_{n}\leq{1})=P(s_{n}\leq{1})*P(s_{n+1}\geq{1}\mid{s}_{n}\leq{1})[/tex]

9. Dernest:
[tex]P(s_{n+1}\geq{1})=P(s_{n}\leq{1})*P(s_{n+1}\geq{1}\mid{s}_{n}\leq{1})+P(s_{n}\geq{1})*P(s_{n+1}\geq{1}\mid{s}_{n}\geq{1})[/tex]

10. I og med at alle ledd er positive, har vi:
[tex]P(s_{n+1}\geq{1}\mid{s}_{n}\geq{1})=1[/tex]

11. Dermed har vi uttrykket:
[tex]P(s_{n}\leq{1})*P(s_{n+1}\geq{1}\mid{s}_{n}\leq{1})=P(s_{n+1}\geq{1})-P(s_{n}\geq{1})[/tex], dvs:
[tex]P(s_{n+1}\geq{1}\cap{s}_{n}\leq{1})=P(s_{n+1}\geq{1})-P(s_{n}\geq{1})[/tex]

Får ta meg en pause..
Sist redigert av arildno den 06/10-2007 13:09, redigert 2 ganger totalt.
mrcreosote
Guru
Guru
Innlegg: 1995
Registrert: 10/10-2006 20:58

[tex]\cap\cup[/tex]

Jeg ser hva du tenker, men er ikke overbevist om at det vil føre fram. Du får prøve litt videre.
arildno
Abel
Abel
Innlegg: 684
Registrert: 17/03-2007 17:19

12. Forventningsverdien for n skulle nå gis ved:
[tex]n_{\mu}=\sum_{i=1}^{\infty}(i+1)*P(s_{i+1}\geq{1}\cap{s}_{i}\leq{1})=\sum_{i=1}^{\infty}(i+1)*(P(s_{i+1}\geq{1})-P(s_{i}\geq{1})=\sum_{i=1}^{\infty}(i+1)(P(s_{i}\leq{1})-P(s_{i+1}\leq{1})[/tex]

13. Vi setter nå [tex]P_{i}\equiv{P}(s_{i}\leq{1})[/tex], og en endelig delsum [tex]S_{N}[/tex] innholder da mange kanselleringer slik:
[tex]2P_{1}-2P_{2}+3P_{2}-3P_{3}+4P_{3}-4P_{4}=(P_{0}-P_{4})+(P_{1}-P_{4})+(P_{2}-P_{4})+(P_{3}-P_{4}), P_{0}\equiv{P}_{1}=1[/tex], dvs, vi kan skrive om uttrykket for forventingsverdien slik:

[tex]n_{\mu}=\lim_{N\to\infty}\sum_{i=1}^{N}(P_{i-1}-P_{N})[/tex]

Dette er da det uttrykket jeg har kommet meg frem til; gitt normalfordeling ([tex]P_{m}=\Phi(\frac{1-\frac{m}{2}}{\frac{\sqrt{m}}{2\sqrt{3}}})[/tex]) kan vi da regne ut en tilnærmingsverdi for n.
mrcreosote
Guru
Guru
Innlegg: 1995
Registrert: 10/10-2006 20:58

Det kan være det fører fram det du holder på med, men det virker unødvendig komplisert. Jeg er heller ikke interessert i en tilnærming (det er det bare dere fluidmekanikere(?) som er), men et nøyaktig og pent svar.
arildno
Abel
Abel
Innlegg: 684
Registrert: 17/03-2007 17:19

Du har fått et nøyaktig, om ikke pent, svar. :)
mrcreosote
Guru
Guru
Innlegg: 1995
Registrert: 10/10-2006 20:58

Svaret er e, hvor stilig er ikke det. Men jeg vil gjerne ha et argument.
Magnus
Guru
Guru
Innlegg: 2286
Registrert: 01/11-2004 23:26
Sted: Trondheim

Jobber du med fluidmekanikk, arildno?
Nebuchadnezzar
Fibonacci
Fibonacci
Innlegg: 5648
Registrert: 24/05-2009 14:16
Sted: NTNU

$e$
"Å vite hva man ikke vet er og en slags allvitenhet" - Piet Hein
https://s.ntnu.no/Integralkokeboken
Lektor - Matematikk, Fysikk og Informatikk
zzzivert
Noether
Noether
Innlegg: 48
Registrert: 27/10-2014 09:26

Tar opp tråden og prøver meg på denne.

Ideen min er å dele intervallet inn i et endelig antall uniformt fordelte tall, og at tallene vi trekker er blandt disse. Deretter lar vi antallet gå mot uendelig og finner forventningsverdien.

Vi kan skrive [tex][0,1]=[0,\frac{1}{n+1}] \cup [\frac{1}{n+1},\frac{2}{n+1}] \cup \cdots \cup [\frac{n}{n+1},1][/tex], og anta at tallene vi kan velge kun er endepunktene i disse intervallene, unntatt 0 og 1.

La oss trekke tallene [tex]x_1, x_2, ... , x_m, x_{m+1}[/tex], der [tex]x_i \in \{ \frac{1}{n+1}, ..., \frac{n}{n+1} \}[/tex], slik at [tex]x_1+x_2+ \cdots+ x_m<1\leq x_1+x_2+ \cdots+ x_m + x_{m+1}[/tex]. Vi får en sum på minst 1 etter [tex]m+1[/tex] trekk.

La [tex]P_n(m+1)[/tex] være sannsynligheten for å en sum på minst 1 etter [tex]m+1[/tex] trekk, og la [tex]R_n(m+1)[/tex] være antall [tex](m+1)[/tex]-tupler slik at vi får en sum på minst 1 etter [tex]m+1[/tex] trekk (når vi kan velge mellom [tex]n[/tex] tall).

Siden det finnes [tex]n^{m+1}[/tex] mulige [tex](m+1)[/tex]-tupler, har vi at
[tex]P_n(m+1)=\frac{R_n(m+1)}{n^{m+1}}[/tex]

Vi skal nå finne et utrykk for [tex]R_n(m+1)[/tex].
La [tex]S=x_1+x_2+ \cdots+ x_m<1[/tex]. Med et "stars and bars"-argument kan vi vise at antall kombinasjoner [tex]x_1, x_2, ... , x_m[/tex] som har denne summen er [tex]\binom{S-1}{m-1}[/tex]. I tillegg stemmer det at for hver sum [tex]S[/tex], har vi [tex]S[/tex] mulige trekk for [tex]x_{m+1}[/tex] slik at [tex]x_1+x_2+ \cdots+ x_m + x_{m+1} \geq 1[/tex].

Derfor har vi nå
[tex]R_n(m+1)=\sum_{S=m}^{n} \binom{S-1}{m-1} \cdot S \\ =m \sum_{S=m}^{n} \binom{S}{m} \\ =m \cdot \binom{n+1}{m+1}[/tex]
der den siste likheten bruker det som blir kalt "hockey stick identity".

Siden [tex]m \cdot \binom{n+1}{m+1} = m \cdot \frac{(n+1)n(n-1)\cdots (n-m+1)}{(m+1)!}=m \cdot \frac{n^{m+1}+r(n)}{(m+1)!}[/tex], der [tex]r(n)[/tex] er et polynom av grad [tex]\leq n^m[/tex], får vi
[tex]P_n(m+1)=\frac{R_n(m+1)}{n^{m+1}}=m\cdot \frac{n^{m+1}+r(n)}{(m+1)!n^{m+1}}[/tex]

La [tex]P(m+1)=\lim_{n \rightarrow \infty} P_n(m+1)=m\cdot \frac{1}{(m+1)!}[/tex], da er [tex]P(m+1)[/tex] sannsynligheten til å nå en sum på minst 1, etter [tex]m+1[/tex] trekk.

Til slutt har vi at forventningsverdien er gitt
[tex]E(X)=\sum_{m=1}^{\infty} P(m+1)\cdot (m+1)=\sum_{m=1}^{\infty} m\cdot \frac{1}{(m+1)!}\cdot (m+1)=\sum_{m=1}^{\infty} \frac{1}{(m-1)!}=e[/tex]
Svar