Hvor mange 6'ere er det mulig å slå på rad?

[JBlack]

Som sagt på side to, alle program som bruker pseudorandom algoritmer er avhengig av algoritmens oppløsning, og de vil før eller siden gjenta seg. Man har derfor en praktisk øvre grense.

 

Har man derimot en prosess som genererer ekte tilfeldige tall, og man setter som forutsetning at denne prosessen vil gå i uendelig tid, så vil man før eller siden få en uendelig rekke 6'ere. Der tar anth feil, og resten har rett.

 

Anta at vi har en prosess som trekker en million tall med ekte tilfeldighet. Sansynligheten for at vi fikk den rekken vi fikk, er akkurat like stor som sansynligheten for at vi skulle ha fått bare 6'ere. Det ville vært utrolig om vi fikk bare 6'ere. Men ikke mer utrolig enn den rekken vi faktisk fikk!

 

Poenget er at det finnes ekstremt mange flere rekker med blanding av tall, enn det finnes rekker med bare 6'ere i. Derfor er sansynlighet større for at vi skal trekke en av disse ekstremt mange rekkene, enn den er for at vi treffer 6'er-rekka. Men akkurat den rekka vi fikk, den er like usanslig og unik som 6'er rekka. Og hvis vi fortsatte å trekke rekker med en million tall, så er sansynligheten for at vi skal få akkurat den rekka igjen før vi får 6'er rekka 50%.

 

Oppgave: Anta at vi trekker en uendelig rekke tall, og at vi kan velge hvor i denne vi kan begynne å se etter den rette kombinasjonen på en million tall (enten kopi av rekken over, eller en million 6'ere).

A) Hvordan endrer sansynligheten seg da?

B) Hva er de nye sansynlighetene?

 

Når det gjelder problemstillingen uendelig rekker av 6'ere (og andre tall), samtidig som man før eller siden må få en fem'er, dersom man trekker tall uendelilg fort i all evighet, så tror jeg at vi har et paradox og at begge er riktig. Uendelig er et vanskelig begrep å forstå. Og jeg tror det i numerikken finnes flere forskjellige klasser av uendelig. Men dette er ikke noe jeg kan.

[834HF42F242]

Uendelig er ikke et tema lenger, og vi vil aldri få se en uendelig rekke med like tall fra en generator i praksis.

 

Edit: Ja der forteller du om det samme paradokset. Begge deler blir riktig, og uendelig kan ikke brukes som argumentasjon.

Endret 1. november 2005 av anth

[Torbjørn]

Det er ikke noe problem å forholde seg til uendelig matematisk

 

Sannsynligheten for aldri å få en 6'er når antall kast går mot uendelig er:

 

p(n) = (5/6)^n

 

Dette uttrykket går mot 0 når antall kast går mot uendelig, dvs du vil aldri få en rekke med samme tall når antall kast går mot uendelig.

 

Men en million? javisst.

[834HF42F242]

Venter i spenning på om noen kan klare å få simulert dette i et miljø som viser om kurven noen gang vil bøye av etter x antall kast i forhold til sannsynlighetskurven eller ikke.

[Torbjørn]

Siden dette er en uendelig kurve så var jo det et meningsfullt utsagn å komme med.

[834HF42F242]

Snakker ikke om å kjøre uendelig, men å kjøre den mye lenger enn det er gjort til nå, og se om begge kurvene fortsatt går likt.

[Torbjørn]

Som sagt før, med mindre du setter dette i lys av noe annet, så er det fortsatt rimelig meningsløst.

 

For 20 år siden var slik enkel maskinkraft Sci-Fi - ville du da ikke gitt deg før noen hadde kjørt slik 10 million ganger og plottet en kurve?

 

Så lenge du ikke innfører noe annet enn at terningen til en hver tid har 1/6 sannsynlighet for å få et gitt tall, så har du ingen grunn til å tro at fremtidige resultater vil bli annerledes.

[834HF42F242]

Jeg vil bare se en lenger kurve enn den vi har nå, og se om kurven som viser treff på like tallrekker følger etter.

Hva er problemet med å ville se det?

[Torbjørn]

Venter i spenning på om noen kan klare å få simulert dette i et miljø som viser om kurven noen gang vil bøye av etter x antall kast i forhold til sannsynlighetskurven eller ikke.

5093140[/snapback]

 

Problemet er det at du ikke hadde noen skjellig grunn til å tro noe som helst om dataene opp til 12-13 like terninger, hvorfor er disse dataene utover dette annerledes? det er fortsatt tallet 1/6 som gjelder. Det at du syntes kurven ikke nådde langt nok, så så du ut til å trekke rett inn i din argumentasjon for at tallet for 1.000.000 vil flate ut.

 

Jeg kjører 1e12 kast til imorgen, forventet tidsbruk er 8.5 time. håper kanskje å nå opp på 16 like.

 

Når det er sagt kan kurven fort endres, det er meget mulig at sannsynligheten følger en kurve som bare i de 10-20 første størrelsesordnene følger en tilsynelatende eksponentiell utvikling.

 

Ellers er problemet at vi tilsynelatende er i grenseland for der den eksponensielle kurven for antall kast toucher nedi den lineære kurven for vår tids datakraftutvikling. så å øke på med et par like terninger vil kreve enoormt mye mer for hvert tall utover.

 

EDIT: ser at den har nådd 17 etter 90 mrd kast

Endret 2. november 2005 av Torbjørn

[834HF42F242]

Ja, er klar over at begrensningene for hva som er mulig å gjøre med dagens teknologi melder seg veldig raskt.

Lurer derfor på hvor mange kast det er mulig å få unnagjort om man kjører et utlimat program i 1 uke på NTNUs supermaskin. Vet ikke så mye om maskinen, men har hørt at den består av over 1000 prosessorer og er den kraftigste maskinen i Norge, om ikke Norden.

Hvis noen lager et knakende bra program, kan jeg få en kar til å teste dette på nevnte supermaskin.

[Paddington]

Ja, er klar over at begrensningene for hva som er mulig å gjøre med dagens teknologi melder seg veldig raskt.

Lurer derfor på hvor mange kast det er mulig å få unnagjort om man kjører et utlimat program i 1 uke på NTNUs supermaskin. Vet ikke så mye om maskinen, men har hørt at den består av over 1000 prosessorer og er den kraftigste maskinen i Norge, om ikke Norden.

Hvis noen lager et knakende bra program, kan jeg få en kar til å teste dette på nevnte supermaskin.

5093218[/snapback]

 

I natt traff jeg 16! etter 608 897 420 571 kast! Hvis jeg lar programmet gå en uke til, har jeg gode muligheter for å få 17. Jeg vil sannynlig vis som du sier aldri komme over 20, men kan får nok 19 etter ca et år, eller 22 om et par hundre år....

 

Min nye verdensrekord: :-)

 

2 like etter 2 iterasjoner med 2'ere

3 like etter 7 iterasjoner med 3'ere

4 like etter 463 iterasjoner med 3'ere

5 like etter 1191 iterasjoner med 3'ere

6 like etter 10511 iterasjoner med 2'ere

7 like etter 97934 iterasjoner med 3'ere

8 like etter 324693 iterasjoner med 6'ere

9 like etter 1853106 iterasjoner med 5'ere

10 like etter 2501804 iterasjoner med 3'ere

11 like etter 3625549 iterasjoner med 4'ere

12 like etter 198560987 iterasjoner med 4'ere

13 like etter 8667746122 iterasjoner med 6'ere

14 like etter 8667746123 iterasjoner med 6'ere

15 like etter 8667746124 iterasjoner med 6'ere

16 like etter 608897420571 iterasjoner med 1'ere

 

 

------

Anth og Torbjørn:

 

La oss si at 16 er den magiske grensen man ikke kan komme over. Mitt program kom dit på ett døgn: Hvis programmet kjører 6 døgn, vil jeg sannsynlivis komme til 16.. 6 ganger. For hver av rekkene med 16 på rad skal det slås en terning til. Og: Siden jeg har 1/6 sannsylighet for å treffe, vil jeg kunne forvente at ca 1 av dem treffer, altså har jeg 17 på en av dem. Logikken fortsetter fra 17 til 18, jeg må kjøre 6 ganger så lenge.... Hvis du kan noe om datastrukturer, ser du at dette blir et tre med 6 barn for hver node.

 

forventningen blir da (hvis man bare tillater 6'ere):

 

1 : 6 kast

2 : 36 kast

3 : 729 kast

4 : 6^4 kast

5 : 6^5 kast

n : 6^n kast

 

En mill på rad er barnemat, men det tar altså 6^1000000 kast å forvente å treffe. Dette kan du selvsagt aldri oppnå i universets levetid....

 

Denne fikser 6^100 000, tallet har jeg allerede postet som vedlegg tidligere i tråden... (ikke plass til tallet i en post :-)

 

Jeg tillater ikke bare 6'ere på rad, og får forventning 6^(n-1) = 470 184 984 576 kast for 16 på rad, ikke så langt unna, hadde bare litt "uflaks"....

Endret 2. november 2005 av Paddington

[Torbjørn]

Hvorfor begrense deg til bare 6ere?

[Paddington]

Hvorfor begrense deg til bare 6ere?

5093729[/snapback]

 

Ingen grunn til det, men det er blitt nevnt flere steder i tråden : Sannsylighet for 6'ere på rad...., men les site linje i min forrige post....

 

EDIT: ser at den har nådd 17 etter 90 mrd kast

 

Snakk om griseflaks!! Bare 3,2 prosent sjans for å treffe 17 så tidlig!!

Endret 2. november 2005 av Paddington

[Torbjørn]

ah, jeg leste en "ikk" for lite

[Simen1]

La oss si at 16 er den magiske grensen man ikke kan komme over. Mitt program kom dit på ett døgn: Hvis programmet kjører 6 døgn, vil jeg sannsynlivis komme til 16.. 6 ganger. For hver av rekkene med 16 på rad skal det slås en terning til. Og: Siden jeg har 1/6 sannsylighet for å treffe, vil jeg kunne forvente at ca 1 av dem treffer, altså har jeg 17 på en av dem. Logikken fortsetter fra 17 til 18, jeg må kjøre 6 ganger så lenge.... Hvis du kan noe om datastrukturer, ser du at dette blir et tre med 6 barn for hver node.

Her er du inne på kjernen av spørsmålet. For hver gang men kjører 6 ganger så lenge så er det sansynlig å få 6 rekker med like mange siffer på rad, og dermed sansynligvis få ennå et likt siffer etter den lange rekka.

 

En mill på rad er barnemat, men det tar altså 6^1000000 kast å forvente å treffe. Dette kan du selvsagt aldri oppnå i universets levetid....

 

Denne fikser 6^100 000, tallet har jeg allerede postet som vedlegg tidligere i tråden... (ikke plass til tallet i en post

5093575[/snapback]

Innleggene her på HW er begrenset til 65536 tegn.

 

Angående den kraftige maskinen på NTNU så er det faktisk flere. Spesifikasjonene finnes på hjemmesiden til NOrsk TUngRegning (NOTUR). Den med flest CPU'er har 512 stk R14000-CPU'er, mens den som regnes som kraftigst har 396 ItaniumII prosessorer og står på universitetet i Tromsø. Regnekapasiteten på sistnevnte er oppgitt til å være 2229 Gflops. Altså drøyt 2 trillioner flyttallsoperasjoner per sekund. Noe som bør være nok til å få kjørt teoretisk opp mot ca 2*10^17 terningkast per døgn, eller ca 22 like på rad på ett døgn. 23 like vil ta ca en uke, 24 like vil ta ca en måned, 25 like vil ta ca et halvt år osv. Men da kan du jo sikkert bare si at "det flater ut en plass etter der". Altså: du kan skyve argumentasjonen videre og videre etter hvert som man får testet lengre. Det blir altså umulig for oss å bevise noe som helst så lenge du holder på slik og ikke godtar matematikken.

 

Forøvrig er det vanskelig å få kjøretid på maskina. Hvis du ikke er med i et vitenskapelig prosjekt på ett av universitetene og får innvilget søknad om dekning av kostnadene av universitetet så må du betale for kjøretida selv og det er i hvertfall ikke billig når man begynner å prate om kjøretider på et døgn.

[kyrsjo]

Kanskje noen kan forsøke å få en generator til å sette en verdensrekord?

 

Ny verdensrekord ;-)

 

2 like etter 2 iterasjoner med 2'ere

3 like etter 7 iterasjoner med 3'ere

4 like etter 463 iterasjoner med 3'ere

5 like etter 1191 iterasjoner med 3'ere

6 like etter 10511 iterasjoner med 2'ere

7 like etter 97934 iterasjoner med 3'ere

8 like etter 324693 iterasjoner med 6'ere

9 like etter 1853106 iterasjoner med 5'ere

10 like etter 2501804 iterasjoner med 3'ere

11 like etter 3625549 iterasjoner med 4'ere

12 like etter 198560987 iterasjoner med 4'ere

13 like etter 8667746122 iterasjoner med 6'ere

14 like etter 8667746123 iterasjoner med 6'ere

15 like etter 8667746124 iterasjoner med 6'ere

 

Forventet antall iterasjoner som kreves for å få 100 000 6'ere på rad ligger i vedlagt fil, et lite tall i forhold til uendelig, men jeg tror ikke vi treffer de nermeste dagene ;-)

5089040[/snapback]

 

Stopper den etter at den har funnet forrige+1, eller teller den hvor mange den faktisk greide?

 

Ang. supermaskin så har jeg tilgang til en 4-veis Xeon box (arkimedes.uio.no), som sikkert kan få krunche på 1-2 cpu'er noen timer uten at noen sier noe. Eneste er at jeg aner ikke hvordan man skriver trådede programmer, så hvis noen kan skrive et bra trådet program i C/C++/Java (altså språk jeg kan lese og forstå uten problemer), så kan jeg få kjørt det der.

 

Forøvrig så vil den fortsette å utvikle seg slik (1/6^x, hvor x er hvor mange like vi ønsker)- problemet er altså at sjangsen for å få en riktig til faller av med en faktor på 1/6 for hver gang vi vil ha ennå en lik.

 

Anth: Du ville hatt glede av MAT-1100 (calculus), med en skikkelig gjennomgang av grenseverdier

Endret 2. november 2005 av kyrsjo

[Paddington]

Stopper den etter at den har funnet forrige+1, eller teller den hvor mange den faktisk greide?

 

Stopper aldri, legger til ett terningkast og holder hele tellingen på hvor mange på rad den har akkurat nå....(og hva som er max til nå...) ref. kildekoden: while(true)

 

Eksempel, traff 13 like og slo to seksere på rad etter dette....:

 

13 like etter 8667746122 iterasjoner med 6'ere

14 like etter 8667746123 iterasjoner med 6'ere

15 like etter 8667746124 iterasjoner med 6'ere

Endret 2. november 2005 av Paddington

[Torbjørn]

Parallellisering er problemet ja, programmet må skrives så det kan kjøre enkeltoppgavene parallellt, inntil det skjer, vil ikke superdatamaskinen regne raskere enn hva dets enkelt cpu'er klarer alene

 

og disse er ikke alltid særlig kjappere enn forbruker-cpuer, igjen, hvis noen har en AMD FX cpu med c kompilator, så si gjerne fra

[Torbjørn]

Resultatet av en over-natta kjøring ser slik ut (totalt antall kast = 10^12, 1000 milliarder):

 

torbjorn@fuge(~/c-code)$ time ./dice
 2             2
 3            38
 4           394
 5          2109
 6          9067
 7         96398
 8        437694
 9       5330691
10      12112013
11      44671062
12     167304731
13    2269442411
14   18776232539
15   54167386821
17   93328530762

real    562m17.489s
user    561m56.004s
sys     0m4.430s

 

Modellen ser slik ut:

 

Coefficients:
(Intercept)            x
   -0.9832       1.6898

 

Viktig å merke seg her, er at stigningstallet for x er omtrent det samme som forige gang. Så estimatet for 20 blir omtrent uforandret (vel, 180 000 milliarder men fortsatt i samme størrelsesorden)

[Simen1]

Torbjørn: Hvis du kjører programmet mange ganger så kan du legge inn resultatet mange ganger for å få et mer nøyaktig stigningstall.

 

Angående kjøring i parallell: Kjør heller to instanser av programmet (affinitet til hver sin kjerne) og la programmet logge de første og siste 100 sifrene til en fil. Så kan du i ettertid legge tallrekkene etter hverandre (slutten av fil 1 sammen med begynnelsen av fil 2) slik at det blir en sammenhengene rekke. Hvis tilfeldighetene skulle gjøre sånn at du får mange like på rad akkurat i overgangen mellom fil 1 og fil 2 så får du ta det i betraknting manuelt. Samme metode kan brukes for å kjøre dette på en massivt parallell superdatamaskin.