długie losowanie

[Fibik]

Losujemy liczby np. z przedziału 1 do n=1000, i tysiąc razy.

Teoretycznie wychodzi 1000/1000, czyli każda liczba raz będzie wylosowana, ale tylko średnio,
bo raczej jest nikła szansa że wylosujemy za każdym razem inną - coś tam się powtórzy,
a tym samym automatycznie część liczb nam zniknie, znaczy nie wylosujemy ich w ogóle, ani raza.

Zatem ile będzie tych brakujących, tak zazwyczaj, czyli też średnio?

5 sztuk, 10, a może aż 100?

[jarek4700]

Zasymulowałem to w Matlabie.

Kod: Zaznacz cały

clear all;
close all;

Nmax = 1000;
N = 2:Nmax;
avg = zeros(1,Nmax);
rep = 1000;

for j = N;
 for i = 1:rep
  V = ones(1,j);
  R = ceil(j.*rand(1,j));
  V(R) = 0;
  avg(j) = avg(j) + sum(V);
 end
avg(j) = avg(j)/rep;
end

plot(N,avg(N)./N);

Skrypt rysuje wykres stosunku liczb niewylosowanych do wszystkich w zależności od tego ile ich było.
Widać że stosunek ten tabilizuje się gdzieś na poziomie \(\displaystyle{ 0,367}\)
Wychodzi więc na to że należy się spodziewać aż \(\displaystyle{ 367}\) takich liczb.

[norwimaj]

Widać że stosunek ten tabilizuje się gdzieś na poziomie \(\displaystyle{ 0,367}\)

Podejrzanie blisko liczby \(\displaystyle{ e^{-1}}\). Czy to może być przypadek?

Ustalmy konkretną liczbę \(\displaystyle{ k}\) z przedziału od \(\displaystyle{ 1}\) do \(\displaystyle{ n}\). Strzelamy w tę liczbę \(\displaystyle{ n}\) razy niezależnie, za każdym razem trafiając celu z prawdopodobieństwem \(\displaystyle{ \frac1n}\). Zatem prawdopodobieństwo, że ta liczba zostanie trafiona, jest równe:

\(\displaystyle{ P_n=n\cdot\frac1n-\binom n2\cdot\frac1{n^2} + \binom n3\frac1{n^3} - \ldots}\)

To wyrażenie dąży do \(\displaystyle{ 1-\frac1e}\), gdy \(\displaystyle{ n}\) dąży do nieskończoności. Wartość oczekiwana liczby brakujących liczb jest równa \(\displaystyle{ n - n\cdot P_n\approx \frac ne}\).

[Fibik]

Tak myślałem. Rozkład Bernoullego zbiega do Poissona.

A teraz trochę inaczej: losujemy ze zbioru 1 do N=1000, ale mniej, np. tylko 20 sztuk,
i dwa razy, znaczy tworzymy dwie paczki po 20 sztuk.

Ile teraz będzie powtórzeń pomiędzy tym paczkami?

Potem można pojechać z tym dalej: trzy paczki, 4, 5, ...