---

Jeg så lige en matematikkonkurrence i SIAM News.

Der er ti små opgaver, hvor løsningen på hver af dem er et reelt tal.
Man skal så finde svaret med ti betydende cifre -- et point for hvert
rigtigt ciffer. Den med flest point vinder $100.

Det kan jo være at nogle af læserne her trænger til at lege med en lille
udfordring:

<http://www.siam.org/siamnews/01-02/challenge.pdf>

---

Jesper Harder wrote:
>
> Jeg så lige en matematikkonkurrence i SIAM News.
>
> <http://www.siam.org/siamnews/01-02/challenge.pdf>

Bvadr! Jeg synes jeg har set 2'eren før et sted. Den ville være noget
behageligere hvis fotonen startede med at bevæge sig mod stik nord ...

6'ere, den med loppen på Z×Z, er sjov nok. Hvad er det nu sandsyn-
ligheden for at komme tilbage er hvis epsilon=0? Åbenbart større end
1/2.

--
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:

> Bvadr! Jeg synes jeg har set 2'eren før et sted. Den ville være noget
> behageligere hvis fotonen startede med at bevæge sig mod stik nord ...

Ha, ha...


> 6'ere, den med loppen på Z×Z, er sjov nok. Hvad er det nu sandsyn-
> ligheden for at komme tilbage er hvis epsilon=0? Åbenbart større end
> 1/2.

Øhh... den er da præcist 1. Er det ikke et standard eksempel ?

Men i øvrigt: Er der noget i vejen for, at man kører en slags Newtons
metode på dét problem ?

-Claus

---

Claus Rasmussen wrote:
>
> > 6'ere, den med loppen på Z×Z, er sjov nok. Hvad er det nu sandsyn-
> > ligheden for at komme tilbage er hvis epsilon=0? Åbenbart større end
> > 1/2.
>
> Øhh... den er da præcist 1. Er det ikke et standard eksempel ?

Præcis 1, det kan godt være. Det gælder i hvert fald i én dimension.

Jo, det er et standard-eksempel, jeg kan bare ikke huske det.

Nå, her står det jo:
http://mathworld.wolfram.com/RandomWalk1-Dimensional.html
http://mathworld.wolfram.com/RandomWalk2-Dimensional.html
http://mathworld.wolfram.com/RandomWalk3-Dimensional.html

Det er åbenbart først i tre dimensioner at sandsynligheden for at
vende tilbage til udgangspunkt bliver under 1.

>
> Men i øvrigt: Er der noget i vejen for, at man kører en slags Newtons
> metode på dét problem ?

Hvad mener du med Newtons metode?

--
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:

> Nå, her står det jo:
> http://mathworld.wolfram.com/RandomWalk1-Dimensional.html
> http://mathworld.wolfram.com/RandomWalk2-Dimensional.html
> http://mathworld.wolfram.com/RandomWalk3-Dimensional.html

Det er altså nogle super sider.

[...]

>> Men i øvrigt: Er der noget i vejen for, at man kører en slags Newtons
>> metode på dét problem ?
>
> Hvad mener du med Newtons metode?

Ved nærmere eftertanke: Glem Newton

Forestil dig i stedet at vi har en simulationsalgoritme, der for et
givet epsilon kører problemet mange skridt mange gange og som giver
sandsynligheden for at vende tilbage til nulpunktet.

Så kan vi lave et program som dette:

e := 1; // Epsilon
p := 0.0; // Sandsynlighed
sålænge p != 0.5
hvis p > 0.5 så
gør e større
ellers
gør e mindre
sluthvis
p := algoritme(e);
slutså

....hvis altså problemet ikke er noget kaoslignende fnadder.

-Claus

---

Claus Rasmussen wrote:
>
> Forestil dig i stedet at vi har en simulationsalgoritme, der for et
> givet epsilon kører problemet mange skridt mange gange og som giver
> sandsynligheden for at vende tilbage til nulpunktet.

Jo, men hvor længe vil du lade den køre hver gang? Selvom den ikke er
vendt tilbage efter en milliard skridt, kan den jo stadig nå det.

>
> Så kan vi lave et program som dette:
>
> e := 1; // Epsilon
> p := 0.0; // Sandsynlighed
> sålænge p != 0.5
> hvis p > 0.5 så
> gør e større
> ellers
> gør e mindre
> sluthvis
> p := algoritme(e);
> slutså
>
> ...hvis altså problemet ikke er noget kaoslignende fnadder.

Problemet ligger i at finde p når epsilon er valgt.

Umiddelbart er problemet med fotonen og alle spejlene da meget lettere.
Det er jo helt deterministisk. Det må da være nogenlunde let?

--
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:

> Claus Rasmussen wrote:
>>
>> Forestil dig i stedet at vi har en simulationsalgoritme, der for et
>> givet epsilon kører problemet mange skridt mange gange og som giver
>> sandsynligheden for at vende tilbage til nulpunktet.
>
> Jo, men hvor længe vil du lade den køre hver gang? Selvom den ikke er
> vendt tilbage efter en milliard skridt, kan den jo stadig nå det.

Jeg mener: Hvis nu vi sætter en overgrænse på f.eks 1000 skridt og
beregner vores sandsynlighed ud fra det. Så vil vi få en værdi, der
ligger i nærheden af den virkelige værdi (hvis det altså er liniært).


>> Så kan vi lave et program som dette:
>>
>> e := 1; // Epsilon
>> p := 0.0; // Sandsynlighed
>> sålænge p != 0.5
>> hvis p > 0.5 så
>> gør e større
>> ellers
>> gør e mindre
>> sluthvis
>> p := algoritme(e);
>> slutså
>>
>> ...hvis altså problemet ikke er noget kaoslignende fnadder.
>
> Problemet ligger i at finde p når epsilon er valgt.

Nej problemet siger "p=0.5, hvad er epsilon" ?


> Umiddelbart er problemet med fotonen og alle spejlene da meget lettere.
> Det er jo helt deterministisk. Det må da være nogenlunde let?

Det er helt forfærdeligt. Du bliver nødt til at bruge reelle tal i din
simulation og de har en begrænset præcision. Den manglende præcision vil
blive pustet op af alle de runde spejle, så du til sidst ikke har nogen
anelse om, hvor fotonen befinder sig.

-Claus

---

Claus Rasmussen wrote:
>
> > Problemet ligger i at finde p når epsilon er valgt.
>
> Nej problemet siger "p=0.5, hvad er epsilon" ?

Jo jo, men problemet med *dit forslag* ligger i det du har kaldt
algoritme(). Altså, det er klart at hvis algoritme() kunne fungere
nogenlunde, så ville man kunne bruge en slags bisektionsmetode a la
den du foreslår.

>
> > Umiddelbart er problemet med fotonen og alle spejlene da meget lettere.
> > Det er jo helt deterministisk. Det må da være nogenlunde let?
>
> Det er helt forfærdeligt. Du bliver nødt til at bruge reelle tal i din
> simulation og de har en begrænset præcision. Den manglende præcision vil
> blive pustet op af alle de runde spejle, så du til sidst ikke har nogen
> anelse om, hvor fotonen befinder sig.

Så kan du jo bare kigge på 7'eren, der er ingen reelle tal i den.
Det er bare inversion af en kvadratisk matrix med heltalsindgange.

Jeg synes det er svagt bare at kræve svaret til 7'eren med ti decimaler.
Man kan vel bare give svaret som en uforkortelig brøk

7'eren er den eneste hvor det er indlysende at svaret er rationalt.
(Hvis altså svaret eksisterer ...)

--
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)

---

Claus Rasmussen <clr@cc-consult.dk> writes:

> Jeppe Stig Nielsen wrote:
>
>> Claus Rasmussen wrote:
>>>
>>> Forestil dig i stedet at vi har en simulationsalgoritme, der for et
>>> givet epsilon kører problemet mange skridt mange gange og som giver
>>> sandsynligheden for at vende tilbage til nulpunktet.
>>
>> Jo, men hvor længe vil du lade den køre hver gang? Selvom den ikke er
>> vendt tilbage efter en milliard skridt, kan den jo stadig nå det.
>
> Jeg mener: Hvis nu vi sætter en overgrænse på f.eks 1000 skridt

Problemet er at 1000 skridt slet ikke er nok. Jeg prøvede lige at køre
100 simulationer for epsilon=0 med en øvre grænse på 300 millioner
skridt i hver af dem.

85 af de 100 forsøg vendte tilbage til nulpunktet indenfor grænsen; men
vi ved jo at den eksakte sandsynlighed er 1 (når epsilon=0). Hvis vi
satser på ti betydende cifre, er 300 mio. skridt altså alt, alt for
lidt.

Jeg tvivler lidt på man kan løse problemet ved bare at smide rå
computerkraft efter det. Man bliver nok nødt til at udtænke noget mere
snedigt og *så* kaste noget computerkraft efter det

---

Jesper Harder wrote:

> Claus Rasmussen <clr@cc-consult.dk> writes:
>
>> Jeg mener: Hvis nu vi sætter en overgrænse på f.eks 1000 skridt
>
> Problemet er at 1000 skridt slet ikke er nok. Jeg prøvede lige at køre
> 100 simulationer for epsilon=0 med en øvre grænse på 300 millioner
> skridt i hver af dem.
>
> 85 af de 100 forsøg vendte tilbage til nulpunktet indenfor grænsen; men
> vi ved jo at den eksakte sandsynlighed er 1 (når epsilon=0). Hvis vi
> satser på ti betydende cifre, er 300 mio. skridt altså alt, alt for
> lidt.

Ok. Jeg var vist lidt for optimistisk, kan jeg se Jeg lavede lidt
hovedregning på 1D simulationen: Efter to skridt er 50% tilbage i nul
og efter 4 skridt er 62.5% tilbage i nul, så jeg tænkte at det nok var
noget i samme stil, hvis man kørte det i 2D.


> Jeg tvivler lidt på man kan løse problemet ved bare at smide rå
> computerkraft efter det. Man bliver nok nødt til at udtænke noget mere
> snedigt og *så* kaste noget computerkraft efter det

Ja. Det er sikkert også det, der er pointen med opgaven.

-Claus

---

Jesper Harder wrote:
>
> Problemet er at 1000 skridt slet ikke er nok. Jeg prøvede lige at køre
> 100 simulationer for epsilon=0 med en øvre grænse på 300 millioner
> skridt i hver af dem.
>
> 85 af de 100 forsøg vendte tilbage til nulpunktet indenfor grænsen; men
> vi ved jo at den eksakte sandsynlighed er 1 (når epsilon=0). Hvis vi
> satser på ti betydende cifre, er 300 mio. skridt altså alt, alt for
> lidt.

Mon ikke middelværdien af ventetiden på første tilbagekomst til
udgangspunktet, er uendelig? Det kunne jeg forestille mig.

--
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)

---

Claus Rasmussen <clr@cc-consult.dk> writes:

> Jesper Harder wrote:
>
>> Claus Rasmussen <clr@cc-consult.dk> writes:
>>
>>> Jeg mener: Hvis nu vi sætter en overgrænse på f.eks 1000 skridt
>>
>> Problemet er at 1000 skridt slet ikke er nok. Jeg prøvede lige at køre
>> 100 simulationer for epsilon=0 med en øvre grænse på 300 millioner
>> skridt i hver af dem.
>>
>> 85 af de 100 forsøg vendte tilbage til nulpunktet indenfor grænsen; men
>> vi ved jo at den eksakte sandsynlighed er 1 (når epsilon=0). Hvis vi
>> satser på ti betydende cifre, er 300 mio. skridt altså alt, alt for
>> lidt.
>
> Ok. Jeg var vist lidt for optimistisk, kan jeg se

Hmm, det ser ud til at det er meget værre når epsilon=0, end når epsilon
bliver lidt større.

<http://ifa.au.dk/~harder/flea.png> viser sandsynligheden som funktion
af epsilon for 100 skridt og 5000 skridt. Så man har sikkert ikke brug
for så astromisk mange skridt i den omegn hvor p(epsilon) = ½.

Men hvis vi vil have ti betydende cifre på epsilon, skal vi sikkert
mindst bruge den samme præcision på p. Det vil sige at man skal køre
omkring 10^19 simulationer for hver epsilon-værdi. Det kunne hurtigt
begynde at tage lang tid

---

Jesper Harder wrote:
>
> <http://ifa.au.dk/~harder/flea.png> viser sandsynligheden som funktion
> af epsilon for 100 skridt og 5000 skridt. Så man har sikkert ikke brug
> for så astromisk mange skridt i den omegn hvor p(epsilon) = ½.

Hmmm, Netscape 4 viser hverken akserne eller signaturforklaringen. Det
går bedre med andre programmer. Blot til evt. andre brugere af Netscape.

--
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:
>
> Jesper Harder wrote:
> >
> > <http://ifa.au.dk/~harder/flea.png> viser sandsynligheden som funktion
> > af epsilon for 100 skridt og 5000 skridt. Så man har sikkert ikke brug
> > for så astromisk mange skridt i den omegn hvor p(epsilon) = ½.
>
> Hmmm, Netscape 4 viser hverken akserne eller signaturforklaringen. Det
> går bedre med andre programmer. Blot til evt. andre brugere af Netscape.

1 point ud af de 100 til Harder for at have vist at epsilon=0,06.

Hvad sker der i øvrigt hvis man gør problemet éndimensionalt, altså
forhindrer hop mod nord og syd?

--
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> writes:

> Jeppe Stig Nielsen wrote:
>>
>> Jesper Harder wrote:
>> >
>> > <http://ifa.au.dk/~harder/flea.png> viser sandsynligheden som
>> > funktion af epsilon for 100 skridt og 5000 skridt. Så man har
>> > sikkert ikke brug for så astronomisk mange skridt i den omegn hvor
>> > p(epsilon) = ½.
>>
>> Hmmm, Netscape 4 viser hverken akserne eller
>> signaturforklaringen. Det går bedre med andre programmer. Blot til
>> evt. andre brugere af Netscape.

Skal du ikke snart have opgraderet det gamle skrammel til Mozilla?

> 1 point ud af de 100 til Harder for at have vist at epsilon=0,06.

Jeg tør også godt byde på næste ciffer: epsilon = 0,061.

Man kunne sikkert godt få et par cifre mere med den "naive" metode, men
der ikke så meget fremtid i den, hvis man vil op på ti cifre.

---

Jesper Harder wrote:
>
> Skal du ikke snart have opgraderet det gamle skrammel til Mozilla?

Jeg bruger også Mozilla og Netscape 6 indimellem. De kan vise flere
sider korrekt, men de crasher altså også jævnligt.
(Netscape 4 er heller ikke altid stabil; den »fryser«.)

--
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)

---

Jesper Harder <harder@myrealbox.com> writes:

> Jeppe Stig Nielsen <mail@jeppesn.dk> writes:
>
> [opgave 6]
>
>> 1 point ud af de 100 til Harder for at have vist at epsilon=0,06.
>
> Jeg tør også godt byde på næste ciffer: epsilon = 0,061.

Juhu! Det viste sig at være rigtigt. Hvis man er interesseret i at se,
hvordan folk har løst dem, er der links til forskellige løsninger på:

<http://web.comlab.ox.ac.uk/oucl/work/nick.trefethen/hundred.html>

(bl.a. kunne opgave 6 åbenbart løses vha. et smart elliptisk integrale).

---

Jesper Harder wrote:

> <http://web.comlab.ox.ac.uk/oucl/work/nick.trefethen/hundred.html>

Jeg kan stadig ikke komme mig over, at de faktisk løste opgave 2 med et
simulationsprogram. Og eet af dem endda i BASIC !!

For meget.

-Claus