Lectures¶
1.-7. See web of Václav Rozhoň¶
8. Balls-into-bins.¶
Birthday paradox. (You may want to check a calculator of exact probabilities for it.)
Balls&bins: visualisation of the process, distribution of individual bin, applications (bucketsort, hashing). Maxload estimates: from above directly. We used twice the union bound from Prob&Stat 1. For the other estimate we started explaining the Poisson approximation. (Will be finished next week.)
Video recording A Video recording B
9. Balls-into-bins (Poisson approximation). Bernoulli process.¶
Two examples of how the Poisson approximation works (coupon collector and maxload). Sorry for the mess in the final estimate calculation, much simpler version in the lecture notes.
We didn't get to this in the class, but here is a simulation to illustrate the Poisson approximation of maxload as a Jupyter notebook and as a pdf. Also see a nice visualisation of the "power of two choices"
A short intro to Bernoulli (and Poisson) processes), more on this next week.
Video recording A Video recording B
10. Bernoulli & Poisson process.¶
(At the end of first recording I haven't moved the camera back to the table. Look at the strt of the recording B to see what I was writing :) )
We saw four related ways to describe the same random process -- sequence of Bernoulli random variables \(X_i\), arrival times \(T_k\) when we get \(k\)-th 1 among the \(X_i\)'s, waiting times \(L_k = T_k - T_{k-1}\), and number of arrivals \(N_n\). Merging, splitting of Bernoulli processes.
Then we turned to the continuous approximation by Poisson process, where we measure the arrival and waiting times in real numbers.
Illustration of the processes (synthetic data)
Video recording A Video recording B
10. Nonparametric statistics.¶
We briefly recalled what are 1-sample, 2-sample and pair tests. How do one-sided and two-sided tests differ, and why randomized experiment is better than observational study. Mainly, we looked at Wilcoxon rank test and Mann-Whitney U test, at permutation tests and (very briefly) touched the topic of bootstrapping.