# Probability and Statistics in Computing

## Lecture notes

**2019-09-23**.*Preliminaries 3 (contd.): The Cramér-Rao inequality and lower bounds on the variance of estimators. Interlude and revision: Randomized rounding for MAX-CUT.***2019-09-19**.*Preliminaries 3 (contd.): Relative-entropy based minimax lower bounds for testing multiple hypotheses: examples. Excursion: Equivalence of Pinkser’s inequality and Hoeffding’s lemma.*See chapter 2 of Tsybakov, 2009.

Notes on connections between Pinsker’s inequality and concentration.

**2019-09-16**.*Preliminaries 3 (contd.): Minimax lower bounds with multiple hypotheses.*- See chapter 2 of Tsybakov, 2009.

**2019-09-12**.*Preliminaries 3: Discussion of \(\varepsilon\)-nets; example: operator norm of a random matrix. Minimax lower bounds. Information theoretic lower bounds for distinguishing Bernoulli distributions.***2019-09-09**.*Analysis of clustering after projection to the principal component (contd.); \(\varepsilon\)-nets. Issues with conditioning on the observed data and fixes.*- See also
*Vempala and Wang*, JCSS 80(4), 2004.

- See also
**2019-09-05**.*Analysis of clustering after projection to the principal component (contd.). Properties of the principal component.*- See also
*Vempala and Wang*, JCSS 80(4), 2004.

- See also
**2019-08-29**.*Analysis of distance based clustering. Possibilities for improvement. The singular value decomposition.***2019-08-26**.*Properties of Gaussian vectors. Distance-based clustering of Gaussian mixtures.*`julia`

notebook. Needs to be run as an`IJulia`

notebook environment for the`julia`

programming language.

**2019-08-22**.*Preliminaries 2: Some probability estimates for spheres and balls in \(\mathbb{R}^d\).***2019-08-19**.*Preliminaries 1: Basic hypothesis testing terminology. The Neyman-Pearson lemma.*

## General information

**Instructor:** Piyush Srivastava

**Schedule:** Mondays and Thursdays, 1400-1530, A-201.

## Grading/Assignments

**Homework 4**. Due December 10, 2100IST. Last updated version hash:`ca4c390`

, December 2. Files required for Q2 are here.**Homework 3**. Due November 11, before class. Last updated version hash:`354a930`

, October 28.**Homework 2**. Due October 7, before class. Last updated version hash:`de0ba01`

, September 23.**Homework 1**. Due September 5, before class. Last updated version hash:`7093495`

, August 30.

## References

*Foundations of Data Science*. A. Blum, J. E. Hopcroft, R. Kannan. To be published by Cambridge University Press.*Introduction to Nonparametric Estimation*. Alexandre B. Tsybakov. Springer Series in Statistics, 2009.