losowe permutacje
-
- 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
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ąć?
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.
-
- 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
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.
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.
-
- 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
\(\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?
tak?
-
- 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
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}\)
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}\)
-
- 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
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?
\(\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?
-
- 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
\(\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}\)
Zauważ jeszcze, że
\(\displaystyle{ n^{2} - n = n(n-1)}\)
\(\displaystyle{ \mathrm{VarX} = 1 + 1 - 1 = 1}\)