Exam

Markov Chains

Bayesian Statistics

Conditional Expectation

Balls & Bins

• Really useful approximation
  • $1-x\approx e^{-x}$
  • example usage: birthday paradox
    • $(1-\frac1{365})(1-\frac2{365})\dots(1-\frac{k-1}{365})\approx e^{-\frac{k(k-1)}{2\cdot 365}}$
    • because $1-\frac1{365}\approx e^{-\frac1{365}}$ etc.
• Union bound
  • for events $A_1,A_2,\ldots$ it holds that $P(\bigcup A_i)\leq \sum P(A_i)$
  • therefore $P(\text{none of }A_i)\geq 1-\sum P(A_i)$
• Balls and bins model
  • we will be throwing $m$ balls randomly into $n$ bins
  • $X_i$ … number of balls in bin $i$
• How many bins are empty?
  • $P(X_i=0)=(1-\frac1n)^m\approx e^{-\frac mn}$
  • $I_i=1$ if $X_i=0$ (otherwise 1)
  • $\mathbb E(\sum_i I_i)=\sum_i\mathbb EI_i\approx ne^{-\frac mn}$
• How many balls are in bin $i$?
  • $X_i\sim \text{Bin}(m,\frac 1n)\approx\text{Pois}(\frac mn)$
  • $\mathbb EX_i=\frac mn$
• Max-load likely upper bound
  • definition: max-load … $\max\set{X_1,\dots,X_n}$
  • theorem: for large enough $n$ we have $P(\text{maxload}\geq\frac{3\log\log n}{\log n})\leq\frac1n$
  • proof
    • …
• Max-load likely lower bound
  • theorem: for large enough $n$ we have $P(\text{maxload}\leq\frac{\log\log n}{\log n})\leq\frac1n$
  • proof
    • …
• Exact case vs. Poisson case
  • theorem: any event that happens with probability $\leq p$ in the Poisson case happens with probability $\leq p\cdot e\sqrt m$ in the exact case
  • proof
    • …

Stochastic Processes

• Bernoulli process
  • infinite sequence of independent identically distributed Bernoulli trials
  • sequence of RVs $X_1,X_2,\dots$ that are independent and each follows $\text{Ber}(p)$ distribution
  • $X_k=1$ … success/arrival at time $k$
• Quantities of a Bernoulli process
  • $N_t$ … number of successes up to time $t$
    • $N_t\sim\text{Bin}(t,p)$
    • $\mathbb E[N_t]=t\cdot p$
  • $T_k$ … time of the $k$-th success
  • $L_k=T_k-T_{k-1}$
    • waiting time
    • memory-less
    • $L_k\sim\text{Geom}(p)$
      • $\mathbb E[L_k]=\frac1p$
      • $P(L=l)=(1-p)^{l-1}\cdot p$
  • $T_k$ properties
    • $T_k=L_1+\dots+L_k$
    • by linearity $\mathbb E[T_k]=\frac kp$
    • $T_k$ has Pascal distribution of order $k$
    • $P(T_k=t)=\begin{cases}{t-1\choose k-1}p^{k}(1-p)^{t-k} & \text{for }t\geq k\\ 0& \text{otherwise}\end{cases}$
• Alternative description of a Bernoulli process
  • we can describe the situation by the interarrival times
  • i.i.d. random variables $L_1,L_2,\ldots\sim\text{Geom}(p)$
  • $T_k=L_1+\dots+L_k$
  • $X_k=1$ whenever $T_t=k$ for some $t$
  • clearly, the sequence $X_1,X_2,\dots$ is a Bernoulli process
• Merging of Bernoulli processes
  • two independent Bernoulli processes, $Z_i=X_i\lor Y_i$
  • $BP(p)\text{[merge with]}BP(q)=BP(1-(1-p)(1-q))$
  • $=BP(p+q-pq)$
• Splitting of Bernoulli processes
  • $X_i,Y_i,Z_i$
  • $Z_i\sim BP(p)$
  • if $Z_i=0$, then $X_i=Y_i=0$
  • if $Z_i=1$, then with probability $q$ we set $(X_i,Y_i)=(1,0)$, otherwise $(X_i,Y_i)=(0,1)$
  • then $X_i\sim BP(pq)$ and $Y_i\sim BP(p(1-q))$
• Poisson process
  • continuous time
  • $T_1,T_2,T_3,\dots$ are the times of individual arrivals
  • $N_t$ … number of arrivals up to time $t$
  • $\lambda$ … intensity (how many successes per unit of time)
  • $N_t\sim\text{Pois}(\lambda\cdot t)$
  • $L_k\sim\text{Exp}(\lambda)$
  • $T_k$ has Erlang distribution, $\mathbb E[T_k]=\frac k\lambda$
• Poisson process interval independence
  • for any sequence $0\leq t_0\lt t_1\dots\lt t_k$
  • RVs $(N_{t_i}-N_{t_{i+1}})$
    • are independent
    • each one follows $\text{Pois}(\lambda(t_{i+1}-t_i))$
• Merging of Poisson process
  • $PP(\lambda)\text{[merge with]}PP(\lambda')=PP(\lambda+\lambda')$
• Splitting of Poisson process
  • for each success of $PP(\lambda)$, we toss a coin with probability $p$ (with probability $p$, the success is counted as valid)
  • the resulting process is $PP(\lambda p)$

Non-parametric Tests

• Permutation test
  • two-sample test
  • A/B testing
    • $A$ … control group (no treatment)
    • $B$ … group with treatment applied
    • is the $A$ vs. $B$ difference only random?
  • we observe … $T(A,B)$
    • $T$ … test statistic
    • example: $T=\bar A-\bar B$
  • $\mathcal F=\set{T(\pi(A\cup B))\mid \pi\in S_{m+n}}$
  • p-value: percentage of $\mathcal F$ more extreme than observed $T(A,B)$
  • speed-up … we use only $k$ random samples from $S_{m+n}$
  • for paired test, we only permute $X_i$ with $Y_i$
• Signed test
  • paired test
    • pairs $X_i,Y_i$
    • $Z_i=Y_i-X_i$
  • $H_0$ … $P(X_i\gt Y_i)=\frac12$
  • count number of pairs where $Z_i\gt 0$ (there was a measurable improvement after the treatment)
  • use $\text{Bin}(n,\frac12)$ to get the p-value
• Wilcoxon signed rank test
  • paired test
  • procedure
    • let $X_i$ be the difference $B_i-A_i$
    • sort by absolute value, assign ranks ($R_i$)
    • calculate $T$ (or $T^+$ or $T^-$, it does not matter)
      • $T^+=\sum_{X_i\gt 0}R_i$
      • $T^-=\sum_{X_i\lt 0} R_i$
      • $T=T^+-T^-=\sum R_i\cdot\text{sign}(X_n)$
    • compare with scores for measurements with random $+/-$ signs
  • we use stronger null hypothesis
    • $H_0:$ median = 0 & distribution of $X$ is symmetric
    • note: $X$ is symmetric $\iff A,B$ have the same continuous distribution (source)
• Mann-Whitney U-test
  • two-sample test
    • we have two populations, $X$ and $Y$
    • we get $X_1,\dots,X_m$ and $Y_1,\dots,Y_n$
    • usually, $m\neq n$
  • $S(X_i,Y_j)=\begin{cases} 1 & X_i\gt Y_j\\ \frac12 & X_i=Y_j \\ 0 & X_i\lt Y_j\end{cases}$
  • $U=\sum_{i=1}^m\sum_{j=1}^nS(X_i,Y_j)$
  • sign test is a paired variant of this
  • we use the same approach as in the permutation test with $U$ instead of $T=\bar X_m-\bar Y_n$
  • alternative view: we sort $X\cup Y$ and count pairs “$X_i$ before $Y_j$”
  • when to use it?
    • numerical data … real numbers (weight, time, price) → permutation test
    • ordinal data … classes (light/medium/heavy, quick/slow) → $U$-test

Moment Generating Functions and their applications

• Markov inequality
  • for $X$ nonnegative
  • $\forall a\geq 1:P(X\geq a\cdot \mu)\leq\frac1a$
• Chebyshev inequality
  • $\forall a\gt 0:P(|X-\mu|\geq a\cdot\sigma)\leq\frac1{a^2}$
• Chernoff bounds
  • for $X=\sum_{i=1}^nX_i$ where $X_i\sim\text{Ber}(p_i)$ are independent
  • $\mu=\sum_{i=1}^np_i$
  • $\forall\delta\in(0,1]:P(X\geq (1+\delta)\cdot\mu)\leq e^{-\mu\delta^2/3}$
  • $\forall\delta\in(0,1):P(X\leq(1-\delta)\cdot\mu)\leq e^{-\mu\delta^2/2}$
  • note: there are many more alternative bounds