%
% file:         synopsis.tex
% purpose:      synopsis of prob & stat Ostrava course
% created:      pasha sep 25-27 2017
% modified:     pasha dec 1 2019
%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentclass[12pt,a4paper,oneside]{amsart}
\input{pasha-inc.tex}
\geometry{hmargin=1.8cm,top=2cm,bottom=2.5cm}
\pagestyle{plain}

%\usepackage{fouriernc}
\usepackage{palatino}

\usepackage[colorlinks=false]{hyperref}
\usepackage{amssymb}

\renewcommand{\sectionname}{Lecture}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{claim}{Claim}[section]

\theoremstyle{definition}
\newtheorem{definition}{Definition}[section]
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\begin{document}

\title{Introduction to Probability \& Statistics. \\ 
Synopsis of a course at OU \\ winter semesters 2017/2018, 2018/2019, 2019/2020}
\author{Pasha Zusmanovich}
\address{}
\email{pasha.zusmanovich@gmail.com}
\date{last modified \today}

\maketitle


{\small Each lecture lasted 1.5 hours}.


\section{Basic combinatorics} % lecture 1

{\small
\noindent
Literature: 

\begin{enumerate}%[\upshape[[1]]]
\item Wikipedia: 
\emph{Binomial coefficient}, \emph{Pascal's triangle}, \emph{Permutation}.
\item 
R.L. Graham, D.E. Knuth, and O. Patashnik, \emph{Concrete Mathematics}, 2nd ed.,
Addison-Wesley, 1994, Chapter 5.1.
\item N.Ya. Vilenkin, \emph{Combinatorics}, Academic Press, 1971.
\end{enumerate}
}

\medskip

A subject of probability and statistics. 

To compute probabilities, we have to count, be it counting of discrete sets,
like in combinatorics, or counting of areas of geometric figures, like in 
mathematical analysis.


\begin{theorem}\label{th-perm}
The number of permutations of $n$ elements is equal to $n!$.
\end{theorem}

\begin{proof}
By induction.
\end{proof}

Variation without repetition = a way to choose $k$ elements out of $n$ elements,
taking into account the order of elements.

\begin{theorem}\label{th-var}
The number of variations without repetition is equal to $\frac{n!}{(n-k)!}$.
\end{theorem}

Variation with repetition = a way to choose $k$ elements out of $n$ elements,
taking into account the order of elements, and with possible repetitions of 
elements.

\begin{theorem}
The number variations with repetition is equal to $n^k$.
\end{theorem}

Combination = a way to choose $k$ elements out of $n$ elements, without taking
into account order of elements (and not allowing repetitions).

\begin{theorem}
The number of combinations is equal to $\binom{n}{k}$.
\end{theorem}

\begin{proof}
This is the same as doing variation without repetitions, but without accounting
for different permutations of elements, i.e. the number in Theorem \ref{th-var}
should be divided by the number of permutations of $k$ elements, which, 
according to Theorem \ref{th-perm}, is equal to $k!$: $\frac{n!}{k!(n-k)!}$.
\end{proof}

These numbers are \emph{binomial coefficients}, occurring in the binomial 
formula: \newline
$(a+b)^n = \sum_{k=0}^n \binom{n}{k} a^k b^{n-k}$.

Properties of binomial coefficients: 
$\binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1}$, 
$\binom{n}{k} = \binom{n}{n-k}$.

Pascal's triangle.

A combinatorial meaning of the particular case of the binomial formula
$2^n = \sum_{k=0}^n \binom{n}{k}$: all possible ways to choose elements out of 
$n$ elements, i.e., the number of $n$-length binary sequences (like 
$0110 \dots$, etc.)

Inclusion-exclusion principle:
\begin{alignat*}{2}
|A_1 \cup \dots \cup A_n| =&   \\
  &|A_1| + \dots + |A_n|  \\
- &|A_1 \cap A_2| - |A_1 \cap A_3| - \dots - |A_{n-1} \cap A_n| \\
+ &|A_1 \cap A_2 \cap A_3| + \dots + |A_{n-2} \cap A_{n-1} \cap A_n|  \\
- &\dots + \\
+ &(-1)^{n+1} |A_1 \cap A_2 \cap \dots \cap A_n| .
\end{alignat*}





\section{Probability function} % lecture 2

{\small
\noindent
Literature: \cite[Chapter 2]{main}.
}

\bigskip

Notions of sample space, event, elementary event. 

Dictionary between set-theoretic and logical terms 
($\cup$ = $\&$, $\cap$ = $\wedge$, complement = $\neg$).

Definition of probability function on finite and infinite sample space.

\begin{claim}
If $P$ is a probability function on a sample space $\Omega$, then 
$P(\varnothing) = 0$.
\end{claim}

\begin{proof}
Follows from $P(A_1 \cup A_2) = P(A_1) + P(A_2)$ for 
$A_1 \cap A_2 = \varnothing$ (take $A_2 = \varnothing$).
\end{proof}

\begin{claim}
If $P$ is a probability function on a sample space $\Omega$, then for any
$A \subseteq \Omega$, $P(\Omega \backslash A) = 1 - P(A)$.
\end{claim}

\begin{proof}
Follows from $P(A_1 \cup A_2) = P(A_1) + P(A_2)$ for 
$A_1 \cap A_2 = \varnothing$, and from $P(\Omega) = 1$ (take $A_1 = A$, 
$A_2 = \Omega \backslash A$).
\end{proof}

Example: we are tossing an unbiased coin till the fist head. Our sample space is
$\Omega = \{1,2,3,\dots,n,\dots\}$, where $n$ signifies that the first head
occurs at $n$th toss. Then $P(n) = \frac{1}{2^n}$, and 
$$
P(1) + P(2) + P(3) + \dots = \frac 12 + \frac{1}{4} + \frac 18 + \dots = 1 ,
$$
as expected.

For arbitrary events $A_1, A_2, \dots, A_n$, not necessary disjoint, we have
\begin{alignat*}{2}
P(A_1 \cup \dots \cup A_n) =&   \\
  &P(A_1) + \dots + P(A_n)  \\
- &P(A_1 \cap A_2) - P(A_1 \cap A_3) - \dots - P(A_{n-1} \cap A_n) \\
+ &P(A_1 \cap A_2 \cap A_3) + \dots + P(A_{n-2} \cap A_{n-1} \cap A_n) \\
- &\dots + \\
+ &(-1)^{n+1} P(A_1 \cap A_2 \cap \dots \cap A_n) ,
\end{alignat*}
what is exactly the inclusion-exclusion principle.





\section{Conditional probability, Bayes' formula, independent events} 
% lecture 3

{\small
\noindent
Literature:

\begin{enumerate}
\item \cite[Chapter 3]{main}
\item Wikipedia: \emph{Independence (probability theory)}
\end{enumerate}
}

\bigskip

Definition and meaning of conditional probability.

\begin{theorem}\label{th-1}
Let $\Omega$ be a sample space, and $B$ an event. Then 
$Q: \mathscr P(\Omega) \to [0,1]$ defined as $Q(A) = P(A|B)$ is a probability
function on $\Omega$.
\end{theorem}

Relationship between $P(A|B)$ and $P(B|A)$, Bayes' formula.

\begin{theorem}
Let $\Omega$ be a sample space, $B_1, \dots, B_n$ events such that 
$B_1 \cup \dots B_n = \Omega$, and $B_i$'s are pairwise disjoint. Then
$$
P(B_i|A) = \frac{P(A|B_i) P(B_i)}{P(A|B_1)P(B_1) + \dots + P(A|B_n)P(B_n)} .
$$
\end{theorem}

\begin{proof}
Using (several times) additivity of the conditional probability (what follows 
from Theorem \ref{th-1}), and Bayes' formula.
\end{proof}

\begin{definition} 
Two events $A$ and $B$ are called independent, if one of the following six equivalent condition holds:
\begin{enumerate}[\upshape(i)]
\item $P(A|B) = P(A)$
\item $P(B|A) = P(B)$
\item $P(A \cap B) = P(A)P(B)$
\end{enumerate}
and the same conditions (i)-(iii) with $A$ and $B$ being replaced by 
$\overline A$ and $\overline B$ (complements), respectively.
\end{definition}

Generalization of this definition to the case of several events is not as
straightforward as one might think at the first glance:

\begin{definition}
Events $A_1, \dots, A_n$ are called independent, if 
$$
P(A_{i_1} \cap \dots \cap A_{i_k}) = P(A_{i_1}) \dots P(A_{i_k})
$$
for any $\{i_1, \dots, i_k\} \subseteq \{1, \dots, n\}$.
\end{definition}

An alternative definition of independent events: events $A_1, \dots A_n$ are 
called independent, if 
$$
P(B_1 \cap \dots \cap B_n) = P(B_1) \dots P(B_n)
$$
where each $B_i$'s is either $A_i$ or $\overline A_i$.

Equivalence of this definition with the definition from the previous lecture.

When events $A$ and $\overline A$ are independent? Answer: if and only if
$P(A) = 0$ or $1$.





\section{Discrete and continous random variables. Distribution function}
% lecture 4
{\small
\noindent
Literature:

\begin{enumerate}
\item \cite[Chapter 4, \S 5.1]{main}

\item Wikipedia: 
\emph{Probability distribution}, \emph{Probability mass function}.
\end{enumerate}
}

\bigskip

%A way to give examples of events and probability functions: define a (finite or
%countable) set $\Omega$, and define $P(a) \in [0,1]$ for each $a\in \Omega$ such
%that $\sum_{a \in \Omega} P(a) = 1$.

Notion of discrete random variable, mass function, and distribution function.
Example with ``tossing two coins'' with $0$ and $1$ (so 
$\Omega = \{0,1\} \times \{0,1\}$).

Properties of discrete distribution functions: piecewise constant, 
non-decreasing, $\lim_{x\to -\infty} F_X(x) = 0$, 
$\lim_{x\to +\infty} F_X(x) = 1$.

Interplay between discrete and continuous.
Continuous random variable as a limiting process of discrete random variables.

Continuous distribution function, density function, its properties. 
Density is not a probability!

Example: picking a point at a circle of radius $R$, the random variable $X(r)$ 
is the probability that the point will lie in a circle with radius $r$, 
$0 \le r \le R$.





\section{Expectation, quantiles}
%lecture 6

{\small
\noindent
Literature: \cite[\S\S 5.6, 7.1, 7.3]{main}.
}

\bigskip

Expectation of discrete and continuous random variables. Physical meaning of
expectation as center of masses.

Formula for $E[g(X)]$. 

\begin{theorem}\label{th-e}
$E[aX+b] = aE[X] + b$.
\end{theorem}

Quantiles, median.





\section{Variance. Uniform distribution}
{\small
\noindent
Literature:

\begin{enumerate}
\item \cite[\S\S 5.2, 7.4]{main}
\item Wikipedia: 
\emph{Discrete uniform distribution}, \emph{Uniform distribution (continuous)}.
\end{enumerate}
}

Definition and meaning of variance.

\begin{theorem}
$Var(X) = E[X^2] - E[X]^2$.
\end{theorem}

Proof goes separately for discrete and continuous distributions.

\begin{theorem}
$Var(aX + b) = a^2 Var(X)$.
\end{theorem}

Proof using the definition of variance and Theorem \ref{th-e}.

Standard deviation.

Discrete and continuous uniform distributions, their expectation and variance.





\section{Binomial, geometric, exponential distributions}
{\small
\noindent
Literature:

\begin{enumerate}
\item \cite[\S\S 4.3, 4.4, 5.3]{main}
\item Wikipedia: 
\emph{Binomial distribution}, \emph{Geometric distribution}, 
\emph{Exponential distribution}.
\end{enumerate}
}

Binomial distribution, its expectation and variance.

\medskip

Geometric distributuon: the mass function is $f_X(k) = (1-p)^{k-1}p$.

$E[X] = \sum_{k=0}^\infty (1-p)^{k-1}p k = \frac 1p$.

$Var(X) = E[X^2] - E[X]^2$.
\begin{multline*}
E[X^2] = \sum_{k=0}^\infty (1-p)^{k-1}p k^2 
= \sum_{k=1}^\infty (1-p)^{k-1}p k^2 
= p \sum_{k=1}^\infty (-k \frac{d}{dp}((1-p)^k))
= -p \frac{d}{dp} \Big(\sum_{k=1}^\infty k(1-p)^k\Big) \\ 
= -p \frac{d}{dp} \Big(\frac{1-p}{p} \sum_{k=0}^\infty (1-p)^{k-1}pk \Big)
= -p \frac{d}{dp} \Big(\frac{1-p}{p} E[X] \Big)
= -p \frac{d}{dp} \Big(\frac{1-p}{p^2} \Big)
= -p \frac{d}{dp} \Big(\frac{1}{p^2} - \frac 1p \Big) \\
= -p (-\frac{2}{p^3} + \frac{1}{p^2}) 
= \frac{2}{p^2} - \frac{1}{p}.
\end{multline*}

$Var(X) = \frac{2}{p^2} - \frac{1}{p} - \frac{1}{p^2} = \frac{1-p}{p^2}$.

(Continuous) exponential distribution, its utility, expectation, and variance.





\section{Poisson and normal distributions. Sum of random variables}
{\small
\noindent
Literature:

\begin{enumerate}
\item \cite[\S\S 5.5, 10.1, 12.2]{main}
\item Wikipedia: 
\emph{Poisson distribution},
\emph{Normal distribution}.
\end{enumerate}
}

(Discrete) Poisson distribition, its utility, expectation, and variance.

Normal distribution, its significance. Central limit theorem (imprecise,
on an empirical level).

\medskip

$E[X + Y] = E[X] + E[Y]$.

$E[a_1 X_1 + \dots + a_n X_n + b] = a_1E[X_1] + \dots + a_nE[X_n] + b$.

Application of this formula: a short derivation of the formula $E[X] = pn$ for
a binomial distribution with parameters $p$, $n$, without evaluating of the
corresponding sums.





\section{covariance, correlation}
{\small
\noindent
Literature:

\begin{enumerate}
\item \cite[Chapter 10]{main}
\item Wikipedia: 
\emph{Covariance}, \emph{Correlation and dependence}.
\end{enumerate}
}

$Var(X+Y) = Var(X) + Var(Y) + 2Cov(X,Y)$.

If $X$ and $Y$ are independent random variables, then $E[XY] = E[X]E[Y]$.
The opposite is not true: an example.

Property of correlation: $-1 \le Cor(X,Y) \le 1$. Correlation vs. dependence.



\section{Data analysis. Statistical models}
{\small
\noindent
Literature: \cite[\S\S 15.2, 15.5, 16.1, 16.2, 16.3, 17.4, 22.1]{main}.
}

Graphical representation of datasets: histogram, scatterplot.

Numerical characteristics of datasets: mean, median, quantiles, variance.

Statistical models. Linear model (= linear regression). Method of least squares.




\section{Hypotheses testing}
{\small
\noindent
Literature: \cite[\S 25]{main}.
}

Hypotheses testing. Null and alternative hypotheses. Test statistic. 
$p$-values. Type I and type II errors.






\begin{thebibliography}{DKLM}

\bibitem[DKLM]{main} 
F.M. Dekking, C. Kraaikamp, H.P. Lopuha\"a, and L.E. Meester, 
\emph{A Modern Introduction to Probability and Statistics}, Springer, 2005.

\end{thebibliography}

\end{document}
%end of synopsis.tex
