\documentclass[11pt,a4paper]{amsart}

\pagenumbering{gobble}

\usepackage[boxed]{algorithm2e}
\SetAlgoInsideSkip{medskip} %ustawia skok przed i w ramce
\setalcapskip{13pt}
\SetAlgoSkip{smallskip}
\SetKwInput{KwData}{Dane}
\SetKwInput{KwResult}{Wynik}


\usepackage[polish]{babel}
\usepackage{polski}
\usepackage{a4wide}
\usepackage{amsmath}
\usepackage{amssymb}

%\usepackage[a4paper,margin=1cm]{geometry}
\usepackage[cp1250]{inputenc}


\title{Repetytorium z matematyki dyskretnej \\ Lista 2}


\sloppy

\theoremstyle{plain}
\newtheorem{lemat}{Lemat}
\newtheorem{twierdzenie}[lemat]{Twierdzenie}
\newtheorem{wniosek}[lemat]{Wniosek}
\newtheorem{fakt}[lemat]{Fakt}

\SetAlCapFnt{\small}
%\SetAlCapFnt{\footnotesize}
\renewcommand{\algorithmcfname}{Algorytm}%
\newcommand{\Prob}{\mathbb{P}}
\newcommand{\Expv}{\mathbb{E}}
\newcommand{\Var}{\mathbb{D}^2}




\begin{document}

\maketitle

Druga lista. Z wartości oczekiwanej. Proszę zajrzeć również do zadań na stronie p. Przemki Kanarek (link na mojej stronie).
Niektóre zadania mogą być trudne.

\subsubsection*{Zadanie 1}

Udowodnij, że jeśli $X,Y$ są niezależne, to $$\Expv[XY]=\Expv[X]\Expv[Y].$$

\subsubsection*{Zadanie 2}

Pokaż, że $$ \Expv[\sum_i a_i X_i]= \sum_i a_i \Expv[X_i].$$

\subsubsection*{Zadanie 3}

Dane jest $p$ pudełek i $k$ kulek. Niezależnie i jednostajnie wrzucamy kulki do pudełek. Jaka jest oczekiwana liczba pustych pudełek? A niepustych pudełek? Jaka jest oczekiwana liczba kulek będących w pudełku z $1.$ kulka? Czy gdzieś korzystamy z niezależności?

\subsubsection*{Zadanie 4}

Losujemy niezależnie i jednostajnie $n$ punktów ze zbioru $\{1 , \ldots , m \} \times \{1 , \ldots , m \}$ (na płaszczyźnie). Mówimy, że punkt $(x_1,y_1)$ dominuje punkt $(x_2,y_2)$, jeśli $x_1 > x_2$ oraz $y_1 > y_2$. Jaka jest oczekiwana ilość punktów zdominowanych? Liczony z krotnościami, tj. jeśli jeden punkt jest dominowany $k$ różnych punktów to liczymy go $k$-krotnie.

\subsubsection*{Zadanie 5}

Niech $X$ ma tylko wartości naturalne. Udowodnij, że $$ \Expv[X] = \sum_{i>0}\Prob[X \geq i]=\sum_{i\geq0}\Prob[X > i]$$

\subsubsection*{Zadanie 6}

Rzucamy kostką tak długo, aż uzyskamy wszystkie oczka. Jaka jest oczekiwana ilość rzutów?

\subsubsection*{Zadanie 7}

Dana jest losowa permutacja $a_1,\ldots,a_n$ liczb $1, \ldots, n$. Budujemy z niej drzewo binarne,
w $i$-tym kroku wstawiamy do drzewa liczbę $a_i$. Jaki jest pesymistyczny (oczekiwany)
czas zbudownia drzewa?

\textbf{Wskazówka}: Rozważ zmienne losowe $\{ X_{i,j} \}_{1 \leqslant i<j \leqslant n}$ liczące porównania
$a_i$ z $a_j$, tj.:
$$X_{i,j}=
\begin{cases}
1 & \text{, jeśli $a_i$ zostało porównane z $a_j$ w czasie budowania drzewa} \\
0 & \text{, jeśli $a_i$ nie zostało porównane z $a_j$ w czasie budowania drzewa}
\end{cases},
$$
następnie wyraź koszt zbudowania drzewa przez $X_{i,j}$ i skorzystaj
z liniowości wartości oczekiwanej.
\end{document}


