Exam

• $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.

• 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)$

• we will be throwing $m$ balls randomly into $n$ bins
• $X_i$ … number of balls in bin $i$

• $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}$

• $X_i\sim \text{Bin}(m,\frac 1n)\approx\text{Pois}(\frac mn)$
• $\mathbb EX_i=\frac mn$

• 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
  • …

• theorem: for large enough $n$ we have $P(\text{maxload}\leq\frac{\log\log n}{\log n})\leq\frac1n$
• proof
  • …

• 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
  • …

• 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$

• $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}$

• 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

• 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)$

• $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))$

• 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$

• 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))$

$PP(\lambda)\text{[merge with]}PP(\lambda')=PP(\lambda+\lambda')$

• 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)$

• 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$

• 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

• 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)

• 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

• for $X$ nonnegative
• $\forall a\geq 1:P(X\geq a\cdot \mu)\leq\frac1a$

$\forall a\gt 0:P(|X-\mu|\geq a\cdot\sigma)\leq\frac1{a^2}$

• 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