Carlos Fernandez-Granda

1 probability and Statistics for Data ScienceCarlos Fernandez-GrandaPrefaceThese notes were developed for the courseProbability and Statistics for Data Scienceat theCenter for Data Science in NYU. The goal is to provide an overview of fundamental conceptsin probability and statistics from first principles. I would like to thank Levent Sagun and VladKobzar, who were teaching assistants for the course, as well as Brett Bernstein and DavidRosenberg for their useful suggestions. I am also very grateful to all my students for writing these notes, I was supported by the National Science Foundation under NSFaward York, August 2017iiContents1 Basic probability probability spaces .. Conditional probability .. Independence ..72 Random Definition .. Discrete random variables .. Continuous random variables .. Conditioning on an event .. Functions of random variables .. Generating random variables.

2 Proofs ..333 Multivariate Random Discrete random variables .. Continuous random variables .. Joint distributions of discrete and continuous variables .. Independence .. Functions of several random variables .. Generating multivariate random variables .. Rejection sampling ..644 Expectation operator .. Mean and variance .. Covariance .. Conditional expectation .. Proofs ..895 Random Definition .. Mean and autocovariance functions .. Independent identically-distributed sequences .. Gaussian process .. Poisson process .. Random walk .. Proofs .. 1076 Convergence of Random Types of convergence .. Law of large numbers .. Central limit theorem .. Monte Carlo simulation .. 1187 Markov Time-homogeneous discrete-time Markov chains .. Recurrence .. Periodicity .. Convergence .. Markov-chain Monte Carlo.

3 1378 Descriptive Histogram .. Sample mean and variance .. Order statistics .. Sample covariance .. Sample covariance matrix .. 1499 Frequentist Independent identically-distributed sampling .. Mean square error .. Consistency .. Confidence intervals .. Nonparametric model estimation .. Parametric model estimation .. Proofs .. 17610 Bayesian Bayesian parametric models .. Conjugate prior .. Bayesian estimators .. 18311 Hypothesis The hypothesis-testing framework .. Parametric testing .. Nonparametric testing: The permutation test .. Multiple testing .. 20012 Linear Linear models .. Least-squares estimation .. Overfitting .. Global warming .. Proofs .. 209 CONTENTSvA Set Basic definitions .. Basic operations .. 213B Linear Vector spaces .. Inner product and norm .. Orthogonality .. Projections.

4 Matrices .. Eigendecomposition .. Eigendecomposition of symmetric matrices .. Proofs .. 231 Chapter 1 Basic probability TheoryIn this chapter we introduce the mathematical framework of probability theory, which makes itpossible to reason about uncertainty in a principled way using set theory. Appendix A containsa review of basic set-theory probability spacesOur goal is to build a mathematical framework to represent and analyze uncertain phenomena,such as the result of rolling a die, tomorrow s weather, the result of an NBA game, etc. To thisend we model the phenomenon of interest as anexperimentwith several (possibly infinite)mutually in simple cases, when the number of outcomes is small, it is customary to reason aboutsets of outcomes, calledevents. To quantify how likely it is for the outcome of the experimentto belong to a specific event, we assign aprobabilityto the event. More formally, we defineameasure(recall that a measure is a function that maps sets to real numbers) that assignsprobabilities to each event of formally, the experiment is characterized by constructing aprobability ( probability space).

5 A probability space is a triple( ,F,P)consisting of: Asample space , which contains all possible outcomes of the experiment. A set of eventsF, which must be a -algebra(see Definition below). Aprobability measurePthat assigns probabilities to the events inF(see Definition ).Sample spaces may bediscreteorcontinuous. Examples of discrete sample spaces include thepossible outcomes of a coin toss, the score of a basketball game, the number of people that showup at a party, etc. Continuous sample spaces are usually intervals ofRorRnused to modeltime, position, temperature, term -algebra is used in measure theory to denote a collection of sets that satisfy certainconditions listed below. Don t be too intimidated by it. It is just a sophisticated way of statingthat if we assign a probability to certain events (for exampleit will rain tomorroworit will1 CHAPTER 1. BASIC probability THEORY2snow tomorrow) we also need to assign a probability to their complements ( will not raintomorroworit will not snow tomorrow) and to their union (it will rain or snow tomorrow).

6 Definition ( -algebra).A -algebraFis a collection of sets in such that:1. If a setS FthenSc If the setsS1,S2 F, thenS1 S2 F. This also holds for infinite sequences; ifS1,S2,.. Fthen i=1Si our sample space is discrete, a possible choice for the -algebra is thepower setof the samplespace, which consists of all possible sets of elements in the sample space. If we are tossing a coinand the sample space is :={heads,tails},( )then the power set is a valid -algebraF:={heads or tails,heads,tails, },( )where denotes the empty set. However, in many cases -algebras do not contain every possibleset of (Cholesterol).A doctor is interested in modeling the cholesterol levels of herpatients probabilistically. Every time a patient visits her, she tests their cholesterol level. Heretheexperimentis the cholesterol test, the outcome is the measured cholesterol level, and thesample space is the positive real line. The doctor is mainly interested in whether the patientsto have low, borderline-high, or high cholesterol.

7 The eventL(low cholesterol) contains alloutcomes below 200 mg/dL, the eventB(borderline-high cholesterol) contains all outcomesbetween 200 and 240 mg/dL, and the eventH(high cholesterol) contains all outcomes above240 mg/dL. The -algebraFof possible events therefore equalsF:={L B H,L B,L H,B H,L,B,H, }.( )The events are a partition of the sample space, which simplifies deriving the corresponding role of the probability measure P is to quantify how likely we are to encounter each of theevents in the -algebra. Intuitively, the probability of an eventAcan be interpreted as thefraction of times that the outcome of the experiment is inA, as the number of repetitions tendsto infinity. It follows that probabilities should always be nonnegative. Also, if two eventsAandBare disjoint (their intersection is empty), thenP(A B) =outcomes inAorBtotal( )=outcomes inA+ outcomes inBtotal( )=outcomes inAtotal+outcomes inBtotal( )=P(A) +P(B).

8 ( )CHAPTER 1. BASIC probability THEORY3 Probabilities of unions of disjoint events should equal the sum of the individual , the probability of the whole sample space should equal one, as it contains alloutcomesP( ) =outcomes in total( )=totaltotal( )= 1.( )These conditions are necessary for a measure to be a valid probability ( probability measure).A probability measure is a function defined over thesets in a -algebraFsuch (S) 0for any eventS If the setsS1,S2,..,Sn Fare disjoint ( Sj= fori6=j) thenP ( ni=1Si) =n i=1P (Si).( )Similarly, for a countably infinite sequence of disjoint setsS1,S2,.. FP(limn ni=1Si)= limn n i=1P (Si).( ) ( ) = two first axioms capture the intuitive idea that the probability of an event is a measuresuch as mass (or length or volume): just like the mass of any object is nonnegative and thetotal mass of several distinct objects is the sum of their masses, the probability of any eventis nonnegative and the probability of the union of several disjoint objects is the sum of theirprobabilities.

9 However, in contrast to mass, the amount of probability in an experiment cannotbe unbounded. If it is highly likely that it will rain tomorrow, then it cannot be also verylikely that it willnotrain. If the probability of an eventSis large, then the probability ofits complementScmust be small. This is captured by the third axiom, which normalizes theprobability measure (and implies that P (Sc) = 1 P (S)).It is important to stress that the probability measure doesnotassign probabilities to individualoutcomes, but rather to events in the -algebra. The reason for this is that when the numberof possible outcomes is uncountably infinite, then one cannot assign nonzero probability to allthe outcomes and still satisfy the condition P ( ) = 1. This is not an exotic situation, it occursfor instance in the cholesterol example where any positive real number is a possible the case of discrete or countable sample spaces, the -algebra may equal the power set of thesample space, which means that we do assign probabilities to events that only contain a singleoutcome ( the coin-toss example).

10 CHAPTER 1. BASIC probability THEORY4 Example (Cholesterol (continued)).A valid probability measure for Example isP (L) = ,P (B) = ,P (H) = ( )Using the properties, we can determine for instance that P (B H) = + = has the following consequences:P ( ) = 0,( )A Bimplies P (A) P (B),( )P (A B) = P (A) + P (B) P (A B).( )We omit the proofs (try proving them on your own). Conditional probabilityConditional probability is a crucial concept in probabilistic modeling. It allows us to updateprobabilistic models when additional information is revealed. Consider a probabilistic space( ,F,P) where we find out that the outcome of the experiment belongs to a certain eventS F. This obviously affects how likely it is for any other eventS Fto have occurred: wecan rule out any outcome not belonging toS. The updated probability of each event is knownas theconditional probabilityofS givenS. Intuitively, the conditional probability can beinterpreted as the fraction of outcomes inSthat are also inS ,P(S |S)=outcomes inS andSoutcomes inS( )=outcomes inS andStotaltotaloutcomes inS( )=P (S S)P (S),( )where we assume that P (S)6= 0 (later on we will have to deal with the case whenShaszero probability , which often occurs in continuous probability spaces).