Matematyka.pl

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ąć?

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

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

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.

\(\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.

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}\)

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

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?

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

\(\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}\)