Rart fenomen?

[Zoiros]

Sitter å pirker med et dataprogram jeg laget. Det genererer n tilfeldige uniformt fordelte heltall mellom
[0,n-1] og legger det til en mengde uten å skape duplikater.

Altså hvis jeg legger til {4,3,6,3} så inneholder settet bare {3,4,6}.

Uansett n jeg velger blir settets størrelse ca. 0.62n. Jeg tenkte meg at det kom til å bli 0.5n. Rart.

Noen som kan forklare hvorfor akkurat dette tallet?

For de som bryr seg så er javakoden her:

Kode: Velg alt

Set<String> s = new TreeSet<String>();
Random r = new Random();
int k = 10000;
for(int i = 0; i < k; i++)
{
	s.add("" + r.nextInt(k));
	System.out.println();
}
System.out.println("Størrelse: " + s.size());

PS: Aner ikke hvorfor jeg ikke får skrive ordet "ny" på engelsk? Blir bytta ut med --

[Bogfjellmo]

Burde snarere bli ca. 0,63 for store tall. Grenseverdien er faktisk [tex]1-\frac 1e[/tex]

Skal vi se. En måte vi kan formulere spørsmålet på er: Fra en mengde med n elementer skal det, med tilbakelegging, trekkes ut n elementer. Hva er sannsynligheten P for at et gitt element blir trukket ut minst en gang?

Ser på det motsatte, hva er sjansen for at det ikke blir trukket ut, dvs sjansen for at det er et av de andre n-1 elementene som blir trukket ut hver gang?

[tex]1 - P = \left(\frac{n-1}n\right)^n = \left(1-\frac 1n \right)^n[/tex]
[tex]P = 1 - \left(1-\frac 1n \right)^n[/tex]

Lar vi [tex] n \rightarrow \infty[/tex] får vi

[tex]P = 1- \displaystyle \lim_{n \rightarrow \infty} \left(1-\frac 1n \right)^n = 1 - e^{-1}[/tex]