We introduce natural collection of subsets

Remark: \sigma(\mathcal{C}) always exists since, alternatively, you can think of it as the intersection of all \sigma-algebras which contains \mathcal{C}. Indeed we always have \mathcal{C} \subset 2^\Omega and arbitrary intersections of \sigma-algebras are \sigma-algebras (see Homework for more details).

An important characterization of the Borel \sigma-algebra of \mathbb{R} is the following. It will play a big role to characterize random variables

Proof of Theorem 1.5.

• Independence: P(A \cap B^c)= P(A) - P(A \cap B) = P(A) - P(A)P(B) = (1-P(A))P(B) =P(A^c)P(B).

We recall some standard probability models

The Poisson distribution is ubiquitous, in particular because of its relation with the binomial distribution (sometimes called The Law of small numbers see Theorem 2.1). Typical examples are the number of typos in a page, the number of earthquakes hitting a region, the number of radiactive atoms decay, etc…

The Pareto distribution is a model with polynomial tails. It is widely used in economics where polynomial tails often occurs. Classical example is the the wealth distribution in a population, or the size of cities, or the number of casualties in wars. See the Pareto principle (“20% of the population controls 80% of the wealth”) and the examples in this paper

Sometimes the negative binomial is defined slightly differently and counts the number of failure until the k^{th} success occurs.

Examples:

1. Poisson RV: X: \Omega \to \mathbb{N} and P(X =j)=e^{-\lambda}\frac{\lambda^j}{j!}. Then E[X]=\sum_{j=0}^\infty j e^{-\lambda}\frac{\lambda^j}{j!} \sum_{j=1}^\infty e^{-\lambda}\frac{\lambda^j}{(j-1)!}=\lambda \sum_{j=0}^\infty e^{-\lambda}\frac{\lambda^j}{j!} =\lambda

2. Bernoulli (Indicator) Random variable: Given an event A define X_A: \omega \to \{0,1\} by X_A(\omega) = \left\{ \begin{array}{cl} 1 & \omega \in A \\ 0 & \omega \notin A\\ \end{array}\right. Then E[X_A] = 1 P(A) + 0(1-P(A)) =P(A)

3. Binomial Random variable: The Binomial RV can be written as sum of n Bernoulli. From this we see immediately that E[X]=np.

4. Zeta RV: If X is has zeta distribution with parameter \alpha>0 then E[X] = \sum_{n=1}^\infty n \frac{1}{\zeta(\alpha+1)} \frac{1}{n^{\alpha+1}} = \frac{1}{\zeta(\alpha+1)} \sum_{n=1}^\infty \frac{1}{n^{\alpha}} = \left\{ \begin{array}{cl} \frac{\zeta(\alpha)}{\zeta(\alpha+1)} & \alpha >1 \\ +\infty & 0 < \alpha \le 1 \end{array} \right.

5. Geometric RV: We have with q=1-p E[X]=\sum_{n=1} nq^{n-1} p = p \frac{d}{dq} \sum_{n=0}^\infty q^n = p \frac{d}{dq} \frac{1}{1-q} = p \frac{1}{(1-q)^2} = \frac{1}{p}

6. Negative binomial RV: Since a negative binomial with paramter k is the sum of k geometric RV we have E[X]=\frac{k}{p}.

7. Uniform distribution on \Omega=\{1,2,\cdots, N\}: we have p_j=\frac{1}{N} for every j and thus E[X] = \frac{1}{N}(1 + 2 + \cdots +N) = \frac{1}{N} \frac{N(N+1)}{2}=\frac{N+1}{2}

8. A RV wihtout expectation: Suppose p_n = c_n \frac{1}{n^2} for n \in \mathbb{Z}\setminus \{0\} and p_0=0 and for a suitable normalization c_n.
   Then the series for the expecation
   \sum_{n=-\infty}^\infty n p_n is undefined because \sum_{n> 0}np_n =\infty and \sum_{n< 0}np_n = -\infty.

Fortunately it is enough to check the condition for a few sets

Remark: One can always rewrite a simple function in canonical form if needed. Just make a list of the values the function takes b_1, b_2, \cdots, b_m and set B_i=\{x, f(x)=b_i\}.

Adding some terminology

The interpretation is that this \sigma-algebra contains all the “information” you can extract from the probability measures P simply by using the random variable X. This will play an increasingly important role in the future!

Remarks:

• Note that F is in general not (left)-continuous. Indeed if s \nearrow t then (-\infty, s) \nearrow (-\infty,t) and P^X( (-\infty,t] )=P^X( (-\infty,t) ) + P^X( \{t\}). We denote the left limit by F(t-).

• One can compute probabilities using the CDF. For example

  • P( a < X \le b ) = F(b)-F(a)

  • P( a \le X \le b ) = F(b) - F(a-)

  • P( X=b ) = F(b)-F(b-)

Another way to define a CDF is to use a PDF (=probability density function).

For now think of the integral as a Riemann integral (e.g. f is piecewise continuous). We will revisit this later when equipped with better integration tools. Many of the classical distributions in probability are given by densities. Here are some examples which will come back.

Examples of PDF:

1. Uniform RV on [a,b]: This random variable takes values uniformly distributed in the interval [a,b]. f(x)= \left\{ \begin{array}{cl} \frac{1}{b-a} & a \le x \le b \\ 0 & \text{otherwise} \end{array} \right. \quad \quad F(x)= \left\{ \begin{array}{cl} 0 & x \le a \\ \frac{x-a}{b-a} & a \le x \le b \\ 1 & x \ge b \end{array} \right.

2. Exponential RV with parameter \beta:

f(x)= \left\{ \begin{array}{cl} 0 & x \le 0 \\ \beta e^{-\beta x} & x \ge 0 \end{array} \right. \quad \quad F(x)= \left\{ \begin{array}{cl} 0 & x \le 0 \\ 1 - e^{-\beta x} & x \ge 0 \\ \end{array} \right.

3. Gamma RV with parameters (\alpha,\beta):

4. Weibull distribution with parameters (\alpha,\beta):

5. Normal distribution with parameters (\mu, \sigma^2): The normal distribution has parameter \mu \in \mathbb{R} f(x)= \frac{1}{\sqrt{2 \pi \sigma^2}} e^{-\frac{(x-\mu)^2}{2 \sigma^2}} \quad \quad F(x)=\int_{-\infty}^x f(t) \, dt

6. Log-normal distribution parameters (\mu, \sigma^2):

7. Laplace distribution with parameters (\alpha,\beta): This is a 2-sided and shifted version of the exponential distribution. f(x)= \frac{\beta}{2} e^{-\beta|x-\alpha|}

8. Cauchy distribution with parameters (\alpha,\beta): This is an example of distribution without a finite mean f(x)= \frac{1}{\beta \pi} \frac{1}{1+(x-\alpha)^2/\beta^2} \quad \quad F(x) =\frac{1}{\pi} \arctan\left( \frac{x-\alpha}{\beta}\right) + \frac{1}{2}

9. Pareto distribution with paramters (x_0,\alpha):

The function F(t) is CDF in good standing. We have P([1/3,2/3])=0 as well as P([1/9,2/9])=P([7/9,8/9])=0$ and so on. In particular there are 2^{n-1} intervals of lengths 3^n whose probability vanishes. The total lenghts of all the interval on which the probability vanish is \frac{1}{3} + 2 \times \frac{1}{9} + 4 \frac{1}{27} =\sum_{n=0}^\infty \frac{2^{n-1}}{3^n} = 1.

A random variable X with CDF F(t) is neither continuous (in the sense of having a density), nor discrete.

We now make a choice to make it unique (other conventions occur in the literature).

Remark:

• Q is well defined since F being increasing and right-continuous implies that \{t\,:\,F(t)\ge p\}=[a,\infty)
  and thus the mimimum exists.

• Q(p) is a p-quantile since if s=Q(p) then F(s)\ge p and, for any t< s, F(t)<p. Therefore F(s-)\le p. In fact this shows that Q(p) is the smallest p-quantile of X.

• If we had picked \widetilde{Q}(t)=\inf \{ t\,:\, F(t) > p \} this would have given us the largest p-quantile (a fine choice as well).

We turn next to constructing all probabilities on \mathbb{R}. To do this we first need to construct at least one.

Equipped with this we can now prove

Another way to interpret this result is that we have constructed a probability space for any RV with a given CDF. Namely we constructed a probability space (here (\Omega,\mathcal{A},P)=([0,1],\mathcal{B},P_0)) (here P_0) is the Lebesgue measure on [0,1] and a map X=Q (the quantile function) with Q:[0,1] \to \mathbb{R}.

Remarks Let us make a number of comments on the definition.

1. If the simple RV is not in canonical form, i.e. X=\sum_{i=1}^N a_i 1_{A_i}. Then E[X]=\sum_{n}a_i P(A_i).

2. The preceeding remark implies that if X and Y are simple random variables then E[X +Y]=E[X]+ E[Y] (linearity of expectation).

3. If X and Y are simple and nonnegative and X \le Y then E[X]\le E[Y]. This follows from the linearity by writing Y= X + (Y-X) and so E[Y] =E[X] + E[Y-X]. If Y-X \ge 0 then E[Y-X]\ge 0 and so E[X]\le E[Y].

4. The function d_n are increasing in n, d_n(x) \le d_{n+1}(x) and this implies that X_n \le X_{n+1} and thus E[X_n] \le E[X_{n+1}].
   Therefore the limit in Equation 6.2 always exists but could well be equal to +\infty.

5. The definition in item 2. seems somewhat arbitrary since it is using a particualr choice of simple function d_n. We will show soon that this choice actually does not matter.

6. For general X we allow the expectation to equal to +\infty (if E[X_+]=\infty] and E[X_-]<\infty]) or (-\infty if E[X_+]<\infty] and E[X_-]=\infty]). If both E[X_+]=\infty] and E[X_-]=\infty] the expectation is undefined.

7. If X:\omega \to \overline{\mathbb{R}} is is extended real-valued we can still define expectation in the same way.

Claim: Suppose Y is simple and Y \le X then \lim_{n \to \infty} E[X_n] \ge E[Y].

Indeed if the claim is true \lim_{n \to \infty} E[X_n] \ge E[d_k \circ X ] for all k and taking the limit k \to \infty concludes the proof.

To prove the claim take b \ge 0 and consider the set B=\{ X > b\} and set B_n =\{ X_n >b \}. Since B_n \nearrow B we have P(B_n) \to P(B) by sequential continuity. Furthermore X_n 1_{B} \ge X_n 1_{B_n} \ge b 1_{B_n} which implies, by monotonicity, that E[X_n 1_{B}] \ge b P(B_n) and taking n \to \infty we obtain \lim_{n \to \infty} E[X_n 1_B]\ge b P(B). \tag{6.4} Now this inequality remains true if we consider the set \overline{B}=\{ X \ge b\} instead of B. To see this, take an increasing sequence b_m \nearrow b so that \{X >b_m\} \nearrow \{X \ge b\}. Indeed apply Equation 6.4 (with b replaced by b_m) and then used monotonicity.

To conclude note that if Y=\sum_{i=1}^m a_i 1_{A_i} (in canonical form) and X\ge Y then X\ge a_i on A_i. By finite additivity, using Equation 6.4, we have \lim_{n \to \infty} E[X_n] = \sum_{i=1}^m \lim_{n \to \infty} E[X_n 1_{A_i}] \ge \sum_{i=1}^m a_i P(A_i) = E[Y] and this concludes the proof. \quad \square

Almost sure properties:

• We say that two RVs X and Y are equal almost surely if P(X=Y)= P(\{\omega\,:\, X(\omega)=Y(\omega)\})=1 that is X and Y differ on a negligible set. We write X=Y a.s.

• If X=Y almost surely then E[X]=E[Y]. Indeed then the simple approximations satisfies X_n=Y_n almost surely. If two random variables are equal almost surely then their expectations are equal (use the canonical form).

• We say, for example, that X \ge Y a.s if P(\{\omega\,:\, X(\omega)\ge Y(\omega)\}=1.

• We say X_n converges to X almost surely if there exists a negligible sets N such that for all \omega \in \Omega \setminus N we have \lim_{n}X_n(\omega)=X(\omega).

Variation on Fatou’s Lemma: One can deduce directly from Fatou’s Lemma the following results

1. If X_n \ge Y and Y is an integrable RV then E[\liminf_{n} X_n] \le \liminf_{n} E[X_n].
   Proof: Apply Fatou’s Lemma to the RV Y_n=X_n-Y which is nonnegative.

2. If X_n \le Y and Y is an integrable RV E[\limsup_{n} X_n] \ge \limsup_{n} E[X_n]. Proof: Apply Fatou’s Lemma to the RV Y_n=Y-X_n which is nonnegative.

3. We shall use these versions of Fatou’s Lemma to prove our next big result, the Dominated Convergene Theorem.

4. The Fatou’s Lemma tells us that you can “lose probability” but never gain it. For example if X_n \to 0 then \liminf_n E[X_n] \ge 0.
   For example if we take \Omega=[0,1] and P the Lebesgue measure. Let X_n(\omega)= n 1_{[0,\frac{1}{n}]}(\omega) Then E[X_n]=nP([0,\frac{1}{n}])=1 for all n. But X_n \to 0 a.s. and so E[\lim_n X_n] =0 \not =1.

A special case of the dominated convergence theorem is frequently used

Remark on almost sure versions:

Monotone convergence theorem, Fatou’s lemma and dominated convergence theorem has also almost sure versions.
For example if Y is integrable and |X_n| \le Y almost surely and X_n(\omega)\to X almost surely then \lim_{n} E[X_n]=E[X]. To see this define N=\{\omega \,:\, |X_n(\omega)|\le Y(\omega) \text{for all } n \} \quad \text{ and } \quad M= \{\omega\,:\,\lim_{n} X_n(\omega)= X(\omega) \} Then P(M^c)=P(N^c)=0. We can modify the RV on sets of measures of 0 in such a way that the statements hold for all \omega: set X_n=0, X=0, Y=0 on M^c \cup N^c. Then the properties holds for all \omega and since the expectations do not change we are done.

Consequences:

• If X is a real-valued random variable, we can compute its expectation as doing an integral on \mathbb{R}

• If X is real-valued and h: \mathbb{R} \to \mathbb{R} is a (measurable) function (e.g. X^{n}, or e^{i\alpha X}, or \cdots. Then we
  have E[X]= \int_{\mathbb{R}} x dP^X(x)\, \quad E[X^n]= \int_{\mathbb{R}} x^n dP^X(x)\, \quad \cdots An alternative would to compute the distribution P^Y of the Y=X^n and then we have E[X^n] = E[Y] = \int_{\mathbb{R}} y dP^Y(y)

• Generally we will compute E[h(X)] using the distribution of X ….

• But often we will work backward. We will use the change of variable formula to compute the distribution of Y (see item 3. in Theorem 6.8). Checking the equality for all non-negative function or all characteristic function is not always easy so we will show that one can restrict onesleves to just nice functions! (Later..)

• Examples forthcoming

Location-scale family of random variables: A family of random variables parametrized by parameter \alpha \in \mathbb{R} (=location) and \beta \in (0,\infty) (=scale) is called a location-scale family if X belonginging to the family implies that Y=aX+b also belong to the family for any parameter a and b. If f has a density this is equivalent to require that the densities have the form f_{\alpa,\beta}(x) = \frac{1}{\beta}f(\frac{x-\alpha}{\beta}) for some fixed function f(x).

• Normal RV are scale/location family with parameters \mu (=location) and \sigma (=scale)$ and f(x)= \frac{e^{-x^2/2}}{\sqrt{2 \pi}}

• The Cauchy distribution with pdf \frac{1}{\beta \pi} \frac{1}{1 + (\frac{x-\alpha}{\beta})^2} is also a location scale family.

• Some family of distribution are only a scale family. For example the exponential random variables with density f(x) = \frac{1}{\beta} e^{-x/\beta} are a scale family with scaling parameter \beta.

Examples

• Since f(x)=x^2 is convex we have E[X]^2 \le E[X^2].

• Since f(x)=e^{\alpha x} is convex for any \alpha \in \mathbb{R} we have E[e^{\alpha X}] \ge e^{\alpha E[X]}.

Remark The theory of convex functions is very rich and immensely useful!

We will need the following slight generalization of Jensen inequality

Once this is done let us turn to Hölder inequality:

• If p=1 and q=\infty then we have |XY|\le|X| \|Y\|_\infty almost surely and thus \|XY\|_1\le \|X\|_1\|Y\|_\infty.

• The convexity of f in Equation 7.1 implies that for non negative random variables U and V we have E[ U^b V^{1-b}] \le E[U]^b E[V]^{1-b}\,. If 1 < p < q <\infty then we set b=\frac{1}{p} and 1-b=\frac{1}{q} and U=|X|^p and V=|Y|^q. Then E[ |X| |Y| ] = E\left[ (|X|^p)^\frac{1}{p} (|Y|^q)^\frac{1}{q}\right] \le E[|X|^p]^\frac1p E[|Y|^q]^\frac{1}{q}

For Minkowski

• If p=\infty Minkowski inequality is easy to check.

• The convexity of f in Equation 7.1 implies that for non negative random variables U and V we have E[ U^b + V^{b}] \le \left(E[U]^b + E[V]^{b}\right)^{1/b}\,. which implies Minkovski if we take b=\frac{1}{p} and U=|X|^p V=|Y|^q.

\quad \square.

Examples:

• If X has a Pareto distribution with parameter \alpha and x_0 then its the CDF is F(t)= 1- \left(\frac{t}{x_0}\right)^\alpha \quad \text{ for } t \ge x_0 and F(t)=0 for t \le x_0.
  The pdf is f(x) = \frac{\alpha x_0^\alpha}{x^{\alpha+1}} and we have E[|X|^p] = E[X^p] = \int_{x_0}^\infty \alpha x_0^\alpha x^{-\alpha -1 + p} dx = \left\{ \begin{array}{cl} \frac{\alpha}{\alpha-\beta} x_0^{\beta}& p <\alpha \\ +\infty & \beta \ge p \end{array} \right.

• If X has a normal distribution (or an exponential, gamma, etc…} then X \in L^p for all 1\le p <\infty but X \notin L^\infty.

• Other norms exists (Orlicz norms) to capture the tail of random variables.

• Chebyshev inequality suggests measuring deviation from the mean in multiple of the standard deviation \sigma= \sqrt{{\rm Var}[X]}: P(|X-E[X]| \ge k \sigma ) \le \frac{1}{k^2}

• Chebyshev inequality might be extremly pessimistic

• Chebyshev is sharp. Consider the RV X with distributioncP(X=\pm 1) = \frac{1}{2k^2} \quad P(X=0)=1 -\frac{1}{k^2} Then E[X]=0 and {\rm Var}[X]=\frac{1}{k^2} P( |X|\ge k \sigma) = P(|X| \ge 1 )=\frac{1}{k^2}

• Chernov inequality is a very sharp inequality as we will explore later on when studying the law of large numbers. The optimization over t is the key ingredient which ensures sharpness.

• The function M(t)=E[e^{tX}] is called the moment generating function for the RV X and we will meet again.

• Example Suppose X is a standard normal random variable \mu=0 and \sigma^2. Then, completing the square, we have E[e^{tX}]= \frac{1}{\sqrt{2\pi}} \int e^{tx} e^{-x^2/2\sigma^2} dx = \int e^{-(x-\sigma^2t)^2/2} e^{\sigma^2t^2/2} = e^{\sigma^2t^2/2} and Chernov bound gives for a \ge 0 that P(X \ge a) \le \sup_{t\ge 0} e^{\sigma^2t^2/2 -ta} = e^{- \inf_{t\ge 0} (ta - \sigma^2t^2/2)} = e^{-a^2/2\sigma^2} which turns out to be sharp up to a prefactor (see exercises).

We consider from now on only two random variables X and Y but all generalizes easily to arbitrary collections. Our next theorem makes the definition a bit more easy to check.

• To see that Item 2. \implies item 1. we use the monotone class theorem Theorem 3.1. Fix B \in \mathcal{D} then the collection \left\{ A \in \mathcal{E}\,:\, P(X \in A, Y \in B)=P(X\in A) P(Y \in B)\right\} contains the p-system \mathcal{C} and is a d-system (contains \Omega, closed under complement, closed under increasing limits, check this please). Therefore by the monotone class theorem it contains \mathcal{E}. Analgously fix now A \in \mathcal{E}, then the set
  \left\{ B \in \mathcal{F}\,:\, P(X \in A, Y \in B)=P(X\in A) P(Y \in B)\right\} contains \mathcal{F}.

• To see that item 3. \implies item 1. first we take f(x)=x and g(y)=y. Conversely we note that V=f(X) is measurable with respect to \sigma(X): since V^{-1}(B) = X^{-1} (f^{-1}(B)) \in \sigma(X) this shows that \sigma(f(X))\subset \sigma(X). Likewise \sigma(g(Y)) \subset \sigma(Y). Since \sigma(X) and \sigma(Y) are independent so are \sigma(f(X)) and \sigma(g(Y)).

• To see that item 4. \implies item 1. take f=1_A and g=1_B. To show that item 1. \implies item 4. note that item 1. can be rewritten that E[1_A(X) 1_B(Y)] =E[1_A(X)] E[1_B(Y)]. By linearity of the expectation then item 4. holds for all simple functions g and g. If f and g are non negative then we choose sequences of simple functions such that f_n \nearrow f anf g_n \nearrow g. We have then f_n g_n \nearrow fg and using the monotone convergence theorem twice we have \begin{aligned} E[f(X)g(Y)] & = E[ \lim_{n} f_n(X) g_n(Y)] = \lim_{n} E[ f_n(X) g_n(Y)] = \lim_{n} E[ f_n(X) ] E[g_n(Y)] \\ &= \lim_{n} E[ f_n(X) ] \lim_{n} E[g_n(Y)] =E[ f(X) ] E[g(Y)] \end{aligned}

If f and g are bounded and measurable then we write f=f_+-f_- and g=g_=-g_-. Then f_\pm and g_\pm are bounded and measurable and thus the product of f_\pm(X) and g_\pm(Y) are also integrable. We have \begin{aligned} E[f(X)g(Y)] & = E[(f_+(X)-f_-(X))(g_+(Y)-g_-(Y))] \\ &= E[ f_+(X)g_+(Y)]+ E[f_-(X)g_-(Y)] - E[f_+(X)g_-(Y)]- E[f_-(X)(g_+(Y)] \\ &= E[ f_+(X)]E[g_+(Y)]+ E[f_-(X)]E[g_-(Y)] - E[f_+(X)]E[g_-(Y)]- E[f_-(X])E[g_+(Y)] \\ &= E[ f_+(X)-f_-(X)] E[ g_+(Y)-g_-(Y)] \end{aligned}

• Clearly item 1. \implies item 4. \implies 5.. For the converse we show that item 5. \implies item 2. Given an interval (a,b) consider an increasing sequence of piecewise linear function continuous function f_n \nearrow 1_{(a,b)}. f_n(t) = \left\{ \begin{array}{cl} 0 & t \le a + \frac{1}{n} \text{ or } t \ge b-\frac{1}{n} \\ 1 & a+\frac{1}{n} \le t \le b-\frac{1}{n}\\ \text{linear} & \text{otherwise } \end{array} \right. Let us consider the p-system which contains all intervals of the form (a,b) and which generate the Borel \sigma-algebra \mathcal{B}. By using a monotone convergence argument like for item 1. \implies item 4. we see that for f_n \nearrow 1_{(a,b)} and g_n \nearrow 1_{(c,d)} E[f_n(X) g_n(Y)]= E[f_n(X)] E[g_n(Y)] \implies P(X \in (a,b)) P(Y \in (c,d)) and so item 2. holds.
  For separable metric space, the so-called Urysohn lemma can be used to prove the same results. \quad \square

Applying MCT again to the function g_n(x) = \sum_{k=1}^n Q(C_n(x)) we find that \sum_{n=1}^\infty R(C_n) = \sum_{n=1}^\infty \int_E Q(C_n(x)) dP(x) = \int_E \sum_{n=1}^\infty Q(C_n(x)) dP(x) = \int_E Q(C(x)) dP(x) =R(C). and this shows that R is a probability measure. Uniqueness of R follows from the monotone class theorem.

For item 2. note that in item 1, we have proved it in the case where f(x,y)= 1_C(x,y). By linearity the result then holds for simple functions. If f is nonnegative and measurable then pick an increasing sequence such that f_n \nearrow f. Then by MCT \int f(x,y) d P\otimes Q(x,y) = \lim_{n} \int f_n(x,y) d P\otimes Q(x,y) = \lim_{n} \int_E (\int_F f_n(x,y) d Q(y)) dP(x) But the function x \to \int_F f_n(x,y) d Q(y) is increasing in n and by MCT again, and again. \begin{aligned} \int f(x,y) d P\otimes Q(x,y) & = \int_E \lim_{n} (\int_F f_n(x,y) d Q(y)) dP(x) = \int_E (\int_F \lim_{n} f_n(x,y) d Q(y)) dP(x) \\ &= \int_E (\int_F f(x,y) d Q(y)) dP(x) \end{aligned} Simlarly one shows that \int f(x,y) d P\otimes Q(x,y) = \int_F (\int_E f(x,y) d P(x)) dQ(y). The result for integrable f follows by decomposing into postive and negative part. \quad \square

Applying this to random variables we get

Fubini-Tonelli for countably many RV:

We extend this result to countable many independent random variables: this is important in practice where we need such models: for example flipping a coin as many times as needed!

This can be seen as an extension of Fubini theorem and is also a specical case of the so-called Kolmogorov extension theorem which us used to construct general probability measures on infinite product space. No proof is given here.

Infinite product \sigma-algebras
Given \sigma-algebras \mathcal{A}_j on \Omega_j we set \Omega = \prod_{j=1}^\infty \Omega_j and define rectangles for n_1 < n_2 < \cdots < n_k and k finite but arbitrary A_{n_1} \times A_{n_2} \times \cdots \times A_{n_k} = \{ \omega=(\omega_1,\omega_2,\omega_3, \cdots) \in \Omega \;: w_{n_j} \in A_{n_j}\} where A_{n_j} \in \mathcal{A_{n_j}}. The product \sigma-algebra \mathcal{A} = \bigotimes_{j=1}^\infty \mathcal{A}_j the \sigma-algebras generated by all the rectangles.

If we have a RV X_n: \Omega_n \to \mathbb{R} then we define its extension to \Omega by \tilde{X_n}(\omega) = X_n(\omega_n) and the distribution of \tilde{X_n} is the same as the distribution of X_n because \tilde{X_n}^{-1}(B_n) = \Omega_1 \times \cdots \times \Omega_{n-1} \times X_n^{-1}(B_n) \times \Omega_{n+1} \times \cdots and thus P(\tilde{X_n}\in B_n) =P_n (X_n \in B_n)\,. A similar computation shows that \tilde{X}_n and \tilde{X}_m are independent for n \not= m or more generally any finite collection of X_j's are independent.

Examples Given independent random variable X_1, X_2, \cdots we define S_n = X_1 + X_2 +\cdots + X_n.

• The event \{ \omega\,:\, \lim_{n} X_n(\omega) \text{ exists }\} belongs to every \mathcal{C}_n and thus belong to \mathcal{C}_\infty. Therefore X_n either converges a.s or diverges a.s.

• A random variable which is measurable with respect to \mathcal{C}_\infty must be constant almost surely. Therefore \limsup_n X_n \,, \quad \liminf_n X_n\,, \quad \limsup_n \frac{1}{n} S_n\,, \quad \liminf_n \frac{1}{n} S_n are all constant almost surely.

• The event \limsup_{n} \{ X_n \in B\} (also called \{ X_n \in B \text{ infinitely often }\}) is in \mathcal{C}_\infty.

• The event \limsup_{n} \{ S_n \in B\} is not in \mathcal{C}_\infty.

The following theorem is a generalization of Fubini-Tonelli

• This theorem is intimately related to the concepts of conditional probability and conditional expectations which we will study later.

• Roughly speaking, on nice probability space (e.g. separable metric spaces), every probaility measure on the product space E \times F can be constructed in the way described in Theorem 9.1 (this is a deep result).

• If R=P \otimes Q is a product measure then the marginal of R are P and Q. This is for the kernel K(x,A)=Q(A).

• If R(dx,dy)= P(dx) K(x,dy) then we have R(A \times F) = \int_A K(x,F) dP(x) = P(A) \quad \quad R(E \times B) = \int_E K(x,B) dP(X) so its marginals are P and and Q given by Q(B) = \int_E K(x,B) dP(x).

By doing a Fubini-Tonelli theorem type argument one can construct the Lebesgue measure on \mathbb{R}^n.

Notations we often use the notation dx or dx_1 \cdots dx_n for integration with respect to m_n.

Remark It does not matter how K(x,B) is defined for such x where f_X(x)=0 and so we have left it undefined. There are in general many kernels densities which will give the same probability aloowing for changes on sets of zero probbaility.

3. We have \int k(x,y) dy = \int \frac{f(x,y)}{f_X(x)} dy = \frac{f_X(x)}{f_X(x)} =1 and thus k(x,y) is a density. Furthermore we have \begin{aligned} P( X \in A, Y \in B) &= \int_A K(x,B) dP(x) = \int_A f_X(x) \left(\int_B k(x,y) dy \right) dx = \int_A f_X(x) \left(\int_B \frac{f(x,y)}{f_X(x)} dy \right) dx \\ & = \int_A \int_B f(x,y) dx dy \end{aligned} and this concludes the proof since the measure is uniquely determined by its value on rectangles (by a monotone class theorem arguemnt).

We have then for any nonnegative h \begin{aligned} E[h(Z,U)]&=E\left[h\left((X_1+X_2,\frac{X_1}{X_1+X_2}\right)\right]\\ &= \int_0^\infty \int_0^\infty h\left(x_1+x_2,\frac{x_1}{x_1+x_2}\right) \frac{\beta^{\alpha_1+\alpha_2}}{\Gamma(\alpha_1) \Gamma(\alpha_2)} x_1^{\alpha_1-1} x_2^{\alpha_2 -1} e^{- \beta(x_1 + x_2)} dx_1 dx_2 \\ & = \int_0^1 \int_0^\infty h(z,u) \frac{\beta^{\alpha_1+\alpha_2}}{\Gamma(\alpha_1) \Gamma(\alpha_2)} (uz)^{\alpha_1-1} ((1-u)z)^{\alpha_2-1} e^{-\beta z} z du dz \\ &= \int_0^1 h(z,u) \frac{\Gamma(\alpha_1+\alpha_2)}{\Gamma(\alpha_1) \Gamma(\alpha_2)} u^{\alpha_1-1} (1-u)^{\alpha_2-1} du \int_0^\infty \frac{\beta^{\alpha_1+\alpha_2}}{\Gamma(\alpha_1+ \alpha_2)} z^{\alpha_1 + \alpha_2 -1} e^{-\beta z} dz \end{aligned} and this proves all three statements at once.

Remark This is a nice, indirect way, to compute the normalization for the density of the \beta distribution which is proportional to u^{\alpha_1-1}(1-u)^{\alpha_2-1}.

There is a natural connection between a binomial random variable (discrete) and the beta random variable (continuous) (let us call it P for a change). The pdf looks strangely similar {n \choose j} p^j (1-p)^{n-j} \quad \text{ versus } \frac{\Gamma(\alpha_1+\alpha_2)}{\Gamma(\alpha_1) \Gamma(\alpha_2)} p^{\alpha_1 -1} (1-p)^{\alpha_2 -1} But p is a parameter for the binomial while it is a variable for the second!

Model:

• Make n indepdent trials, each with a (random) probability P.

• Take P to have a beta distribution with suitably chosen parameter \alpha_1,\alpha_2.

• The mean \frac{\alpha_1}{\alpha_1+\alpha_2} is your average guess for the “true” probability p and by adjusting the scale you can adjust the variance (uncertainty) associated with your guess.

This leads to considering a random variable (X,P) taking value in \{0,1,\cdots,n\} \times [0,1] with a “density” f(j,p) = \underbrace{{n \choose j} p^j (1-p)^{n-j}}_{=k(p,j) \text{ kernel }} \underbrace{\frac{\Gamma(\alpha_1+\alpha_2)}{\Gamma(\alpha_1) \Gamma(\alpha_2)} p^{\alpha_1-1} (1-p)^{\alpha_2-1} }_{=f(p)} which is normalized \sum_{j=0}^n \int_0^1 f(k,p) dp =1

The beta-binomial distribution with paramters (n,\alpha_1,\alpha_2) is the marginal distribution of X on \{0,1,\cdots,n\} given by \begin{aligned} f(j) = \int_0^1 f(j,p) dp & = {n \choose j} \frac{\Gamma(\alpha_1+\alpha_2)}{\Gamma(\alpha_1) \Gamma(\alpha_2)} \int_0^1 p^{\alpha_1+n -1}(1-p)^{\alpha_2+n-k-1} \\ & = {n \choose j} \frac{\Gamma(\alpha_1+\alpha_2)}{\Gamma(\alpha_1) \Gamma(\alpha_2)} \frac{\Gamma(\alpha_1+j) \Gamma(\alpha_2+n-j)}{\Gamma(\alpha_1+\alpha_2+n)} \end{aligned}

Bayesian statisitics framework

• We interpret the distribution f(p) with parameter \alpha_1 and \alpha_2 as the prior distribution which describe our beliefs before we do any experiment. For example \alpha_1=\alpha_2=1 correspond to a uniform distribution on p (that is we are totally agnostic, a fine choice if you know nothing).

• The beta-binomial which is the marginal f(j)=\int_0^1 f(j,p) dp describe the distribution of the independent trials under this model. It is called the evidence.

• The kernel k(p,j) is called the likelihood which describes the number of success, j, given a certain probability of success, p. It is called the likelihood when we view it as a function of p and think of j as a parameter.

• Now we can write the distribution using kernels in two ways: f(j,p)= k(p,j)f(p) = k(j,p) f(j) and the kernel k(j,p) is called the posterior distribution. It is interpreted as the distribution of p given that j trials have occured.

• We can rewrite this (this is just a version of Bayes theorem) as \text{posterior} = k(j,p) = \frac{k(p,j)f(p)}{f(j)} = \frac{\text{likelihood}\times\text{prior}}{\text{evidence}}\,.

• For the particular model at hand k(j,p) \propto p^{j} (1-p)^{n-j} p^{\alpha_1-1} (1-p)^{\alpha_2-1} \propto p^{\alpha_1+j-1} (1-p)^{\alpha_2+ n- j-1} and therefore k(j,p) has a binomial distribution with parameter \alpha_1 +j and \alpha_2+n-j.

• This is special: the prior and posterior distribution belong to the same family. We say that we have conjugate priors and this is a simple model to play. with. In general we need Monte-Carlo Markov chains to do the job.

• Example: Amazon seller ratings You want to buy a book online

Remarks

• We have not talked explicitly about integration of complex valued function h=f+ig where f and g are the real and imaginary part. It is simply defined as \int (f+ig)dP = \int f dP + i \int g dP provided f and g are integrable. A complex function h is integrable iff and only if |h| is intergable if and only if f and g are integrable. (The only thing a bit hard to prove is the triangle inequality |\int h dP|\le \int|h| dP.)

• The function e^{i\langle t,x \rangle} = \cos(\langle t,x \rangle) + i \sin (\langle t,x \rangle) is integrable since \sin(\langle t,x \rangle) and \cos(\langle t,x \rangle) are bounded function (thus in L^1 \subset L^\infty) or by noting that |e^{i\langle t,x \rangle}|=1.

• Suppose the measure P has a density f(x) then we have \widehat{P}(t)= \int e^{i\langle t,x \rangle} f(x) dx which is simply the Fourier transform (usually denoted by \widehat{f}(t)) of the function f(x). (Diverse conventions are used for the Fourier, e.g. using e^{-i 2\pi\langle k,x \rangle} instead e^{i\langle t,x \rangle})
  

As we have seen in Chapter 7 the L^p spaces are form a dcereasing sequence L^1 \supset L^2 \supset L^3 \supset \cdots L^\infty and the next theorem show that if some random variable belongs to L^n (for some integer n) then its chararcteristic function will be n-times continuously differentiable.

First we note that by symmetry
\phi_X(t)= \frac{1}{\sqrt{2\pi}}\int \cos(tx) e^{-x^2/2} dx By Theorem 10.2 we can differentiate under the integral and find after integrating by part \phi_X'(t)=\frac{1}{\sqrt{2\pi}}\int -x \sin(tx)e^{-x^2/2} dx = \frac{1}{\sqrt{2\pi}}\int -t \cos(tx)e^{-x^2/2} dx =-t \phi_X(t) a separable ODE with initial condition \phi_X(0)=1. The solution is easily found to be e^{-t^2/2} and thus we have \phi_X(t)=E\left[e^{itX}\right]= e^{-t^2/2}. Finally noting that Y=\sigma X +\mu is a normal is with mean \mu and \sigma we find by Theorem 10.3 that \phi_Y(t)=e^{i\mu t}E\left[e^{i\sigma t X}\right]= e^{i\mu t -\sigma^2t^2/2}.

5. Exponential with parameter \beta: For any (complex) z we have \int_a^b e^{z x} dx = \frac{e^{z b} - e^{za}}{z}. From this we deduce that \phi_X(t) = \beta \int_0^\infty e^{(it-\beta)x} dx = \frac{\beta}{\beta-it}

The integrand in Equation 10.2 is bounded and converges as T \to \infty to the function \psi_{a,b}(x)= \left\{ \begin{array}{cl} 0 & x < a \\ \frac{1}{2} & x=a \\ 1 & a < x < b \\ \frac{1}{2} & x=b \\ 0 & x >b \\ \end{array} \right. By DCT we have that I_T \to \int \psi_{a,b} dP = P((a,b]) if a and b are not atoms. \quad \square

You can use the Fourier inversion formula to extract more information.

Another tool is the following convolution theorem

For the second part if X and Y have a density we have \begin{aligned} P(Z \in A) =E[1_A(Z)] & = \int \int 1_A(x+y) f_X(x) f_Y(y) dx dy \\ & = \int \int 1_A(z) f_X(z-y) f_Y(y) dz dy \quad \text{ change of variables } z=x+y, dz = dx \\ &= \int \left(\int f_X(z-y) f_Y(y) dy\right) 1_A(z) dz \quad \text{ Fubini } \end{aligned} and since this holds for all A, Z has the claimed density. The second formula is proved in the same way. \quad \square.

Example: triangular distribution
Suppose X and Y are independent and uniformly distributed on [-\frac{1}{2},\frac12]. Then Z=X+Y is between -1 and +1 for z \in [-1,1] we have f_Z(z)= \int_{-\infty}^\infty f_X(z-y) f_Y(y) dy = \left\{ \begin{array}{cl} \int_{-\frac12}^{z+ \frac12} dy & -1\le z \le 0 \\ \int_{z-\frac{1}{2}}^{\frac12} dy & 0 \le z \le 1 \end{array} = 1- |z| \right.

A stronger condition on the moments do imply uniqueness: if all moments exists and E[X^n] do not grow to fast with n then the moments do determine the distribution. This use a analytic continuation argument and relies on the uniqueness theorem for the Fourier transform.

• The next piece is the Taylor expansion theorem with reminder for function which are n-times continuously differentiable f(x)= \sum_{k=0}^n f^{(k)}(x_0) \frac{(x-x_0)^k}{k!} + \int_{x_0}^x \frac{f^{(n+1)}(t)}{n!}(x-s)^n dt from which we obtain
  \left|e^{itx}\left( e^{ihx} - \sum_{k=0}^n \frac{(ix)^k}{k!}\right)\right| \le \frac{|h x|^{n+1}}{(n+1)!}

• Integrating with respect to P and taking n \to \infty together with Theorem 10.2 gives \phi_X(t+h)= \sum_{k=0}^\infty \phi_X^{(k)}(t) \tag{10.3} for |h| < t_0.

• Now suppose X and Y have the same moment generating function in a neighborhood of 0. Then all their moments coincide and thus by Equation 10.3 (with t=0), \phi_X(t)=\phi_Y(t) on the interval (-r_0, r_0). By Theorem 10.2 their derivatives must also be equal on (-t_0,t_0). Using now Equation 10.3 (with t=-t_0+\epsilon and t=t_0-\epsilon shows that \phi_X(t)=\phi_Y(t) on the interval (-2t_0, 2t_0). Repeating this argument \phi_X(t)=\phi_Y(t) for all t and thus by Theorem 10.5 X and Y must have the same distribution. \quad \square

Returning to random variables we find

From the Borel-Cantelli Lemma we obtain useful criteria for almost sure convergence.

The relation between almost sure convergence and convergence in probability is contained in the following theorem.

The third part, while looking somewhat convoluted is very useful to streamline subsequent proofs. It relies on the following simple fact: suppose that the sequence x_n is such that every subsequence has a subsubsequence which converges to x then x_n converges to x.

3. Assume that every subsequence of X_n has a sub-subsequence which converges to X. Fix \epsilon>0 and consider the numerical sequence p_n(\epsilon)=P(|X_n-X| \ge \epsilon). Since this sequence is bounded, by Bolzano-Weierstrass theorem, let p_{n_k} be a convergent subsequence with \lim_{k} p_{n_k} =p. By assumption X_{n_k} has a convergent subsequence X_{n_{k_j}} which converges to X almost surely. This implies, by part 1., that p_{n_{k_j}} converges to 0. This means that for the sequence p_n, every convergent subsequence has a subsubsequence which converges to 0. This implies that p_n converges to 0 and thus X_n converges to X in probability. \quad \square.

Based on this we obtain the following continuity theorem

Using a similar argument we show that convergence in probability is preserved under arithmetic operations.

We finish this section by showing that we can use weak convergence to turn the space of RV into a complete metric space. We will use the following metric d(X,Y) = E[ \min\{ |X-Y|, 1\} ] The choice is not unique, often one will find instead d(X,Y)=E[ \frac{|X-Y|}{1 + |X-Y|}].

We show now that X_n converges to Y in probability. Since |X_n-Y| \le |X_n - X_{N_k}| + |Y_k -Y| we have i_\epsilon(|X_n-Y|) \le i_{\epsilon/2}(|X_n-X_{N_k}|) + i_{\epsilon/2}(|Y_k-Y|) \,. Taking expectations gives P(|X_n-Y| > \epsilon) \le P(|X_n-X_{N_k}| > \epsilon/2) + P(|Y_k-Y|> \epsilon/2). The first goes to 0 as n goes to \infty since the sequence X_n is Cauchy and the second term goes to 0 since we have almost sure convergence. Therefore X_n converges to Y in probability. \quad \square.

• If X_n converges in L^p then X_n converges in probability as well. We have P(|X-X_n| \ge \epsilon) \le E[|X_n-X|^p]/{\epsilon^p} by Markov inequality. In particular, by Theorem 11.3 if X_n converges to X in L^p then there exists a subsequence X_{n_k} which converges almost surely to X.

• Conversely convergence in probability does not imply convergence in L^1. Modify the sequence in Equation 11.2 to make it Y_1=X_1, Y_2=2X_2, Y_3=2X_3, Y_4=3X_4, \cdots. This sequence converges in probability to 0 as well! This ensures that E[Y_n]=1 so Y_n does not converge to 0 in L^1. Note also that for any m there are infitely many m \ge n such that E[|X_n-X_m|=2 so the sequence cannot converge.

We prove now a converse which looks a bit like dominated convergence theorem.

Example: Cauchy Consider X_1, X_2, \cdots, X_n independent Cauchy RV with parameter \beta. Using the characteristic function (recall the chararcteristic function of a Cauchy RV is e^{-\beta|t|}) we find that E\left[e^{it\frac{S_n}{n}}\right]=E\left[e^{\frac{it}{n}X_1} \cdots e^{\frac{it}{n}X_1} \right] = E\left[e^{\frac{it}{n}X_1}\right] \cdots E\left[e^{\frac{it}{n}X_1} \right] = \left( e^{-\beta\left|\frac{t}{n}\right|} \right)^n = e^{-\beta|t|} that is {S_n}{n} is a Cauchy RV with same parameter as X_i. No convergence almost sure or in probability seems reasonable here convergence in distribution will be useful here.

We start with a (not optimal) version of the LLN

Given n pick k=k(n) such that k^2 \le n \le (k+1)^2. Since all the terms are positive we have \frac{x_1 + \cdots + x_{k^2}}{k^2} \frac{k^2}{n} \le \frac{x_1 + \cdots + x_n}{n} \le \frac{(k+1)^2}{n} \frac{x_1 + \cdots + x_{(k+1)^2}}{(k+1)^2} Now as n \to \infty, k=k(n) \to \infty and since \lim_{k \to \infty} \frac{(k+1)^2}{k^2} =1 1 \le \frac{n}{k^2} \le \frac{(k+1)^2}{k^2} \implies \lim_{n}\frac{n}{k^2} =1 \,. Simlarly \lim_{n\to \infty } \frac{(k+1)^2}{n}=1 and this shows that \frac{S_n}{n} converges almost surely. \quad \square.

A stronger version exists, only existence of a finite mean is needed. Proof will be provided with aid of Martingales later on.

We prove next that the case \mu=\infty can also be treated.

A strengthening of the law of large number is that the empirical CDF F_n(t) converges to F(t) uniformly in t.

We show next that, for any \omega \in \Omega_0, the convergence is uniform in t. Since F is increasing and bounded, given \epsilon>0 we can find t_0=-\infty < t_1 < \cdots < t_m=+\infty such that F(t_j)-F(t_{j-1}) \le \frac{\epsilon}{2}. Using that F_n and F are increasing we have for t \in [t_{j-1},t_j] \begin{aligned} F_n(t)-F(t) &\le F_n(t_j) - F(t_{j-1}) \le F_n(t_j)- F(t_j) + \frac{\epsilon}{2}\\ F_n(t)-F(t) &\ge F_n(t_{j-1}) - F(t_{j}) \ge F_n(t_{j-1})- F(t_{j-1}) - \frac{\epsilon}{2}\\ \end{aligned} We can now pick N_j=N_j(\omega) such that |F_n(t_j)- F(t_j)|\le \frac{\epsilon}{2} if n \ge N_j and therefore if n\ge N=\max_j N_j we have, for all t \in \mathbb{R}, |F_n(t,\omega)-F(t)| \le \epsilon for all t and all n \ge N(\omega). This that \sup_{t\in \mathbb{R}}|F_n(t)-F(t)| converges almost surely to 0. \quad \square.

Illustration of the Glivenko-Cantelli Theorem (made with Chat GPT)

import numpy as np
import matplotlib.pyplot as plt
from scipy.stats import beta

# Generate random data from a Beta distribution
np.random.seed(42)
true_distribution = beta.rvs(2, 5, size=1000)

# Generate empirical distribution function
def empirical_distribution(data, x):
    return np.sum(data <= x) / len(data)

# Compute empirical distribution function for different sample sizes
sample_sizes = [10, 100, 1000]
x_values = np.linspace(0, 1, 1000)

plt.figure(figsize=(12, 8))

for n in sample_sizes:
    # Generate a random sample of size n
    sample = np.random.choice(true_distribution, size=n, replace=True)
    
    # Calculate empirical distribution function values
    edf_values = [empirical_distribution(sample, x) for x in x_values]
    
    # Plot the empirical distribution function
    plt.plot(x_values, edf_values, label=f'n={n}')

# Plot the true distribution function
true_cdf_values = beta.cdf(x_values, 2, 5)
plt.plot(x_values, true_cdf_values, linestyle='--', color='black', label='True Distribution')

# Plot the difference between ECDF and true CDF
for n in sample_sizes:
    sample = np.random.choice(true_distribution, size=n, replace=True)
    edf_values = [empirical_distribution(sample, x) for x in x_values]
    difference = np.abs(edf_values - true_cdf_values)
    plt.plot(x_values, difference, linestyle='dotted', label=f'n={n} (Difference)')

plt.title('Glivenko-Cantelli Theorem with Beta Distribution')
plt.xlabel('x')
plt.ylabel('Empirical Distribution Function / Difference')
plt.legend()
plt.show()

• Monte-Carlo version III:

  Pick V non-uniform on [0,1] with density f (e.g a beta RV with parameter \alpha,\beta). Then we have \int_0^1 h(x) dx = \int_{0}^1 \frac{h(x)}{f(x)} f(x) dx and so if V has distribution f then \frac{1}{n} \sum_{i=1}^n \frac{h(V_i)}{f(V_i)} converges to E[\frac{h(v)}{f(V)}]=\int_0^1 h(x) dx.

  This is the idea behind importance sampling: you want to sample more points from regions where h is large and which contribute more ot the integral.

• We can generalize this to integral of subsets of \mathbb{R}^n or integral over the whole space.

If we appply the Hoeffding’s bound to a sum of random variables we find

We obtain from this bound a confidence interval for emprical sum

Using

\delta = 2 e^{-\frac{2 n \varepsilon^2}{(b-a)^2}} \iff \epsilon = \sqrt{ \frac{(b-a)^2\ln\left(\frac{2}{\delta}\right)}{2n}} we get the confidence interval P\left( \mu \in \left[ \frac{S_n}{n}- \sqrt{ \frac{(b-a)^2\ln\left(\frac{2}{\delta}\right)}{2n}}, \frac{S_n}{n} +\sqrt{ \frac{(b-a)^2\ln\left(\frac{2}{\delta}\right)}{2 n}} \right] \right) \ge 1 -\delta

To combine this we a Chernov bound we have to solve the following optimzation problem which after some straightforward but lengthy computation gives \sup_{t \ge 0} \left\{ \varepsilon t - \frac{a t^2}{2(1-bt)} \right\} = \frac{a}{b^2}h\left( \frac{b\epsilon}{a}\right) \quad \textrm{ where } h(u) = 1 +u - \sqrt{1 + 2u} Note that we can invert the function h and we have h^{-1}(z)= z + \sqrt{2z}. This make the Bernstein bound especially convenient to get explcit formulas. By symmetry we find the same bound for the left tail.

Comparison: Taking a=0,b=1 (\textrm{Bernstein}) \quad \frac{c}{3n} \ln\left( \frac{2}{\delta}\right) + \sqrt{2 \ln\left( \frac{2}{\delta}\right)} \frac{\sigma}{\sqrt{n}} \quad \textrm{ versus} \quad \sqrt{2\ln\left(\frac{2}{\delta}\right)} \frac{\sigma_{max}}{\sqrt{n}} \quad (\textrm{Hoeffding})

You should note that this bound can be substantially better than Hoeffding’s bound provided \sigma \le \sigma_{max}, if n is large then the 1/n term is much smaller than the 1/\sqrt{n} term and so Bernstein bound becomes better. See the illustration on the next page.

There is an even more sophisticated version of this bound where one uses the sample variance to build a bound. One needs then to estimate the probability that the sample varaince is far from the true variance which itself requires more sophisticated inequalities which is martingales.

As an illustration we plot the empirical mean as well as Hoeffding’s and Bernstein’s confidence interval for computing the mean beta RV so in Hoeffding’s the maximum variance is \frac{1}{4} and we can take c=1 in Bernstein. Here we take the parameter \alpha=1 and \beta=2 so the true mean is \frac{\alpha}{\alpha +\beta}=\frac{1} {3} and the true variance is \frac{\alpha \beta}{(\alpha+\beta)^2(\alpha + \beta +1)} = \frac{1}{18} which is quite a bit smaller than \frac{1}{4}.

confidence intervals with Bernstein and Hoeffding

Examples:

1. If X_i are identically RV (i.e. P^{X_n}=P for all n then X_i converges in distribution but X_n does not converges in any other sense except if X=X_1=X_2=\cdots.
   An example is when X_i are IID Cauchy RV with parameter \beta then \frac{S_n}{n}=\frac{1}{n}(X_1 + \cdots+ X_n) are also Cauchy RV with paramter \beta. Then both X_n and \frac{S_n}{n} both converges in distribution to a Cauchy RV paramter \beta but these sequences do not converges in any other sense.

2. The measure P^n= \frac{1}{n} \sum_{i=1}^n \delta_{\frac{i}{n}} converges weakly to the Lebesgue measure on [0,1]. Indeed for f continuous, the Riemman sum \int f dP_n = \frac{1}{n}\sum_{i=1}^n f\left(\frac{i}{n}\right) \to \int f dx \,.

3. If P_n = \delta_{x_n} then P_n converges weakly to P if and only if P=\delta_x and x_n \to x.

4. Convergence of the quantile functions: Let Q_n be the quantile function for X_n and Q the quantile function for X and let P_0 be Lebesgue measure on [0,1]. Then P^{X_n}=P_0 \circ Q_N^{-1} and P^{X}=P_0 \circ Q^{-1}.
   If the quantiles Q_n converges to Q for P_0 almost all \omega \in [0,1] then for f continuous and bounded f\circ Q_n converges to f \circ Q for P_0 almost all \omega \in [0,1]. By the bounded convergence theorem
   E[f(X_n)]=\int_{\mathbb{R}} f(x) dP^{X_n}(x) = \int_{[0,1]} f( Q_n(\omega))dP_0(\omega) \to \int_{[0,1]} f( Q(\omega))dP^0(\omega) =E[f(X)] and thus X_n converges in distribution to X.

• Take f bounded and continuous so that a < f(x) < b and consider the probability P \circ f^{-1} on (a,b). Since atoms are countable we pick a partition a_0=a< a_ < a_2 < \cdots < a_m=b so that a_i-a_{i-1} < \epsilon and a_i is not an atom for P \circ f^{-1}.
  Set A_i = f^{-1}((a_{i-1},a_i]) and define the simple function g=\sum_{i} a_{i-1} 1_{A_i}\,, \quad\quad h=\sum_{i} a_{i} 1_{A_i} \,. By construction we have f- \epsilon \le g \le f \le h \le f + \epsilon. \tag{13.1} Since f is continuous if x \in \partial A_i (A_i is collection of intervals) then f(x)=a_{i-1} or f(x)=a_i which are not atoms. Therefore P(\partial A_i)=0 and thus P_n(\partial A_i) \to 0 as n \to \infty. This implies that \int g dP_n \to \int g dP and \int h dP_n \to \int h dP and thus by Equation 13.1 we have \begin{aligned} \int f dP - \epsilon \le \int g dP = \lim_n \int g dP_n & \le \liminf_n \int f dP_n \\ &\le \limsup_n \int f dP_n \le \lim_n \int h dP_n =\int h dP \le \int f dP + \epsilon \end{aligned} Since \epsilon is arbitrary we \lim_n \int f dP_n = f dP. \quad \square.