M.M. <m...@N...gazeta.pl> napisał(a):

> zażółcony <r...@c...pl> napisał(a):
>
> > > 1) Nie powinno być kłopotów przy złączeniach
> > > 2) Można założyć index na T.rnd
> > > 3) Nie ma problemów z usuwaniem i "dziurami"
> > > 4) Rozkład... właśnie nie mam pewności jaki jest rozkład.
> >
> > Rozkład jest ok, jak generator losowy jest ok :)
> Właśnie tego nie umiem matematycznie dowieść :)

Mamy n rekordów. Rekordom przypisaliśmy losową
liczbę z rozkładu równomiernego. Wybieramy
rekord z najmniejszą liczbą. Rozkład był
równomierny, więc każdy rekrod ma równą szansę
dostać liczbę najmniejszą co za tym idzie
zostać wylosowany. Czyli na początku jest ok.

Potem rekordy się podzieliły na dwa zbiory. Jeden
zbiór zawiera n-1 rekordów a drugi 1 rekrod,
ten wylosowany. Rekord wylosowany otrzymuje
na nowo losową liczbę. Szansa że otrzyma mniejszą
liczbę niż najmniejsza liczba ze zbioru n-1 wynosi
1/n, a więc szansa zdarzenia przeciwnego 1-1/n.
Więc szansa że za drugim razem zostanie wylosowany
ten sam rekord z n rekordów wynosi właśnie 1/n.
Pozostałe rekordy mają liczby z rozkładu równomiernego,
a więc wylosowania jednego z pozostałych też
wynosi 1/n.

Czyli na początku szansa wylosowania każdego
rekordu wynosi 1/n, a po losowaniu też wynosi
1/n. Czyżby to był koniec dowodu?

Pozdrawiam


--
Wysłano z serwisu Usenet w portalu Gazeta.pl -> http://www.gazeta.pl/usenet/