---

Når vi nu i en anden tråd diskuterer pindekast og pi, så
kommer jeg til at tænke på en anden pi-sammenhæng.

Vi tager 2000000 mennesker og giver dem en mønt hver.
De kaster nu hver for sig plat og krone og forlader
spillet, hvis de på et tidspunkt har fået lige mange
plat og kroner. Hvis vi antager at de kan nå et kast
i sekundet, hvornår er de mon så færdige allesammen ?

I den kilde, jeg har til opgaven, står der at det var Edmund
Borel, der i 1600'tallet regnede på den. Det tror jeg ikke
meget på, så hvis der er nogen, der er stødt på opgaven før,
vil jeg gerne have et praj om hvor den stammer fra.

Sammenhængen med pi overlades som en øvelse til læserne

mvh Birger Nielsen (bnielsen@daimi.au.dk)

---

"Kai Birger Nielsen" <bnielsen@daimi.au.dk> skrev i en meddelelse news:blel29$1k4$1@news.net.uni-c.dk...
>
> Sammenhængen med pi overlades som en øvelse til læserne
>
Tak.
Er 1595 s nogenlunde rigtigt?

Mvh
Martin

---

In <3f7b67f6$0$32465$edfadb0f@dread16.news.tele.dk> "Martin Larsen" <mlarsen@post7.tele.dk> writes:

>"Kai Birger Nielsen" <bnielsen@daimi.au.dk> skrev i en meddelelse news:blel29$1k4$1@news.net.uni-c.dk...
>>
>> Sammenhængen med pi overlades som en øvelse til læserne
>>
>Tak.
>Er 1595 s nogenlunde rigtigt?

>Mvh
>Martin


Nej. (Jeg gætter på at 1595 s svarer til at du tror at mængden
bliver ca halveret for hver omgang og det er langt fra hvad der
faktisk sker.)

mvh Birger Nielsen (bnielsen@daimi.au.dk)

---

"Kai Birger Nielsen" <bnielsen@daimi.au.dk> skrev i en meddelelse news:blgglp$msc$1@news.net.uni-c.dk...

> Nej. (Jeg gætter på at 1595 s svarer til at du tror at mængden
> bliver ca halveret for hver omgang og det er langt fra hvad der
> faktisk sker.)
>
Nej, her i morgenens uendeligt skarpe lys ser jeg at det er sludder.
Jeg havde en fin formel, men den konvergerer desværre ikke.

Mvh
Martin

---

bnielsen@daimi.au.dk (Kai Birger Nielsen) writes:

> Når vi nu i en anden tråd diskuterer pindekast og pi, så
> kommer jeg til at tænke på en anden pi-sammenhæng.
>
> Vi tager 2000000 mennesker og giver dem en mønt hver.
> De kaster nu hver for sig plat og krone og forlader
> spillet, hvis de på et tidspunkt har fået lige mange
> plat og kroner. Hvis vi antager at de kan nå et kast
> i sekundet, hvornår er de mon så færdige allesammen ?

Der er med meget stor sandsynlighed nogen, der aldrig bliver færdige.

   Torben

---

In <w5pthgdr9k.fsf@pc-032.diku.dk> torbenm@diku.dk (Torben Ægidius Mogensen) writes:

>bnielsen@daimi.au.dk (Kai Birger Nielsen) writes:

>> Når vi nu i en anden tråd diskuterer pindekast og pi, så
>> kommer jeg til at tænke på en anden pi-sammenhæng.
>>
>> Vi tager 2000000 mennesker og giver dem en mønt hver.
>> De kaster nu hver for sig plat og krone og forlader
>> spillet, hvis de på et tidspunkt har fået lige mange
>> plat og kroner. Hvis vi antager at de kan nå et kast
>> i sekundet, hvornår er de mon så færdige allesammen ?

>Der er med meget stor sandsynlighed nogen, der aldrig bliver færdige.

>   Torben

Enig, hvis du regner med normal forventet levealder. Ellers
er jeg ikke enig. Aldrig er lang tid, så hvor mange mener
du at der er tilbage efter fx en million år ?

mvh Birger Nielsen (bnielsen@daimi.au.dk)

---

"Kai Birger Nielsen" <bnielsen@daimi.au.dk> skrev i en meddelelse news:blgnoc$qum$1@news.net.uni-c.dk...
>
> Enig, hvis du regner med normal forventet levealder. Ellers
> er jeg ikke enig. Aldrig er lang tid, så hvor mange mener
> du at der er tilbage efter fx en million år ?
>
Du kan få ss for at vente længe (præcis n/2 sek):
1/(2*sqrt(pi)*n^1.5)
Og her kommer pi ind

Mvh
Martin

---

"Martin Larsen" <mlarsen@post7.tele.dk> skrev i en meddelelse news:3f7bfb5f$0$32498> >

Rettelse 2n sek.

---

"Martin Larsen" <mlarsen@post7.tele.dk> skrev i en meddelelse news:3f7bfc6a$0$32477$edfadb0f@dread16.news.tele.dk...

Hvis ikke der er kommet rod i mine tal skulle ventetiden
for tider større end 500 sek findes med 4 betydene cifre af

ss_vente_mere_end_t_sek = (pi*t/2)^(-.5)

Og nu er der ikke mere plads på konvolutten.

Mvh
Martin

---

"Martin Larsen" <mlarsen@post7.tele.dk> skrev i en meddelelse news:3f7c1e0c$0$32462$edfadb0f@dread16.news.tele.dk...
>
Her kommer så endnu et hint til løsningen

Se her punkt 9
http://mathpages.com/home/kmath322.htm

Mvh
Martin

---

In <3f7bfb5f$0$32498$edfadb0f@dread16.news.tele.dk> "Martin Larsen" <mlarsen@post7.tele.dk> writes:

>"Kai Birger Nielsen" <bnielsen@daimi.au.dk> skrev i en meddelelse news:blgnoc$qum$1@news.net.uni-c.dk...
>>
>> Enig, hvis du regner med normal forventet levealder. Ellers
>> er jeg ikke enig. Aldrig er lang tid, så hvor mange mener
>> du at der er tilbage efter fx en million år ?
>>
>Du kan få ss for at vente længe (præcis n/2 sek):
>1/(2*sqrt(pi)*n^1.5)
>Og her kommer pi ind

>Mvh
>Martin

Det ser rimeligt fornuftigt ud. Hvor mange er der så tilbage
efter fx en million år ? (Eller mere præcist, hvad er det
forventede antal ?)

mvh Birger Nielsen (bnielsen@daimi.au.dk)

---

"Kai Birger Nielsen" <bnielsen@daimi.au.dk> skrev i en meddelelse news:blj4go$fvd$1@news.net.uni-c.dk...
>
> Det ser rimeligt fornuftigt ud. Hvor mange er der så tilbage
> efter fx en million år ? (Eller mere præcist, hvad er det
> forventede antal ?)
>
Under antagelse af at den anden formel jeg angav var rigtig
kan vi finde ss for at der kun er én person tilbage og ham kan
vi give til fanden og sige at vi er færdige.

Så får vi 1/(2000000) = 1/sqr(pi*t/2) <=> t = 8/pi*10^12 sek

80693 år

Ved indsættelse i samme formel findes svaret på dit spørgsmål til
0,284 person tilbage efter 1 mio år.

Mvh
Martin

---

In <3f7d5a46$0$32526$edfadb0f@dread16.news.tele.dk> "Martin Larsen" <mlarsen@post7.tele.dk> writes:

>"Kai Birger Nielsen" <bnielsen@daimi.au.dk> skrev i en meddelelse news:blj4go$fvd$1@news.net.uni-c.dk...
>>
>> Det ser rimeligt fornuftigt ud. Hvor mange er der så tilbage
>> efter fx en million år ? (Eller mere præcist, hvad er det
>> forventede antal ?)
>>
>Under antagelse af at den anden formel jeg angav var rigtig
>kan vi finde ss for at der kun er én person tilbage og ham kan
>vi give til fanden og sige at vi er færdige.

>Så får vi 1/(2000000) = 1/sqr(pi*t/2) <=> t = 8/pi*10^12 sek

>80693 år

>Ved indsættelse i samme formel findes svaret på dit spørgsmål til
>0,284 person tilbage efter 1 mio år.

>Mvh
>Martin

Smukt. Det ser rigtigt ud. Så mangler jeg bare at finde en
reference til hvor problemet stammer fra. Jeg gætter på at det
er Emile Borel, men jeg kunne ikke finde det ved en kort
bladren i de to første bøger, jeg gættede på. Hvis det er
opgave 417 i en fodnote i upublicerede forelæsningsnoter, så
er det nok som at vente på ham den sidste plattenslager

mvh Birger Nielsen (bnielsen@daimi.au.dk)

---

"Kai Birger Nielsen" <bnielsen@daimi.au.dk> skrev i en meddelelse news:bljnrb$r5t$1@news.net.uni-c.dk...

> Så mangler jeg bare at finde en
> reference til hvor problemet stammer fra.

Jeg har ikke fundet noget - der er utallige referencer til Catalan
tal på nettet. Jeg fandt endnu en handy en med illustrationer
http://www.maths.usyd.edu.au:8000/u/kooc/catalan.html

Catalan-tallene fås af K(2n,n)/(n+1)
1,2,5,14,42, ...
Desværre findes der vist ikke et ultranemt bevis for dem.

Mvh
Martin

---

Martin Larsen wrote:
>
> Jeg har ikke fundet noget - der er utallige referencer til Catalan
> tal på nettet. Jeg fandt endnu en handy en med illustrationer
> http://www.maths.usyd.edu.au:8000/u/kooc/catalan.html
>
> Catalan-tallene fås af K(2n,n)/(n+1)
> 1,2,5,14,42, ...
> Desværre findes der vist ikke et ultranemt bevis for dem.

Savner vi ikke en skelnen mellem Catalan-tal og super-Catalan-tal? De
to forskellige følger findes hos Sloane som
http://www.research.att.com/projects/OEIS?Anum=A000108
http://www.research.att.com/projects/OEIS?Anum=A001003

Det n'te Catalan-tal beskriver antallet af måder hvorpå man efter 2n
slag med mønten kan opnå at der er lige mange plat og krone samtidig
med at der aldrig har været flere plat end krone.

Det n'te super-Catalan-tal beskriver derimod antallet af måder man
efter samme antal slag kan have lige mange plat og krone samtidig med
at der aldrig tidligere (bortset fra efter nul slag) har været flere
**eller lige så mange** plat som krone.

Se også http://mathworld.wolfram.com/SuperCatalanNumber.html


Betragt en mand der bliver ved med at slå med en mønt. Efter et lige
antal slag, nemlig 2n slag, er der en sandsynlighed på

P = 2*S(n)/2^(2n)

for at dette netop er *første* gang der er lige mange plat og krone.
Her betegner S(·) super-Catalan-tallene.

--
Jeppe Stig Nielsen <URL:http://jeppesn.dk/>. «

"Je n'ai pas eu besoin de cette hypothèse (I had no need of that
hypothesis)" --- Laplace (1749-1827)

---

Jeppe Stig Nielsen wrote:
>
> Martin Larsen wrote:
> >
> > Jeg har ikke fundet noget - der er utallige referencer til Catalan
> > tal på nettet. Jeg fandt endnu en handy en med illustrationer
> > http://www.maths.usyd.edu.au:8000/u/kooc/catalan.html
> >
> > Catalan-tallene fås af K(2n,n)/(n+1)
> > 1,2,5,14,42, ...
> > Desværre findes der vist ikke et ultranemt bevis for dem.
>
> Savner vi ikke en skelnen mellem Catalan-tal og super-Catalan-tal? De
> to forskellige følger findes hos Sloane som
> http://www.research.att.com/projects/OEIS?Anum=A000108
> http://www.research.att.com/projects/OEIS?Anum=A001003
>
> Det n'te Catalan-tal beskriver antallet af måder hvorpå man efter 2n
> slag med mønten kan opnå at der er lige mange plat og krone samtidig
> med at der aldrig har været flere plat end krone.
>
> Det n'te super-Catalan-tal beskriver derimod antallet af måder man
> efter samme antal slag kan have lige mange plat og krone samtidig med
> at der aldrig tidligere (bortset fra efter nul slag) har været flere
> **eller lige så mange** plat som krone.

Forkert, jeg læser lige på det igen.

--
Jeppe Stig Nielsen <URL:http://jeppesn.dk/>. «

"Je n'ai pas eu besoin de cette hypothèse (I had no need of that
hypothesis)" --- Laplace (1749-1827)

---

Jeppe Stig Nielsen wrote:
>
> > Det n'te Catalan-tal beskriver antallet af måder hvorpå man efter 2n
> > slag med mønten kan opnå at der er lige mange plat og krone samtidig
> > med at der aldrig har været flere plat end krone.
> >
> > Det n'te super-Catalan-tal beskriver derimod antallet af måder man
> > efter samme antal slag kan have lige mange plat og krone samtidig med
> > at der aldrig tidligere (bortset fra efter nul slag) har været flere
> > **eller lige så mange** plat som krone.
>
> Forkert, jeg læser lige på det igen.

Det var jo noget værre vås jeg kom med dér. Det n'te Catalan-tal er som
jeg beskrev. Antallet af måder hvor det heller ikke må have stået lige
på noget tidspunkt, er blot det (n-1)'te Catalan-tal.

Altså fx er sandsynligheden for at det netop er ved det tyvende slag
med mønten at det første gang er uafgjort, på

P = 2·C(8)/2^20 = 2·4862/2^20 = 4862/2^19 = 2431/262144 = 0,00927

Den første faktor 2 skyldes at det jo også kan være plat der »fører«
hele vejen.

Hvis X betegner den stokastiske variabel der giver nummeret på det
første slag med mønten hvorefter der er lige mange plat og krone,
så gælder

P(X=2n) = 2·C(n-2)/2^(2n) = C(n-2)/2^(2n-1)

(Alt afhængigt af hvordan man indicerer Catalan-tallene.)

Hvis man skal vende tilbage til problemet med de 2000000 mennesker,
skal man så betragte lige så mange uafhængige stokastiske variable
der alle har ovenstående fordeling. Så beskriver Y=max(X_i) det
tidspunkt hvor den sidste person er færdig. Altså er det den typiske
værdi af Y der spørges til.

Ifølge Weisstein http://mathworld.wolfram.com/CatalanNumber.html
formel (9) er den asymptotiske formel for Catalan-tallene noget med
sqrt(pi).

--
Jeppe Stig Nielsen <URL:http://jeppesn.dk/>. «

"Je n'ai pas eu besoin de cette hypothèse (I had no need of that
hypothesis)" --- Laplace (1749-1827)

---

"Jeppe Stig Nielsen" <mail@jeppesn.dk> skrev i en meddelelse news:3F7F1E4D.48D2BFDB@jeppesn.dk...
>
> Ifølge Weisstein http://mathworld.wolfram.com/CatalanNumber.html
> formel (9) er den asymptotiske formel for Catalan-tallene noget med
> sqrt(pi).
>
Ja, jeg brugte den asymptotiske formel og integrerede til oo
Jeg brugte trin à 2 sek og du får nemt som check for
trin 1 og 2 ss: 1/2 og 1/8

Mvh
Martin

---

"Jeppe Stig Nielsen" <mail@jeppesn.dk> skrev i en meddelelse news:3F7F1E4D.48D2BFDB@jeppesn.dk...
>
> Altså fx er sandsynligheden for at det netop er ved det tyvende slag
> med mønten at det første gang er uafgjort, på
>
> P = 2·C(8)/2^20 = 2·4862/2^20 = 4862/2^19 = 2431/262144 = 0,00927
>
Det er vist forkert. Der kommer let noget flimmer eftersom man starter ved
0 eller 1. Og jeg skal vist også rette min egen formel lidt.

Det rigtige er, hvis vi regner i skridt af 2 sek: 2*cat(n-1)/4^n
Hvis vi _vil_ regne med sekunder får vi:
2*cat((int(t/2)-1)/4^(int(t/2))

Cat(n) = (2n)!/n!/(n+1)!
Cat(-1) må vi sætte til 0 (og cat(0)=1).

Mvh
Martin

---

bnielsen@daimi.au.dk (Kai Birger Nielsen) writes:

> In <w5pthgdr9k.fsf@pc-032.diku.dk> torbenm@diku.dk (Torben Ægidius Mogensen) writes:
>
> >bnielsen@daimi.au.dk (Kai Birger Nielsen) writes:
>
> >> Når vi nu i en anden tråd diskuterer pindekast og pi, så
> >> kommer jeg til at tænke på en anden pi-sammenhæng.
> >>
> >> Vi tager 2000000 mennesker og giver dem en mønt hver.
> >> De kaster nu hver for sig plat og krone og forlader
> >> spillet, hvis de på et tidspunkt har fået lige mange
> >> plat og kroner. Hvis vi antager at de kan nå et kast
> >> i sekundet, hvornår er de mon så færdige allesammen ?
>
> >Der er med meget stor sandsynlighed nogen, der aldrig bliver færdige.
>
> >   Torben
>
> Enig, hvis du regner med normal forventet levealder. Ellers
> er jeg ikke enig. Aldrig er lang tid, så hvor mange mener
> du at der er tilbage efter fx en million år ?

Lad os se på sandsynligheden p_n for at man nogensinde når til at have
lige mange plat og krone, hvis man har et overskud på n plat.

p_0 er klart 1.

For n>1 er p_n = 1/2*p_{n-1}+1/2*p_{n+1}. Det kan vi omskrive til at
p_{n+1} = 2p_n-p_{n-1}.

Derfra er det ikke svært at se, at p_n = n*(p_1-1)+1. Da
sandsynligheder ikke kan være negative, må p_1 være 1, og dermed er
p_n = 1 for all n>=0.

Altså vil allesammen have sandsynlighed 1 for at blive færdige. Det
betyder dog ikke, at de med sikkerhed bliver det: Det er faktisk
muligt at de bliver ved uendeligt længe, det udfald har bare
sandsynlighed 0. Når man taler om uendeligt mange mulige udfald
betyder sandsynlighed 0 ikke umulighed.

Lad os så se på det gennemsnitlige antal slag s_n, der skal til at
slippe af med et overskud på n. s_0 er selvfølgelig 0.

Hvis man har et platoverskud på n>0, så har man 50% chance for at slå
krone og dermed blive færdig i 1+s_{n-1} slag. Hvis man slår plat,
har man et overskud på n+1. Men for derfra at komme ned under n, så
skal man først fra n+1 til n. Men at komme fra n+1 til n kræver
præcis det samme antal slag som at komme fra 1 til 0. Så vi kan
opstille ligningen

s_n = 1/2*(1+s_{n-1})+1/2*(1+s_1+s_n)

hvilket efter lidt omregning giver

s_n = 2+2*s_{n-1}+s_1.

Specielt for n=1 har vi

s_1 = 2+2*s_0+s_1 = 2+s_1.

Det giver kun mening hvis s_1 er uendelig. Og hvis s_1 er uendelig,
så er s_n det også for n>1.

Så selv om sandsynligheden for at blive færdig er 1, så tager det i
gennemsnit uendeligt mange slag at blive det!

Men for at løse det egentlige problem, skal vi finde sandsynligheden
p^k_n for at være færdig efter præcis k kast. Af de k kast skal n mere
være krone end plat, så der skal være (k-n)/2 plat og (k-n)/2+n krone.
Hvis (k-n) er ulige findes ingen løsning (det kræver et lige antal
kast at slippe af med et lige overskud).

For alle måder vi kan udtage (k-n)/2 elementer af en k-element mængde
får vi (1/2)^((k-n)/2) * 1/2^((k-n)/2+n) = 1/2^k chance for at de
udvalgte elementer alle er plat og de resterende alle er krone. Antal
måder vi kan udvælge (k-n)/2 elementer er K(k,(k-n)/2) =
k!/((k-n)/2)!/(k-(k-n)/2)! = k!/((k-n)/2)!/((k+n)/2)!.

Hvis n=2m og k=2q, så er sandsynligheden for at være færdig i højest k
slag lig med

sum^q_{i=m}((1/4)^i * (2i)!/(i-m)!/(i+m)!)

Vi kan nu bruge Stirlings approksimation for n! og få

sum^q_{i=m}((1/4)^i
* sqrt(2*pi*2i)*(2i)^(2i)*e^-(2i)
/ (sqrt(2*pi*(i-m))*(i-m)^(i-m)*e^-(i-m))
/ (sqrt(2*pi*(i+m))*(i+m)^(i+m)*e^-(i+m)))
=
sum^q_{i=m}((1/4)^i
* sqrt(2*pi*2i)*(2i)^(2i)
/ (sqrt(2*pi*(i-m))*(i-m)^(i-m)
* sqrt(2*pi*(i+m))*(i+m)^(i+m)))
=
sum^q_{i=m}( sqrt(2i)*i^(2i)
/ (sqrt(2*pi)*sqrt(i^2-m^2)*(i-m)^(i-m)*(i+m)^(i+m)))
=
1/sqrt(pi)* sum^q_{i=m}( i^(2i+1/2)
/ (sqrt(i^2-m^2)*(i^2-m^2)^(i-m)*(i+m)^(2m)))
=
1/sqrt(pi)* sum^q_{i=m}(i^(2i+1/2)/((i^2-m^2)^(i-m+1/2)*(i+m)^(2m)))

Hvilket jeg ikke umiddelbart kan reducere mere.

   Torben

---

In <w5smmbztr2.fsf@pc-032.diku.dk> torbenm@diku.dk (Torben Ægidius Mogensen) writes:

>bnielsen@daimi.au.dk (Kai Birger Nielsen) writes:

>> In <w5pthgdr9k.fsf@pc-032.diku.dk> torbenm@diku.dk (Torben Ægidius Mogensen) writes:
>>
>> >bnielsen@daimi.au.dk (Kai Birger Nielsen) writes:
>>
>> >> Når vi nu i en anden tråd diskuterer pindekast og pi, så
>> >> kommer jeg til at tænke på en anden pi-sammenhæng.
>> >>
>> >> Vi tager 2000000 mennesker og giver dem en mønt hver.
>> >> De kaster nu hver for sig plat og krone og forlader
>> >> spillet, hvis de på et tidspunkt har fået lige mange
>> >> plat og kroner. Hvis vi antager at de kan nå et kast
>> >> i sekundet, hvornår er de mon så færdige allesammen ?
>>
>> >Der er med meget stor sandsynlighed nogen, der aldrig bliver færdige.
>>
>> >   Torben
>>
>> Enig, hvis du regner med normal forventet levealder. Ellers
>> er jeg ikke enig. Aldrig er lang tid, så hvor mange mener
>> du at der er tilbage efter fx en million år ?

>Lad os se på sandsynligheden p_n for at man nogensinde når til at have
>lige mange plat og krone, hvis man har et overskud på n plat.

>p_0 er klart 1.

Jeg tror at alle p_i'er er 1.

>For n>1 er p_n = 1/2*p_{n-1}+1/2*p_{n+1}. Det kan vi omskrive til at
>p_{n+1} = 2p_n-p_{n-1}.

>Derfra er det ikke svært at se, at p_n = n*(p_1-1)+1. Da
>sandsynligheder ikke kan være negative, må p_1 være 1, og dermed er
>p_n = 1 for all n>=0.

>Altså vil allesammen have sandsynlighed 1 for at blive færdige. Det
>betyder dog ikke, at de med sikkerhed bliver det: Det er faktisk
>muligt at de bliver ved uendeligt længe, det udfald har bare
>sandsynlighed 0. Når man taler om uendeligt mange mulige udfald
>betyder sandsynlighed 0 ikke umulighed.

nemlig.

Jeg er ikke sikker på at det er sundt at regne alt for håndfast
på det gennemsnitlige antal slag, når der er en mulighed for at
nogle af slagserierne er meget meget lange. I alt fald kan man
komme igennem med regnerier på hvor mange der overlever fra gang
til gang. Det er muligt at dine regnerier giver samme resultat,
men det kan jeg ikke lige gennemskue.

mvh Birger Nielsen (bnielsen@daimi.au.dk)

---

Kai Birger Nielsen wrote:
>
> Når vi nu i en anden tråd diskuterer pindekast og pi, så
> kommer jeg til at tænke på en anden pi-sammenhæng.
>
> Vi tager 2000000 mennesker og giver dem en mønt hver.
> De kaster nu hver for sig plat og krone og forlader
> spillet, hvis de på et tidspunkt har fået lige mange
> plat og kroner. Hvis vi antager at de kan nå et kast
> i sekundet, hvornår er de mon så færdige allesammen ?

>
> Sammenhængen med pi overlades som en øvelse til læserne

Jeg kan ikke lige overskue det, men ifølge den allernederste formel
på http://mathworld.wolfram.com/RandomWalk1-Dimensional.html vil
den forventede (numeriske) forskel mellem antal plat og antal krone
efter N kast være (asymptotisk) sqrt(2N/pi) , og det er da noget med
pi ...

Er der nogen grund til at dit tal 2000000 er på formen 2·k² = ½·(2k)² ?

--
Jeppe Stig Nielsen <URL:http://jeppesn.dk/>. «

"Je n'ai pas eu besoin de cette hypothèse (I had no need of that
hypothesis)" --- Laplace (1749-1827)

---

In <3F7C2FE2.1286B398@jeppesn.dk> Jeppe Stig Nielsen <mail@jeppesn.dk> writes:

>Kai Birger Nielsen wrote:
>>
>> Når vi nu i en anden tråd diskuterer pindekast og pi, så
>> kommer jeg til at tænke på en anden pi-sammenhæng.
>>
>> Vi tager 2000000 mennesker og giver dem en mønt hver.
>> De kaster nu hver for sig plat og krone og forlader
>> spillet, hvis de på et tidspunkt har fået lige mange
>> plat og kroner. Hvis vi antager at de kan nå et kast
>> i sekundet, hvornår er de mon så færdige allesammen ?

>>
>> Sammenhængen med pi overlades som en øvelse til læserne

>Jeg kan ikke lige overskue det, men ifølge den allernederste formel
>på http://mathworld.wolfram.com/RandomWalk1-Dimensional.html vil
>den forventede (numeriske) forskel mellem antal plat og antal krone
>efter N kast være (asymptotisk) sqrt(2N/pi) , og det er da noget med
>pi ...

Ja, jeg tror faktisk det har noget med sagen at gøre.

>Er der nogen grund til at dit tal 2000000 er på formen 2·k² =
½·(2k)² ?

Nej, det tror jeg ikke. Tallet er taget fra den artikel, hvor jeg
fandt opgaven (og den efter min mening suspekte henvisning til
hvor den oprindeligt kommer fra).

mvh Birger Nielsen (bnielsen@daimi.au.dk)

---

Kai Birger Nielsen wrote:
>
> Vi tager 2000000 mennesker og giver dem en mønt hver.
> De kaster nu hver for sig plat og krone og forlader
> spillet, hvis de på et tidspunkt har fået lige mange
> plat og kroner. Hvis vi antager at de kan nå et kast
> i sekundet, hvornår er de mon så færdige allesammen ?

Først sikrer jeg mig at jeg ikke forvirrer mig selv igen med indeks
til Catalan-tallene. Jeg lader

C(-1) = -1/2
C(0) = 1
C(1) = 1
C(2) = 2
C(3) = 5
C(4) = 14
C(5) = 42
etc.

Med denne konvention for Catalan-tallenes indeks n gælder
C(n)=binomial(2n,n)/(n+1).

Antallet af måder hvorpå plat og krone kan stå lige efter 2n kast så-
ledes at plat aldrig har ført, er så C(n).

Og antallet af måder hvorpå plat og krone kan stå lige efter 2n kast
således at plat aldrig har ført eller været oppe på siden af krone før,
er C(n-1).

Derfor er antallet af måder hvorpå det (2n)'te kast kan være første
gang stillingen er lige, på 2·C(n-1).

Lad X være den stokastiske variabel der giver nummeret på det første slag
med mønten hvor plat og krone står lige. Så er fordelingen af X

P(X=2n) = 2·C(n-1)/2^(2n) = C(n-1)/2^(2n-1)

Og så

P(X<=2n) = sum_{i=1}^{n} C(i-1)/2^(2i-1)

Kan denne (endelige) rækkes sum skrives pænt?

Vi betragter nu N personer (N=2000000 fx). Lad X1, X2, ..., XN være
uafhængige stokastiske variable der alle har fordelingen for X herover.
Lad Y=max(Xi) være den største af dem. Da betegner Y netop det antal
sekunder der spørges til. Så er fordelingen for Y givet ved

P(Y<=2n) = P(X1<=2n og X2<=2n og ... og XN<=2n)

= P(X1<=2n)·P(X2<=2n)·...·P(XN<=2n)

= ( sum_{i=1}^{n} C(i-1)/2^(2i-1) )^N

Man kan også finde P(Y=2n) ved at sige P(Y=2n) = P(Y<=2n)-P(Y<=2(n-1)).

Ønsker man forventningsværdien for Y (der som bekendt ikke siger ret
meget om Y), skal man udregne

E(Y) = sum_{i=1}^{uendelig} i·P(Y=i)

= sum_{i=1}^{uendelig} sum_{j=1}^{i} P(Y=i)

= sum_{j=1}^{uendelig} sum_{i=j}^{uendelig} P(Y=i)

= sum_{j=1}^{uendelig} P(Y>=j)

= sum_{j=0}^{uendelig} P(Y>j)

hvilket som bekendt gælder for alle heltallige positive stokastiske
variable. Leddet P(Y>j) = 1-P(Y<=j) kan udregnes af den formel jeg gav
herover.

Den der har noget matematiksoftware/CAS ved hånden, kan lige smide nogle
tal på bordet ...

--
Jeppe Stig Nielsen <URL:http://jeppesn.dk/>. «

"Je n'ai pas eu besoin de cette hypothèse (I had no need of that
hypothesis)" --- Laplace (1749-1827)

---

Jeppe Stig Nielsen wrote:
> Lad X være den stokastiske variabel der giver nummeret på det første slag
> med mønten hvor plat og krone står lige. Så er fordelingen af X
>
> P(X=2n) = 2·C(n-1)/2^(2n) = C(n-1)/2^(2n-1)
>
> Og så
>
> P(X<=2n) = sum_{i=1}^{n} C(i-1)/2^(2i-1)
>
> Kan denne (endelige) rækkes sum skrives pænt?

Det er det samme som:

1 - K(2n-1,n-1)/2^(2n-1)

Jeg fandt ud af det ved at skrive de første
fire tal (1, 5, 22, 93) af følgen

2^(2n-1) * sum_{i=1}^{n} C(i-1)/2^(2i-1)

ind på "Online Encyclopedia of Integer Sequences".
(Efter først at have bandet over at summationsvariablen var
at finde både for oven og for neden i binomialkoeffecienten.)

Lommeregneren bekræfter, at de efterfølgende tal i følgen passer.

--
Jens Axel Søgaard

---

Det her er jo nydeligt. I har regnet ud at
P(X=2n) = 2·C(n-1)/2^(2n) = C(n-1)/2^(2n-1)

Dvs for at sætte lidt tal på
P(game over i netop det 2. kast) = 2*c(0)/2^2 = 2 måder ud af 4
tilsammen 2 måder ud af 4
P(game over i netop det 4. kast) = 2*c(1)/2^4 = 2 måder ud af 16
tilsammen 10 måder ud af 16
P(game over i netop det 6. kast) = 2*c(2)/2^6 = 4 måder ud af 64
tilsammen 44 måder ud af 64
P(game over i netop det 8. kast) = 2*c(3)/2^8 = 10 måder ud af 256
tilsammen 186 måder ud af 256
P(game over i netop det 10.kast) = 2*c(4)/2^10 = 28 måder ud af 1024
tilsammen 772 måder ud af 1024.

Generelt kommer man fra 2,10,44,186... videre ved at gange med 4
og lægge 2 * det næste catalanske tal til. Og der dukkede
endda også en direkte formel op, så problemet er hermed lagt i
graven

Man kan også se det på en anden måde. Efter 2. kast er 1/2 tilbage.
Af disse 2 er der 3/4, der overlever 4. kast. 5/6, der overlever
6. kast. 7/8, der overlever 8.kast og 9/10, der overlever 10.kast.
Dvs efter 10 kast er det 1*3*5*7*9/(2*4*6*8*10) = 945/3840,
hvilket er præcis 252/1024.

Og resterne fra ovenfor kan man skrive som
2/4, 6/10, 20/64, 70/256, 252/1024, ...
så pengene passer.

mvh Birger Nielsen (bnielsen@daimi.au.dk)

---

"Kai Birger Nielsen" <bnielsen@daimi.au.dk> skrev i en meddelelse news:blrkmm$p7g$1@news.net.uni-c.dk...
> Det her er jo nydeligt. I har regnet ud at
>
> Og resterne fra ovenfor kan man skrive som
> 2/4, 6/10, 20/64, 70/256, 252/1024, ...
> så pengene passer.
Øh 6/16
>
Og det er jo K(2n,n)/4^n

Mvh
Martin

---

In <3f815cfe$0$32501$edfadb0f@dread16.news.tele.dk> "Martin Larsen" <mlarsen@post7.tele.dk> writes:


>"Kai Birger Nielsen" <bnielsen@daimi.au.dk> skrev i en meddelelse news:blrkmm$p7g$1@news.net.uni-c.dk...
>> Det her er jo nydeligt. I har regnet ud at
>>
>> Og resterne fra ovenfor kan man skrive som
>> 2/4, 6/10, 20/64, 70/256, 252/1024, ...
>> så pengene passer.
>Øh 6/16

Ja, det var en slåfejl.

>Og det er jo K(2n,n)/4^n

Ja. Er man nødt til at regne eller er det på en eller anden
måde indlysende ? De 2^(2n) er selvfølgelig, så det er de
K(2n,n), der ser besnærende ud som om man burde kunne sige
sig selv at det lige var det. På den anden side giver mit
produkt jo (2n)!/(2^n*n!)^2 og det er jo trivielt at skrive
det om til K(2n,n)/2^(2n), så det kan være at det bare er
held at notationen lige rammer plet her ?

Hvis man bruger Stirling's tilnærmelse
n! =~ (n/e)^n * sqrt(2*pi*n)
får man at K(2n,n)/2^(2n) =~ 1/sqrt(pi/n)

mvh Birger Nielsen (bnielsen@daimi.au.dk)

---

"Kai Birger Nielsen" <bnielsen@daimi.au.dk> skrev i en meddelelse news:bltnuj$pf7$1@news.net.uni-c.dk...
>
> >Og det er jo K(2n,n)/4^n
>
> Ja. Er man nødt til at regne eller er det på en eller anden
> måde indlysende ? De 2^(2n) er selvfølgelig, så det er de
> K(2n,n), der ser besnærende ud som om man burde kunne sige
> sig selv at det lige var det. På den anden side giver mit
> produkt jo (2n)!/(2^n*n!)^2 og det er jo trivielt at skrive
> det om til K(2n,n)/2^(2n), så det kan være at det bare er
> held at notationen lige rammer plet her ?
>
Jeg synes jo at det uklare ligger i hvordan dit produkt fremkommer,
selvom jeg ikke anfægter dets korrekthed.

Du spørger vist om hvorledes man kommer fra dit produkt til
(2n)!/n!/n!/4^n

Skriv dit produkt som (2n-1)!!/n!/2^n
Gang igennem med n!n!4^n
Er 2^n*n!(2n-1)!! = (2n)!
Ja, se:
http://mathworld.wolfram.com/DoubleFactorial.html nummer 6

> Hvis man bruger Stirling's tilnærmelse
> n! =~ (n/e)^n * sqrt(2*pi*n)
> får man at K(2n,n)/2^(2n) =~ 1/sqrt(pi/n)
>
Du mener 1/sqrt(n*pi)

Mvh
Martin

---

"Martin Larsen" <mlarsen@post7.tele.dk> skrev i en meddelelse news:3f82a32b$0$32447$edfadb0f@dread16.news.tele.dk...
> Ja, se:
> http://mathworld.wolfram.com/DoubleFactorial.html nummer 6
>
Nummer 8

Mvh
Martin

---

In <3f82a32b$0$32447$edfadb0f@dread16.news.tele.dk> "Martin Larsen" <mlarsen@post7.tele.dk> writes:

>"Kai Birger Nielsen" <bnielsen@daimi.au.dk> skrev i en meddelelse news:bltnuj$pf7$1@news.net.uni-c.dk...
>>
>> >Og det er jo K(2n,n)/4^n
>>
>> Ja. Er man nødt til at regne eller er det på en eller anden
>> måde indlysende ? De 2^(2n) er selvfølgelig, så det er de
>> K(2n,n), der ser besnærende ud som om man burde kunne sige
>> sig selv at det lige var det. På den anden side giver mit
>> produkt jo (2n)!/(2^n*n!)^2 og det er jo trivielt at skrive
>> det om til K(2n,n)/2^(2n), så det kan være at det bare er
>> held at notationen lige rammer plet her ?
>>
>Jeg synes jo at det uklare ligger i hvordan dit produkt fremkommer,
>selvom jeg ikke anfægter dets korrekthed.

Det kan der være noget om.

>Du spørger vist om hvorledes man kommer fra dit produkt til
>(2n)!/n!/n!/4^n

Nej, det var klart nok. Det er mindre klart om man kan se
at løsningen på det oprindelige problem er K(2n,n)/4^n direkte
uden at regne på catalan-tal og hvilke omveje vi ellers er gået.

>> Hvis man bruger Stirling's tilnærmelse
>> n! =~ (n/e)^n * sqrt(2*pi*n)
>> får man at K(2n,n)/2^(2n) =~ 1/sqrt(pi/n)
>>
>Du mener 1/sqrt(n*pi)

Ak. Endnu en typo. Ja, du har naturligvis ret.

mvh Birger Nielsen (bnielsen@daimi.au.dk)