losowe permutacje

Definicja klasyczna. Prawdopodobieństwo warunkowe i całkowite. Zmienne losowe i ich parametry. Niezależność. Prawa wielkich liczb oraz centralne twierdzenia graniczne i ich zastosowania.
Rafix_
Użytkownik
Użytkownik
Posty: 147
Rejestracja: 31 mar 2007, o 23:44
Płeć: Mężczyzna
Lokalizacja: Lublin
Podziękował: 7 razy
Pomógł: 1 raz

losowe permutacje

Post autor: Rafix_ » 4 gru 2011, o 12:29

Wybieramy losowo permutację \(\displaystyle{ \pi}\) ze zbioru wszystkich permutacji
n-elementowych. Punktem stałym permutacji \(\displaystyle{ \pi}\) nazywamy dowolny
\(\displaystyle{ x}\) dla którego \(\displaystyle{ \pi(x) = x}\).
1. Oblicz wartość oczekiwaną liczby punktów stałych \(\displaystyle{ \pi}\).
2. Oblicz wariancję liczby punktów stałych \(\displaystyle{ \pi}\).

Jak zacząć?
Ostatnio zmieniony 4 gru 2011, o 12:48 przez Rafix_, łącznie zmieniany 1 raz.
Rekrutacja Instytut Matematyczny, Uniwersytet Wrocławski (gif)

adek05
Użytkownik
Użytkownik
Posty: 450
Rejestracja: 3 kwie 2007, o 18:38
Płeć: Mężczyzna
Lokalizacja: Biała Podlaska
Podziękował: 12 razy
Pomógł: 68 razy

losowe permutacje

Post autor: adek05 » 4 gru 2011, o 12:39

Zdefiniować zmienne losowe, które mają dla nas znaczenie.

Rafix_
Użytkownik
Użytkownik
Posty: 147
Rejestracja: 31 mar 2007, o 23:44
Płeć: Mężczyzna
Lokalizacja: Lublin
Podziękował: 7 razy
Pomógł: 1 raz

losowe permutacje

Post autor: Rafix_ » 4 gru 2011, o 12:55

mógłbyś napisać coś więcej? O jakie zmienne chodzi?

adek05
Użytkownik
Użytkownik
Posty: 450
Rejestracja: 3 kwie 2007, o 18:38
Płeć: Mężczyzna
Lokalizacja: Biała Podlaska
Podziękował: 12 razy
Pomógł: 68 razy

losowe permutacje

Post autor: adek05 » 4 gru 2011, o 12:58

Z każdą pozycją w permutacji wiążemy sobie zmienną losową \(\displaystyle{ X_i}\) o rozkładzie Bernoulliego, która mówi nam, czy dana pozycja w permutacji jest punktem stałym.
Następnie liczba punktów stałych w permutacji dana jest przez zmienną:
\(\displaystyle{ X = \sum_{i = 1}^n X_i}\)
Dalej pozostaje tylko znaleźć wartość oczekiwaną takiej zmiennej z wykorzystaniem elementarnych twierdzeń dotyczących zmiennych losowych.

Rafix_
Użytkownik
Użytkownik
Posty: 147
Rejestracja: 31 mar 2007, o 23:44
Płeć: Mężczyzna
Lokalizacja: Lublin
Podziękował: 7 razy
Pomógł: 1 raz

losowe permutacje

Post autor: Rafix_ » 4 gru 2011, o 13:15

\(\displaystyle{ X_i}\) jest punktem stałym z prawdopodobieństwem \(\displaystyle{ p=\frac{1}{n}}\) wartość oczekiwana w rozkłądzie 0/1-kowym to też \(\displaystyle{ p}\). Z addytywności wartości oczekiwanej mamy \(\displaystyle{ \mathbb{E}X = n \frac{1}{n} = 1}\)

tak?

adek05
Użytkownik
Użytkownik
Posty: 450
Rejestracja: 3 kwie 2007, o 18:38
Płeć: Mężczyzna
Lokalizacja: Biała Podlaska
Podziękował: 12 razy
Pomógł: 68 razy

losowe permutacje

Post autor: adek05 » 4 gru 2011, o 13:17

Tak.

Rafix_
Użytkownik
Użytkownik
Posty: 147
Rejestracja: 31 mar 2007, o 23:44
Płeć: Mężczyzna
Lokalizacja: Lublin
Podziękował: 7 razy
Pomógł: 1 raz

losowe permutacje

Post autor: Rafix_ » 4 gru 2011, o 13:39

ok,

teraz wariancja \(\displaystyle{ VarX_i = p(1-p) = \frac{1}{n}(1-\frac{1}{n})=\frac{n-1}{n^2}}\) zmienne są niezależne wiec wariancja spełnia warunek addytywności \(\displaystyle{ VarX = \frac{n-1}{n}}\) Dobrze?

czy może liczyć ze wzoru ?
\(\displaystyle{ VarX = \mathbb{E}(X^2) - (\mathbb{E}X)^2}\)

adek05
Użytkownik
Użytkownik
Posty: 450
Rejestracja: 3 kwie 2007, o 18:38
Płeć: Mężczyzna
Lokalizacja: Biała Podlaska
Podziękował: 12 razy
Pomógł: 68 razy

losowe permutacje

Post autor: adek05 » 4 gru 2011, o 15:47

One nie są niezależne, więc trzeba liczyć z drugiego sposobu.

Rafix_
Użytkownik
Użytkownik
Posty: 147
Rejestracja: 31 mar 2007, o 23:44
Płeć: Mężczyzna
Lokalizacja: Lublin
Podziękował: 7 razy
Pomógł: 1 raz

losowe permutacje

Post autor: Rafix_ » 4 gru 2011, o 17:06

ok.
\(\displaystyle{ VarX = \mathbb{E}X^2 - \mathbb{E}^2X}\)
\(\displaystyle{ \mathbb{E}X = 1 \ \ \ \mathbb{E}^2X = 1}\)

\(\displaystyle{ \mathbb{E}X^2 = \mathbb{E}(\sum_{i=1}^{n} X_i)^2 = \mathbb{E}(\sum_{i=1}^{n} \sum_{j=1}^{n} X_i X_j ) =(\sum_{i=1}^{n} \sum_{j=1}^{n} \mathbb{E}(X_i X_j) = \\ = n\mathbb{E}(X_i X_i) + (n^2-n)\mathbb{E}(X_i X_j) = n\cdot1 + (n^2-n)P(X_i=1 \wedge X_j=1) = n+(n^2-n)\frac{1}{n(n-1)}}\)
ponieważ:
\(\displaystyle{ P(X_i=1 \wedge X_j=1) = \frac{1}{n} \cdot \frac{1}{n-1}}\) (tak ?)

rozbijając podwójną sumę otrzymamy \(\displaystyle{ n}\) skłądników w któch \(\displaystyle{ X_i = X_j}\) oraz \(\displaystyle{ n^2-n}\) składników w którch \(\displaystyle{ X_i \neq X_j}\)

\(\displaystyle{ VarX = n+(n^2-n)\frac{1}{n(n-1)} - 1}\)

teraz jest dobrze?

adek05
Użytkownik
Użytkownik
Posty: 450
Rejestracja: 3 kwie 2007, o 18:38
Płeć: Mężczyzna
Lokalizacja: Biała Podlaska
Podziękował: 12 razy
Pomógł: 68 razy

losowe permutacje

Post autor: adek05 » 4 gru 2011, o 19:05

Dokładnie tak jak było na wykładzie

Potekk
Użytkownik
Użytkownik
Posty: 110
Rejestracja: 2 gru 2007, o 12:34
Płeć: Mężczyzna
Lokalizacja: Piastów
Podziękował: 1 raz
Pomógł: 35 razy

losowe permutacje

Post autor: Potekk » 7 gru 2011, o 22:45

\(\displaystyle{ n\mathbb{E}X _{i} = n\frac{1}{n} = 1}\)
Zauważ jeszcze, że
\(\displaystyle{ n^{2} - n = n(n-1)}\)
\(\displaystyle{ \mathrm{VarX} = 1 + 1 - 1 = 1}\)

ODPOWIEDZ