Random getallen

[PeterPan]

Ik laat een computer random getallen genereren (getallen uniform tussen 0 en 1).

De gegenereerde getallen tel ik op totdat hun som minstens 1 is.

Hoe veel getallen zal de computer daarvoor naar verwachting nodig hebben?

[jhnbk]

Ik denk 3, en mijn computer bevestigd dat, ik zie enkel niet hoe ik tot het resultaat zou kunnen komen.

De kans om met 3 getallen al een som te hebben groter dan 1 is benaderend

\(\frac78\)

[PeterPan]

Ik denk 3, en mijn computer bevestigd dat, ik zie enkel niet hoe ik tot het resultaat zou kunnen komen.

Dat lijkt me niet juist.

De kans om met 3 getallen al een som te hebben groter dan 1 is benaderend

\(\frac78\)

of

\(\frac56\)

[stoker]

zo simpel zal het waarschijnlijk niet zijn, maar ik denk:

1/2 is de verwachte waarde van elk getal, na twee keer trekken is je verwachte waarde 1

dus 2?

[jhnbk]

Dan heb je in ongeveer 50% van de gevallen een getal groter dan 1. Daarmee dat ik dacht dat dit niet volstond.

[A.Square]

Je moet het zoeken in de exponentiele verdeling.

Het blijkt zo te zijn dat de verschillen tussen uniform verdeelde stochasten exponentieel verdeeld zijn.

Dus wanneer je getallen

\(x_{(1)}, x_{(2)}, ... , x_{(n)}\)

uit de uniforme[0,1]-verdeling trekt geldt dat

\(x_{(i+1)}-c_{(i)}\)

verdeeld is als Exp(n).

En nu moet het gemiddelde van de som van de verschillen 1 opleveren.

nb: met

\(x_{(i)}\)

bedoel ik het i-de element van de gesorteerde verzameling trekkingen. Ofwel de i-de 'order statistic'

[Schwartz]

(nog een keer: er ging technisch iets fout waardoor ik het vorige bericht niet kon editen!)

Tussen: is dat >0 en <1 ???

En minstens 1 betekent dat de computer/formule stopt wanneer de som>1 is.

Omdat de randomgenerator niet oneindig is bekomen we bij >0 en <1 aan beide zijden een verschil die dan onwetend is omdat we de informatie van de random generator niet kennen.

(voor een computer, bij wiskunde kan men hiervoor dan oneindig aantal nemen)

Bij een stupide randomgenerator die maar 1 random getal kan leveren tussen 0 en 1, zeg 0.5 zou men altijd 3 keer een resultaat moeten hebben.

0.5 +0.5 =1.

Dat is niet groter dan 1.

Plus 0.5 is 1.5 en we hebben 3 keer een 'randomgetal getrokken.

[jhnbk]

@A.Square: kan je de volledige uitwerking geven, want ik zie niet waar je naartoe wilt.

[Schwartz]

Ik bekom als antwoord: 2.7

Met deze routine in pascal:

procedure TForm1.Button1Click(Sender: TObject);

var r:longint;

var rs:longint;

var x,y:longint;

var t,sum:longint;

var e:extended;

Var s:string;

begin

{-REMARK}

sum:=0;

for y:=1 to 10000 do begin

rs:=0;

t:=0;

for x:=1 to 1000 do begin

inc(t);r:=random(100000)+1;

rs:=rs+r;

if rs>=100000 then begin break;END;

END;

sum:=sum+t;

end;

E:=sum;

E:=E/10000;

str(E:10,S);

form1.memo1.Lines.add('gemiddelde: '+ S);

end;

[jhnbk]

2,7 had ik ook in python, daarmee ik 3 geantwoord heb en hiervoor een benaderende kans heb gegeven.

[PeterPan]

Ik heb wel een oplossing, maar ik denk dat er een eenvoudiger oplossing te geven is.

Bekijk eerst 2 random getallen

\(x_1\)

en

\(x_2\)

.

Wat is de kans dat

\(x_1+x_2>1\)

?

Bekijk daartoe het vierkant van 1 bij 1, waar we de trekking als

\((x_1,x_2)\)

-waarde grafisch weergeven.

Nu komt het gebied

\(x_1+x_2\leq 1\)

overeen met het halve vierkant.

Dus

\(P(x_1+x_2\leq 1) = \frac12\)

.

Nu 3 random getallen

\(x_1,x_2,x_3\)

.

We tekenen de waarden als punten

\((x_1,x_2,x_3)\)

in een kubus met zijden 1.

De kans is de oppervlakte onder de grafiek

\(x_3 = 1-x_2-x_1\)

, dus

\(P(x_1+x_2+x_3\leq 1) = \int_0^1 \int_1^{1-x_1} 1-x_1-x_2 \; dx_2\; dx_1 = (1-x_1)x_2 - \frac12 x_2^2|_0^1 = \frac16\)

.

Ik heb nu het vermoeden dat

\(P(\sum_{i=1}^n x_i \leq 1) = \frac{1}{n!}\)

.

Dan is automatisch (vermenigvuldigingsfactor

\(r\)

in

\(n\)

dimensionele ruimte):

\(P(\sum_{i=1}^n x_i \leq r) = \frac{r^n}{n!}\)

.

Bewijs:

Met volledige inductie. Stel juist voor

\(n=m\)

.

Dan willen we de oppervlakte berekenen onder de grafiek van

\(x_1+x_2+\cdots + x_{m+1} = 1\)

.

Dan is

\(x_1+x_2+\cdots + x_m = 1-x_{m+1}\)

en

\(P(\sum_{k=1}^{m+1}x_k \leq 1) = \int_0^1 \frac{(1-x_{m+1})^m}{m!}\; dx_{m+1} = \frac{-1}{(m+1)!}(1-x_{m+1})^{m+1}|_0^1 = \frac{1}{(m+1)!}\)

waarmee de juistheid van de inductiehypothese bewezen is.

De kans dat de

\(n\)

-de maal de som boven 1 uitkomt is

\((1-\frac{1}{n!})-(1-\frac{1}{(n-1)!}) = \frac{1}{(n-1)!}-\frac{1}{n!} = \frac{n-1}{n!}\)

.

Het verwachte aantal trekking is dan

\(\sum_{n=2}^{\infty} n\frac{n-1}{n!} = \sum_{n=2}^{\infty} \frac{1}{(n-2)!} = e\)

Dit bericht is bewerkt door jhnbk: Overmorgen, 15:51

[jhnbk]

Mooi zo, het lijkt moeilijk, maar het idee erachter is simpel.

[A.Square]

Ik zal het nog een keer uitwerken met de exponentiele verdeling.

Nu heb ik helaas geen tijd.

[Schwartz]

Misschien iets met Exp[ln.......] ???

Als men een reeks van 1 tot en met 4 heeft en men moet minimaal 4 hebben dan heeft men maximaal

4 keer een random trekking omdat 4*1 pas 4 is.

Minimaal heeft men dan 1 trekking als men de eerste keer reeds 4 trekt.

De kans dat men 4 keer moet trekken is 1 op 4^4.

De kans dat men 1 keer moet trekken is simpel 1 op 4.

[PeterPan]

Zij

\(E:[0,1]\to \nn\)

gedefinieerd door

\(E(x)\)

is het verwachte aantal random getallen met als som minimaal

\(x\)

.

We zoeken

\(E(1)\)

.

\(E(x)\geq 1\)

(triviaal).

Het aantal random getallen met minimale som

\(x\)

is precies 1 met kans

\(1-x\)

.

en groter dan 1 als de eerste keer een getal kleiner dan

\(x\)

wordt gegenereerd.

Stel de eerste keer heb je getal

\(y<x\)

.

Dan is het aantal te verwachten nog te genereren getallen om boven die

\(x\)

uit te komen

\(E(x-y)\)

.

Dus

\(E(x) = 1\cdot (1-x) + \int_{0}^{x} 1+E(x-y)\; dy = 1\cdot (1-x) + \int_{0}^{x} 1+E(u)\; du\)

.

Differentiëren geeft

\(E'(x) = -1 + (1+E(x)) = E(x)\)

Dus

\(E\)

is de exponentiële functie. En daar

\(E(0)=1\)

is

\(E(1)=e\)

.

Dit bericht is bewerkt door Swiebertje: Overmorgen, 25:61