Random getallen
Random getallen
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?
De gegenereerde getallen tel ik op totdat hun som minstens 1 is.
Hoe veel getallen zal de computer daarvoor naar verwachting nodig hebben?
- Berichten: 6.905
Re: Random getallen
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
De kans om met 3 getallen al een som te hebben groter dan 1 is benaderend
\(\frac78\)
Het vel van de beer kunnen verkopen vraagt moeite tenzij deze dood voor je neervalt. Die kans is echter klein dus moeten we zelf moeite doen.
Re: Random getallen
Dat lijkt me niet juist.Ik denk 3, en mijn computer bevestigd dat, ik zie enkel niet hoe ik tot het resultaat zou kunnen komen.
ofDe kans om met 3 getallen al een som te hebben groter dan 1 is benaderend\(\frac78\)
\(\frac56\)
-
- Berichten: 2.746
Re: Random getallen
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?
1/2 is de verwachte waarde van elk getal, na twee keer trekken is je verwachte waarde 1
dus 2?
- Berichten: 6.905
Re: Random getallen
Dan heb je in ongeveer 50% van de gevallen een getal groter dan 1. Daarmee dat ik dacht dat dit niet volstond.
Het vel van de beer kunnen verkopen vraagt moeite tenzij deze dood voor je neervalt. Die kans is echter klein dus moeten we zelf moeite doen.
-
- Berichten: 251
Re: Random getallen
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
En nu moet het gemiddelde van de som van de verschillen 1 opleveren.
nb: met
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'- Berichten: 691
Re: Random getallen
(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.
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.
Een computertaal is voor mensen, niet voor de computer.
- Berichten: 6.905
Re: Random getallen
@A.Square: kan je de volledige uitwerking geven, want ik zie niet waar je naartoe wilt.
Het vel van de beer kunnen verkopen vraagt moeite tenzij deze dood voor je neervalt. Die kans is echter klein dus moeten we zelf moeite doen.
- Berichten: 691
Re: Random getallen
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;
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;
Een computertaal is voor mensen, niet voor de computer.
- Berichten: 6.905
Re: Random getallen
2,7 had ik ook in python, daarmee ik 3 geantwoord heb en hiervoor een benaderende kans heb gegeven.
Het vel van de beer kunnen verkopen vraagt moeite tenzij deze dood voor je neervalt. Die kans is echter klein dus moeten we zelf moeite doen.
Re: Random getallen
Ik heb wel een oplossing, maar ik denk dat er een eenvoudiger oplossing te geven is.
Bekijk eerst 2 random getallen
Wat is de kans dat
Bekijk daartoe het vierkant van 1 bij 1, waar we de trekking als
Nu komt het gebied
Dus
Nu 3 random getallen
We tekenen de waarden als punten
De kans is de oppervlakte onder de grafiek
Ik heb nu het vermoeden dat
Dan is automatisch (vermenigvuldigingsfactor
Bewijs:
Met volledige inductie. Stel juist voor
Dan willen we de oppervlakte berekenen onder de grafiek van
Dan is
De kans dat de
Het verwachte aantal trekking is dan
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- Berichten: 6.905
Re: Random getallen
Mooi zo, het lijkt moeilijk, maar het idee erachter is simpel.
Het vel van de beer kunnen verkopen vraagt moeite tenzij deze dood voor je neervalt. Die kans is echter klein dus moeten we zelf moeite doen.
-
- Berichten: 251
Re: Random getallen
Ik zal het nog een keer uitwerken met de exponentiele verdeling.
Nu heb ik helaas geen tijd.
Nu heb ik helaas geen tijd.
- Berichten: 691
Re: Random getallen
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.
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.
Een computertaal is voor mensen, niet voor de computer.
Re: Random getallen
Zij
We zoeken
Het aantal random getallen met minimale som
en groter dan 1 als de eerste keer een getal kleiner dan
Stel de eerste keer heb je getal
Dan is het aantal te verwachten nog te genereren getallen om boven die
Dus
Differentiëren geeft
Dit bericht is bewerkt door Swiebertje: Overmorgen, 25:61
\(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