losowa descendencja

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
Fibik
Użytkownik
Użytkownik
Posty: 953
Rejestracja: 27 wrz 2005, o 22:56
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 11 razy
Pomógł: 74 razy

losowa descendencja

Post autor: Fibik »

Mamy liczbę \(\displaystyle{ n}\), np. \(\displaystyle{ n = 1000}\), i teraz robimy z tego kolejne losowe wg tradycyjnego schematu, czyli:
\(\displaystyle{ n_1 = random(n)}\)

\(\displaystyle{ random(n)}\) produkuje liczby od \(\displaystyle{ 0}\) do do \(\displaystyle{ n-1}\), czyli zawsze mniejsze od \(\displaystyle{ n}\), i z rozkładem równomiernym.

Potem to kontynuujemy ale już od: \(\displaystyle{ n = n_1...}\) aż do \(\displaystyle{ n = 0}\);

Zatem procedura wygląda tak:

Kod: Zaznacz cały

n = n_0; // wartość startowa np. [latex]n_0 = 10000[/latex]
k = 0;   // liczba przejść - wywołań random

repeat
  n = random(n); 
  k++; // liczba wywołań random
until n = 0; // koniec

print k;
jak jest średnia wartość liczby wywołań, czyli \(\displaystyle{ k}\), i jak wygląda rozkład takiej zmiennej losowej?
Ostatnio zmieniony 3 paź 2020, o 01:22 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Brak LaTeX-a. Brak tagów [code].
janusz47
Użytkownik
Użytkownik
Posty: 7910
Rejestracja: 18 mar 2009, o 16:24
Płeć: Mężczyzna
Podziękował: 30 razy
Pomógł: 1670 razy

Re: losowa descendencja

Post autor: janusz47 »

Zmienna losowa \(\displaystyle{ X \sim \mathcal{U}(n) }\) ma dyskretny rozkład równomierny o funkcji prawdopodobieństwa

\(\displaystyle{ p(n) = \frac{1}{n+1} }\)

i średniej

\(\displaystyle{ k = \frac{n}{2}. }\)
Fibik
Użytkownik
Użytkownik
Posty: 953
Rejestracja: 27 wrz 2005, o 22:56
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 11 razy
Pomógł: 74 razy

Re: losowa descendencja

Post autor: Fibik »

Skąd taki pomysł? Nie zgadza się.

[...]
Ostatnio zmieniony 5 paź 2020, o 17:59 przez AiDi, łącznie zmieniany 1 raz.
Powód: Brak kultury...
janusz47
Użytkownik
Użytkownik
Posty: 7910
Rejestracja: 18 mar 2009, o 16:24
Płeć: Mężczyzna
Podziękował: 30 razy
Pomógł: 1670 razy

Re: losowa descendencja

Post autor: janusz47 »

Mamy do czynienia z równomiernym rozkładem zmiennej losowej dyskretnej i jej dwoma parametrami - rozkładem prawdopodobieństwa i wartością średnią.
FasolkaBernoulliego
Użytkownik
Użytkownik
Posty: 157
Rejestracja: 23 sty 2020, o 16:16
Płeć: Mężczyzna
wiek: 30
Podziękował: 14 razy
Pomógł: 18 razy

Re: losowa descendencja

Post autor: FasolkaBernoulliego »

Fibik pisze: 2 paź 2020, o 16:30 jak jest średnia wartość liczby wywołań, czyli \(\displaystyle{ k}\), i jak wygląda rozkład takiej zmiennej losowej?
Nie doszedłem do żadnego wzoru zwartego (ale też niespecjalnie się bawiłem, bo się na tym nie znam), ale rozkład można (jeśli dobrze myślę) wyznaczyć rekurencyjnie:
\(\displaystyle{ p_n(k)}\) - prawdopodobieństwo, że startując z \(\displaystyle{ n > 0 }\) algorytm wykona \(\displaystyle{ k}\) kroków
\(\displaystyle{ p_n(1) = \frac{1}{n}}\)
\(\displaystyle{ p_n(k) = \frac{1}{n} \sum_{i=1}^{n-1} p_i(k-1)}\) dla \(\displaystyle{ k > 1}\)
ODPOWIEDZ