# ---
# jupyter:
#   jupytext:
#     text_representation:
#       extension: .py
#       format_name: light
#       format_version: '1.5'
#       jupytext_version: 1.14.4
#   kernelspec:
#     display_name: Python 3
#     language: python
#     name: python3
# ---

# ## 18.1 Unit overview

# ### 18.1.1 Motivation
#
# https://youtu.be/Xj-QvRBDEi8
#
# Notes:
#
# - Airline overbooked tickets due to 10% passengers on average being not present. What's the maximum number of tickets an airline should sell on a flight with 300 seats? You'll know how to calculate it using central limit theory.

# ## 18.2 Lecture 18 Inequalities, convergence, and the Weak Law of Large Numbers

# ### 18.2.1 Unit 8 overview
#
# https://youtu.be/Kgjc7VU3nUk
#
# The material is covered in section 5.1-5.4 and 9.1 of the text.
#
# - Weaklaw of large numbers: the observed avg of a large number of independent identically distributed random variables, called sample mean, converged to expected value
# - Central limit theorem: provide details of the distribution of the sum of n i.i.d r.v.s. 
# - Estimate an unknow mean with measurements of "accuracy of estimates" and "confidence intervals"
# Note: It's different from previous estimation on:
# (1) make no assumption on the unknown quantity that is being estimated.
# (2) not modeled as a r.v but just as an unknown constant
# (3) cannot invoke the Bayers rule
# Thus it's a very different conceptual setting, called non-Bayersian or classical statistics.
# - Basic rule of classical statistics

# ### 18.2.2 The Markov inequality
#
# https://youtu.be/7OYJoExDHA0
#
# Notes:
#
# Basic ideas under the Markov inequality and many other inequalities and bounds in probability theory:
#
# - learn about probabiliteis of "extreme events" which some variables take very large value
# - Markov inequality: if $X \geq 0$ and $a > 0$, then $P(X \geq a) \leq \frac{E[X]}{a}$: the probability of X that exceeds a is bounded
#
# **Derive method 1**
# Assume X is a conteneous r.v.s (the discrete case is similar), then 
#
# $E[X] = \int_{0}^\infty xf_x (x)d_x \geq \int_{a}^\infty xf_x(x)d_x \geq \int_{a}^\infty af_x(x)d_x = aP(x \geq a)$
#
# **Derive method 2**
#
# $$
# Y = \left\{
#   \begin{array}\\
#      0 & \mbox{if } X < a \\
#      a & \mbox{if } X \geq a \\
#   \end{array}
# \right.
# $$
#
# We know $aP(X \geq a) = E[Y] \leq E[X]$
#
# - Two examles: watch them again

# ### 18.2.3 Exercise Markov inequality
#
# <img src="images/18.2.3 Exercise Markov inequality.png">

# ### 18.2.4 The Chebyshev inequality
#
# https://youtu.be/1vUkgWZf8xU
#
#
# Notes:
#
# - The Chebyshev inequality: Given a r.v. X with finite mean $\mu$ and variance $\sigma^2$, if the variance is small, then X is unlikely to be too far from the mean. Mathematically, $P(|X - \mu| \geq c) \leq \frac{\sigma^2}{c^2}$
#
# - It is a simple application of the Markov inequality but contain a different message
#
# - How to prove:  $P(|x - \mu|) = P((x - \mu)^2) \leq \frac{E[(x-\mu)^2]}{c^2} = \frac{\sigma^2}{c^2}$
#
# Application Example 1:
# The distance from mean is at least k standard deviations where k > 0.
#
# $P(|X - \mu| \geq k\sigma) \leq \frac{\sigma^2}{k^2 \sigma} = \frac{1}{k^2}$
#
#
# Application Example 2:
#
# X is exponential ($\lambda = 1$): $P(X \geq a) \leq \frac{1}{a}$ (Markov)
#
# <img src="images/18.2.4 Exercise Chebyshev inequality.png">
#
# It indicates that The Chebyshev inequality gives us a much smaller bound and therefore more informative than what we obtained from the Markov inequality as it exploits more information about the distribution of the r.v. X., which not just use the knowledge of mean of the r.v. but also use some information about the variance of the r.v.

# ### 18.2.5 Exercise Chebyshev inequality
#
# <img src="images/18.2.5 Exercise Chebyshev inequality.png">

# ### 18.2.6 Exercise Chebyshev versus Markov
#
# <img src="images/18.2.6 Exercise Chebyshev versus Markov.png">

# ### 18.2.7 The Weak Law of Large Numbers
#
# https://youtu.be/YOPiC3oLogU

# ### 18.2.8 Exercise Sample mean bounds
#
# <img src="images/18.2.8 Exercise Sample mean bounds.png">

# ### 18.2.9 Polling
#
# https://youtu.be/-sLyJw06tL8
#
# **The pollster's problem**
#
# - You want to predict what p actually is before the referendum starts. Here p is fraction of population that will vote "yes" in a referendum
# - You select randomly/uniformly a number of people out of the population and record their answer. That is ith randomly selected person polled: 
# $X_i = \left\{
#   \begin{array}\\
#         1, & \mbox{if yes,}\\
#         0， & \mbox{if no.}
#   \end{array}
#   \right.$
# thus $E[x_i] = p$
# Note: We assume we select those people independently then there is always a chance that the 1st person polled will be the same as the 2nd person polled, which we don't want to happen. However, if we assume the population is very large, then this won't happen and will not be a concern.
# - we obtain $M_n = (X_1 + ... + X_n)/n$: fraction of "yes" in the sample, which is a reasonable estimate of the unknow fraction p
# - Here is the scenario:
#
# Boss: Please find the exactly value of p
#
# You: There is no way to calculate p exactly on the basis of a finite and random poll.Therefore, there will be some error in the estimation of p
#
# Boss: Ok. Then try to give me an estimate of p which is very accurate within 1%. Can you do this for me? 
#
# You: Ok. Let me try polling 10,000 people and see if I can guarantee for you such a small error. You realized later that actually there is no way of guaranteeing such a small error with certainty. So you told your boss that " I cannot guarantee with certainty that the error is going to be small, but I can guarantee that the error that I get is small with high probability.
#
# - $|M_n - p| < 0.01$ try n = 10,000 samples
#
# - $P(|M_{10000} - p| \geq 0.01) \leq \frac{\sigma^2}{n \epsilon^2} = \frac{p(1-p)}{10^4 10^{-4}} \leq \frac{1}{4}$
#
# You: if I sample 10,000 people, then the probability of an error more than 1% is going to be less than 25%
#
# Boss: Well, 25% is too big which is unacceptable. I'd like you have a probability of error that is less than 5%.
#
# You: caluclate $\frac{1/4}{n 10^{-4}} \leq 0.05$ => $n \geq \frac{10^6}{20} = 50,000$ and tell your boss that one way of guaranteeing 5% is to take 50000 samples. Here 0.01 is the accuracy, and 5% is the confidence interval.
#
# Summary: the above calculation is based on the Chebyshev inequality which is not that accurate. It turns out that if we use more accurate estimates of this probability, we will find actually much smaller values of n will be enough for our purpose.

# ### 18.2.10 Exercise Polling
#
# <img src="images/18.2.10 Exercise Polling.png">
#
# **MIT Staff Q&A**
#
# - the probabilistic assumption being made here is the following: sampling is done with replacement and every individual in the population has an equal chance of being polled on each iteration of the sampling (You randomly pick (sample) the first individual from the population; then randomly pick the second individual, then the thirds, then the fourth, ....). Of course, people's opinions are not "independent". But the answers we obtain from randomly sampled individuals, are statistically independent and distributed according the population of opinions from which we are sampling.
#
# - **Q**: "a) is ambiguous, the accuracy requirements can be looser or no, this is not the mathematical case, and even in answer you use word "most"." 
#
#   **A**：I agree with you opinion. In the "real world", the accuracy and confidence requirements can be dramatically different: in experimental physics the statistical standards are very high, in observational studies of social issues, the accuracy is determined by the available data and are often much lower than for experiments ("polls") conducted in a lab. 
#
# - **Q**: What does "the Chebyshev bound is too conservative." mean? 
#
#   **A**: It means although it is right, but maybe not close to the true probability. Think about I tell you that someone's height is less than 3 meters. I am right(no one is higher than 3 meters), but this is not a useful information, in this case, I am conservative. Hope it helps.
#
#

# ### 18.2.11 Convergence in probability
#
# https://youtu.be/yT102uPFJw4
#
# **Notes**:
#
# - **Definition**: a sequence of random variables $Y_n$ (not necessarily independent) **converges in probability** to a number <font color='red'>**a**</font> if:
# for any $\epsilon > 0, \lim_{x \to \infty}P(|Y_n - a| \geq \epsilon) = 0$
#
# - In WLLN, it tells us that with high probability, the sample mean falls close to the true mean as n goes to infinity which we interpret it as "$M_n$ converges to $\mu$" in the sense of convergence in probability.
#
# - Convergence comparison
# <img src="images/18.2.11 Convergence in probability.png">
#
# - Some properties of convergence of sequences:
#
# Support that $X_n -> a, Y_n -> b in probability. We do not make any assumptions about independence. That's to say we don't assume the Xn's are independent of each other and the sequence of Xn's is independent of Yn.
#
# Property 1: If g is continuous, then g(Xn) -> g(a);
#
# Property 2: Xn + Yn -> a + b
#
# **However**, E[Xn] need not converge to a, which means convergence of random variables in probability does not imply convergence of expectations.

# ### 18.2.12 Convergence in probability examples
#
# https://youtu.be/Ti0syfE2e4c
#
# **Example 1:**
#
# A sequence of random variables Yn that are discrete. Most of the probabilitiy is concentrated at 0 but there is also a small probability of a large value. Do we have convergence in probability to 0?
#
# <img src="images/18.2.12 Convergence in probability examples1.png">
#
# - convergence in probability (CIP) does not imply convergence of expectations as CIP has to deal with the bulk of the distribution, it only cares the tail of the distribution has small probability. On the other hand, the expectation is highly sensitive to the tail of the distribution. It might be that the tail only has a small probability but if that probability is assigned to a very large value, then the expectation will be strongly affected and can be quite different from the limit of the random variable.
#
# **Example 2:**
# <img src="images/18.2.12 Convergence in probability examples2.png">
#
# **Steps to show convergence in probability**
# - Step 1: make a guess as to what is the value that the sequence converges to.
# - Step 2: write down an expression for the probability of being epsilon away from the conjectured limit.
# - Step 3: calculate that probability 

# ### 18.2.13 Exercise Convergence in probability
#
# <img src="images/18.2.13 Exercise Convergence in probability.png">

# ### 18.2.14 Related topics
#
# https://youtu.be/mR2udEr2pPM

# ## 18.3 Lecture 19 The Central Limit Theorem

# ### 18.3.1 Lecture 19 overview and slides
#
# https://youtu.be/H-llL9ke_pA
#
# Section 5.4 of the textbook.

# ### 18.3.2 The Central Limit Theorem
#
# https://youtu.be/ethm2HoZtE8

# ### 18.3.3 Exercise CLT
#
# <img src="images/18.3.3 Exercise CLT.png">

# ### 18.3.4 Discussion of the CLT
#
# https://youtu.be/43tM56dYwIw

# ### 18.3.5 Exercise CLT applicability
#
# <img src="images/18.3.5 Exercise CLT applicability1.png">
# <img src="images/18.3.5 Exercise CLT applicability2.png">

# ### 18.3. 6 Illustration of the CLT
#
# https://youtu.be/Q8g3sPvxHUw

# ### 18.3.7 CLT examples
#
# https://youtu.be/0XaD4PXmJbk

# ### 18.3.8 Exercise CLT practice
#
# <img src="images/18.3.8 Exercise CLT practice.png">

# ### 18.3. 9 Normal approximation to the binomial
#
# https://youtu.be/Zr8KmnfQNJw

# ### 18.3.10 Exercise CLT for the binomial
#
# <img src="images/18.3.10 Exercise CLT for the binomial.png">

# ### 18.3.11 Polling revisited
#
# https://youtu.be/8PLZvnmTkQk

# ## 18.4 Lecture 20 An introduction to classical statistics

# ### 18.4.1 Lecture 20 overview and slides
#
# https://youtu.be/UC9Tlm3l7AE
#
# Refer to section 9.1 of the text.
#
# Notes:
#
# a brief introduction to the so-called classical (non-Bayesian) statistical methods:
#
# - the general framework
# - estimation based on sample means, confidence intervals, and maximum likelihood estimation. 

# ### 18.4.2 Overview of the classical statistical framework
#
# https://youtu.be/vdaxiJBG7qs

# ### 18.4.3 The sample mean and some terminology
#
# https://youtu.be/Fz_7ymWGx0o

# ### 18.4.4 Exercis Estimator properties
#
# <img src="images/18.4.4 Exercis Estimator properties.png">

# ### 18.4.5 On the mean squared error of an estimator
#
# https://youtu.be/Rw5uq3Js9ZA

# ### 18.4.6 Confidence intervals
#
# https://youtu.be/16P8lB9TPMo

# ### 18.4.7 Exercise Bias and MSE
#
# <img src="images/18.4.7 Exercise Bias and MSE.png">

# ### 18.4.8 Exercise Confidence interval interpretation
#
# <img src="images/18.4.8 Exercise Confidence interval interpretation.png">

# ### 18.4.9 Exercise A simple CI
#
# <img src="images/18.4.9 Exercise A simple CI.png">

# ### 18.4.10 Confidence intervals for an unknown mean
#
# https://youtu.be/ekLmfHCbXOA

# ### 18.4.11 Exercise CI's via the CLT
#
# <img src="images/18.4.11 Exercise CI's via the CLT.png">

# ### 18.4.12 Confidence intervals for the mean when the variance is unknown
#
# https://youtu.be/SBS06u2KwFU

# ### 18.4.13 Other natural estimators
#
# https://youtu.be/Vev2rMQOYtw

# ### 18.4.14 Exercise Natural estimators
#
# <img src="images/18.4.14 Exercise Natural estimators.png">

# ### 18.4.15 Maximum likelihood estimation
#
# https://youtu.be/af6iD1AA6rY

# ### 18.4.16 Maximum likelihood estimation examples
#
# https://youtu.be/osCutN2MFzA

# ### 18.4.17 Exercise ML estimation
#
# <img src="images/18.14.17 Exercise ML estimation.png">

# ## 18.5 Solved Problems

# ### 18.5.1 Convergence in probability example
#
# <img src="images/18.5.1 Convergence in probability example.png">
#
# https://youtu.be/rTectvxtPm4
#
#

# ### 18.5.2 Convergence in probability and in the mean square - Part I
#
# <img src="images/18.5.2 Convergence in probability and in the mean square - Part I.png">
#
# https://youtu.be/HRFM5q6374o
#
# <img src="images/18.5.2 Convergence in probability and in the mean square - Part I1.png">

# ### 18.5.3 Convergence in probability and in the mean square - Part II
#
# <img src="images/Convergence in probability and in the mean square - Part II.png">
#
# https://youtu.be/eoKxh7eznr4

# ### 18.5.4 Probability bounds
#
# <img src="images/18.5.4 Probability bounds.png">
#
# https://youtu.be/8s6hXXA9mKM

# ### 18.5.5 Using the CLT to estimate the probability of a wrong decision
#
# <img src="images/18.5.5 Using the CLT to estimate the probability of a wrong decision.png">
#
# https://youtu.be/qjtb4VTNOQQ

# ### 18.5.6 Using the CLT
#
# <img src="images/18.5.6 Using the CLT.png">
#
# https://youtu.be/9Xl2fRK3q9M

# ### 18.5.7 An unbiased variance estimator
#
# <img src="images/18.5.7 An unbiased variance estimator.png">
#
# https://youtu.be/6H_Wmn9kozg
#
# Solution can be found on pages 467-468 of the text.

# ## 18.6 Additional theoretical material

# ### 18.6.1 Convergence of the sum of two random variables
#
# <img src="images/18.6.1 Convergence of the sum of two random variables.png">
#
# https://youtu.be/p3oDXka-dgw

# ### 18.6.2 Jensen's inequality
#
# <img src="images/18.6.2 Jensen's inequality.png">
#
# https://youtu.be/AG8Aa3fTucA

# ### 18.6.3 Hoeffding's inequality
#
# <img src="images/18.6.3 Hoeffding's inequality.png">
#
# https://youtu.be/ABmRmeRGtb0

# ## 18.7 Problem Set 8

# ### 18.7.1 Convergence in probability
#
# <img src="images/18.7.1 Convergence in probability1.png">
# <img src="images/18.7.1 Convergence in probability2.png">

# ### 18.7.2 Find the limits
#
# <img src="images/18.7.2 Find the limits.png">

# ### 18.7.3 The sample mean
#
# <img src="images/18.7.3 The sample mean1.png">
# <img src="images/18.7.3 The sample mean2.png">

# ### 18.7.4 Airline overbooking
#
# <img src="images/18.7.4 Airline overbooking.png">

# ### 18.7.5 Maximum likelihood estimation
#
# <img src="images/18.7.5 Maximum likelihood estimation.png">

# ### 18.7.6 Tossing a triple of coins
#
# <img src="images/18.7.6 Tossing a triple of coins.png">

# ## 18.8 Unit 8 Summary
#
# https://youtu.be/rojy7JB76wM

#

StarcoderdataJupyterScriptsDedupFiltered