# ---
# 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
# ---

# # Conditional Probability and Conditional Expectation
#
# ## Intro
#
# - given some partial information
# - or just first "condition" on some appropriate $r.v.
# \DeclareMathOperator*{\argmin}{argmin}
# \newcommand{\ffrac}{\displaystyle \frac}
# \newcommand{\Tran}[1]{{#1}^{\mathrm{T}}}
# \newcommand{\d}[1]{\displaystyle{#1}}
# \newcommand{\EE}[2][\,\!]{\mathbb{E}_{#1}\left[#2\right]}
# \newcommand{\dd}{\mathrm{d}}
# \newcommand{\Var}[2][\,\!]{\mathrm{Var}_{#1}\left[#2\right]}
# \newcommand{\Cov}[2][\,\!]{\mathrm{Cov}_{#1}\left(#2\right)}
# \newcommand{\Corr}[2][\,\!]{\mathrm{Corr}_{#1}\left(#2\right)}
# \newcommand{\using}[1]{\stackrel{\mathrm{#1}}{=}}
# \newcommand{\I}[1]{\mathrm{I}\left( #1 \right)}
# \newcommand{\N}[1]{\mathrm{N} \left( #1 \right)}
# \newcommand{\space}{\text{ }}
# \newcommand{\bspace}{\;\;\;\;}
# \newcommand{\QQQ}{\boxed{?\:}}
# \newcommand{\CB}[1]{\left\{ #1 \right\}}
# \newcommand{\SB}[1]{\left[ #1 \right]}
# \newcommand{\P}[1]{\left( #1 \right)}
# \newcommand{\ow}{\text{otherwise}}$
#
# ## The Discrete Case
#
# $\forall$ events $E$ and $F$, the **conditional probability** of $E$ *given* $F$ is defined, as long as $P(F) > 0$, by
#
# $$P(E\mid F) = \ffrac{P(EF)} {P(F)}$$
#
# Hence, if $X$ and $Y$ are discrete $r.v.$, then it's natural to define the **conditional probability mass function** of $X$ *given* that $Y=y$ and $P\CB{Y=y}>0$, by:
#
# $$\begin{align}
# p_{X\mid Y}(X\mid Y) &= P\CB{X=x\mid Y=y} \\[0.5em]
# &= \ffrac{P\CB{X=x\mid Y=y}} {P\CB{Y=y}} \\
# &= \ffrac{p(x,y)} {p_{Y}(y)}
# \end{align}$$
#
# and the conditional pdf of $X$ *given* that $Y=y$ and $P\CB{Y=y}>0$ is
#
# $$\begin{align}
# F_{X\mid Y}(X\mid Y) &= P\CB{X \leq x\mid Y=y} \\[0.5em]
# &= \sum_{a \leq x} p_{X\mid Y}(a\mid Y)
# \end{align}$$
#
# and finally, the conditional expectation of $X$ *given* that $Y=y$ and $P\CB{Y=y}>0$ is defined by
#
# $$\begin{align}
# \EE{X\mid Y=y} &= \sum_{x} x \cdot P\CB{X = x\mid Y=y} \\[0.5em]
# &= \sum_{x} x \cdot p_{X\mid Y}(x\mid Y)
# \end{align}$$
#
# $Remark$
#
# If $X$ is independent of $Y$, then all the aforementioned definitions are identical to what we have learned before.

# **e.g.** 
#
# If $X_1$ and $X_2$ are independent **binomial** $r.v.$ with respective parameters $(n_1,p)$ and $(n_2,p)$. Find the conditional pmf of $X_1$ given that $X_1 + X_2 = m$.
#
# >$\begin{align}
# P\CB{X_1 = k \mid X_1 + X_2 = m} &= \ffrac{P\CB{X_1 = k , X_1 + X_2 = m}} {P\CB{X_1 + X_2 = m}} \\[0.6em]
# &= \ffrac{P\CB{X_1 = k}\cdot P\CB{ X_2 = m-k}} {P\CB{X_1 + X_2 = m}}\\
# &= \ffrac{\d{\binom{n_1} {k} p^k q^{\d{n_1 - k}} \cdot \binom{n_2} {m-k} p^{m-k} q^{\d{n_2 - m + k}}}} {\d{\binom{n_1 + n_2}{m} p^m q^{\d{n_1 + n_2 -m}}}}
# \end{align}$
# >
# >Here $q = 1-p$ and $X_1 + X_2$ is a **binomial** $r.v.$ as well with parameters $(n_1 + n_2 , p)$. Simplify that, we obtain:
# >
# > $$P\CB{X_1 = k \mid X_1 + X_2 = m} = \ffrac{\d{\binom{n_1} {k}\binom{n_2} {m-k}}} {\d{\binom{n_1 + n_2}{m}}}$$
# >
# >$Remark$
# >
# >This is a hypergeometric distribution.
#
# ***
#
# **e.g.**
#
# If $X$ and $Y$ are independent **poisson** $r.v.$ with respective parameters $\lambda_1$ and $\lambda_2$. Find the conditional pmf of $X$ given that $X+Y = n$.
#
# >We follow the same fashion and can easily get that
# >
# >$\begin{align}
# P\CB{X = k \mid X + Y = n} &= \ffrac{e^{-\lambda_1} \; \lambda_1^k} {k!}\cdot\ffrac{e^{-\lambda_2}\; \lambda_2^{n-k}} {(n-k)!} \left[\ffrac{e^{-\lambda_1 - \lambda_2} \left(\lambda_1 + \lambda_2\right)^{n}} {n!}\right]^{-1} \\
# &= \ffrac{n!} {k!(n-k)!}\left(\ffrac{\lambda_1} {\lambda_1 + \lambda_2}\right)^k\left(\ffrac{\lambda_2} {\lambda_1 + \lambda_2}\right)^{n-k}
# \end{align}$
# >
# >Given this, we can say that the conditional distribution of $X$ given that $X+Y=n$ is the binomial distribution with parameters $n$ and $\lambda_1/\left(\lambda_1 + \lambda_2\right)$. Hence, we also have
# >
# >$$\EE{X \mid X+Y = n} = n\ffrac{\lambda_1}{\lambda_1 + \lambda_2}$$
#
# ***

# ## Continuous Case
#
# If $X$ and $Y$ have a joint probability density function $f\P{x,y}$, the the ***conditional pdf*** of $X$, given that $Y=y$, is defined for all values of $y$ such that $f_Y\P{y} < 0$, by
#
# $$f_{X \mid Y} \P{x \mid y} = \ffrac{f\P{x,y}} {f_Y\P{y}}$$
#
# Then the expectation: $\EE{X \mid Y = y} = \d{\int_{-\infty}^{\infty}} x \cdot f_{X \mid Y} \P{x \mid y} \;\dd{x}$
#
# **e.g.**
#
# Joint density of $X$ and $Y$: $f\P{x,y} = \begin{cases}
# 6xy(2-x-y), & 0 < x < 1, 0 < y < 1\\
# 0, & \text{otherwise}
# \end{cases}$
#
# Compute the conditional expectation of $X$ given that $Y=y$, where $0 <y <1$.
#
# >We first need to compute the conditional density:
# >
# >$f_{X \mid Y} \P{x\mid y} = \ffrac{f\P{x,y}} {f_Y\P{y}} = \ffrac{6xy(2-x-y)} {\d{\int_{0}^{1} 6xy(2-x-y) \;\dd{x}}} = \ffrac{6x(2-x-y)} {4-3y}$
# >
# >Hence we can find the expectation
# >
# >$\EE{X \mid Y=y} = \d{\int_{0}^{1}} x \cdot \ffrac{6x(2-x-y)} {4-3y} \;\dd{x} = \ffrac{5-4y} {8-6y}$
#
# ***
#
# **e.g.** The ***t-Distribution***
#
# If $Z$ and $Y$ are independent, with $Z$ having a **standard normal** distribution and $Y$ having a **chi-squared** distribution with $n$ degrees of freedom, then the random variable $T$ defined by
#
# $$T = \ffrac{Z} {\sqrt{Y/n}} = \sqrt{n} \ffrac{Z} {\sqrt{Y}}$$
#
# is said to be a $\texttt{t-}r.v.$ with $n$ degrees of freedom. We now compute its density function:
#
# >Here the strategy is to use one conditional density function and multiply that with the one just on condition, then integrate them.
# >
# >$$f_T(t) = \int_{0}^{\infty} f_{T,Y}\P{t,y} \;\dd{y} = \int_{0}^{\infty} f_{T\mid Y}\P{t \mid y} \cdot f_{Y}(y) \;\dd{y}$$
# >
# >Since we have already get the pdf for **chi-squared** $r.v.$,so $f_Y(y) = \ffrac{e^{-y/2} y^{n/2-1}} {2^{n/2} \Gamma\P{n/2}}$, for $y > 0$. Then $T$ conditioned on $Y$, which is a **normal distribution** with mean $0$ and variance $\P{\sqrt{\ffrac{n} {y}}}^2 = \ffrac{n} {y}$, so
# >
# >$f_{T \mid Y} \P{t \mid y} = \ffrac{1} {\sqrt{2\pi n /y}} \exp\CB{-\ffrac{t^2 y} {2n}} = \ffrac{y^{1/2}} {\sqrt{2 \pi n}} \exp\CB{-\ffrac{t^2 y} {2n}}$ for $-\infty < t < \infty $. Then:
# >
# >$$\begin{align}
# f_{T}(t) &= \int_{0}^{\infty} \ffrac{y^{1/2}} {\sqrt{2 \pi n}} \exp\CB{-\ffrac{t^2 y} {2n}} \cdot \ffrac{e^{-y/2} y^{n/2-1}} {2^{n/2} \Gamma\P{n/2}} \;\dd{y} \\[0.6em]
# &= \ffrac{1} {\sqrt{\pi n} \; 2^{\P{n+1}/2} \; \Gamma\P{n/2}} \int_{0}^{\infty} \exp\CB{-\ffrac{1} {2} \P{1 + \ffrac{t^2} {n}}y} \cdot y^{\P{n-1}/2} \; \dd{y} \\[0.8em]
# & \;\;\;\;\text{then we let } \ffrac{1} {2} \P{1 + \ffrac{t^2} {n}}y = x \\[0.8em]
# &= \ffrac{\P{1 + \frac{t^2} {n}}^{-\P{n+1}/2} \P{1/2}^{-\P{n+1}/2}} {\sqrt{\pi n} \; 2^{\P{n+1}/2} \; \Gamma\P{n/2}} \int_{0}^{\infty} e^{-x} x^{\P{n-1}/2} \;\dd{x} \\[0.6em]
# &= \ffrac{\P{1 + \frac{t^2} {n}}^{-\P{n+1}/2}} {\sqrt{\pi n} \; \Gamma\P{n/2}} \Gamma\P{\ffrac{n-1} {2} + 1} = \ffrac{\Gamma\P{\frac{n+1} {2}}} {\sqrt{\pi n} \; \Gamma\P{\frac{n} {2}}} \P{1 + \ffrac{t^2} {n}}^{-\P{n+1}/2}
# \end{align}$$
#
# $Remark$
#
# It will be much easier if given the joint distribution of $T$ and $Y$. $\texttt{FXXX}$
#
# ***
#
# **e.g.**
#
# Joint density of $X$ and $Y$: $f\P{x,y} = \begin{cases}
# \ffrac{1} {2} y e^{-xy}, & 0 < x < \infty, 0 < y < 2 \\[0.7em]
# 0, &\ow
# \end{cases}$. So what is $\EE{e^{X/2} \mid Y=1}$?
#
# > This time will be much easier, we first obtain the conditional density of $X$ given that $Y=1$:
# >
# >$$\begin{align}
# f_{X\mid Y} \P{x \mid 1} &= \ffrac{f\P{x,1}} {f_Y\P{1}} \\
# &= \ffrac{\ffrac{1} {2} e^{-x}} {\d{\int_{0}^{\infty}\frac{1} {2} e^{-x} \; \dd{x}}} = e^{-x}
# \end{align}$$
# >
# >Hence, we have $\EE{e^{X/2} \mid Y=1} = \d{\int_{0}^{\infty}} e^{x/2} \cdot f_{X\mid Y} \P{x \mid 1} \; \dd{x} =  2$
#
# ***

# **(V)e.g.**
#
# Let $X_1$ and $X_2$ be independent **exponential** $r.v.$ with rates $\mu_1$ and $\mu_2$. Find the conditional density of $X_1$ given that $X_1 + X_2 = t$.
#
# >We'll be using the formula: $f_{\d{X_1 \mid X_1 + X_2}}\P{x \mid t} = \ffrac{f_{\d{X_1, X_1 + X_2}}\P{x, t}} {f_{\d{ X_1 + X_2}}\P{t}}$. The denominator is a *constant at this time*, not given. And as for the numerator, using Jacobian determinant we can find that
# >
# >$$J = \begin{vmatrix}
# \ffrac{\partial x} {\partial x} & \ffrac{\partial x} {\partial y}\\ 
# \ffrac{\partial x+y} {\partial x} & \ffrac{\partial x+y} {\partial y}
# \end{vmatrix} = 1$$
# >
# >So our conclusion is: $f_{\d{X_1, X_1 + X_2}}\P{x, t} = f_{\d{X_1, X_2}}\P{x_1,x_2} \cdot J^{-1} = f_{\d{X_1, X_2}}\P{x,t-x}$. Plug in, we have
# >
# >$$\begin{align}
# f_{\d{X_1 \mid X_1 + X_2}}\P{x \mid t} &= \ffrac{f_{\d{X_1, X_2}}\P{x,t-x}} {f_{\d{X_1 + X_2}}\P{t}} \\
# &= \ffrac{1} {f_{\d{X_1 + X_2}}\P{t}} \cdot \P{\:\mu_1 e^{\d{-\mu_1 x}}}\P{\mu_2 e^{\d{-\mu_2 \P{t-x}}}}, \;\;\;\; 0 \leq x \leq t \\[0.7em]
# &= C \cdot \exp\CB{-\P{\mu_1 - \mu_2}t}, \;\;\;\; 0 \leq x \leq t 
# \end{align}$$
# >
# >Here $C = \ffrac{\mu_1 \mu_2 e^{\d{-\mu_2t}}} {f_{\d{X_1 + X_2}}\P{t}} $. The easier situation is when $\mu_1 = \mu_2 = \mu$, then $f_{\d{X_1 \mid X_1 + X_2}}\P{x \mid t} = C, 0 \leq x \leq t$, which is a uniform distribution, yielding that $C = 1/t$.
# >
# >And when they're not equal, we need to use:
# >
# >$$1 = \int_{0}^{t} f_{\d{X_1 \mid X_1 + X_2}}\P{x \mid t} \;\dd{x} = \ffrac{C} {\mu_1 - \mu_2} \P{1 - \exp\CB{-\P{\mu_1 - \mu_2}t}}\\[1.6em]
# \Longrightarrow C = \ffrac{\mu_1 - \mu_2} {1 - \exp\CB{-\P{\mu_1 - \mu_2}t}}$$
#
# >Now we can see the final answer and the byproduct:
# >
# >$f_{\d{X_1 \mid X_1 + X_2}}\P{x \mid t} = \begin{cases}
# 1/t, & \text{if }\mu_1 = \mu_2 = \mu\\[0.6em]
# \ffrac{\P{\mu_1 - \mu_2}\exp\CB{-\P{\mu_1 - \mu_2}t}} {1 - \exp\CB{-\P{\mu_1 - \mu_2}t}}, &\text{if } \mu_1 \neq \mu_2
# \end{cases}$
# >
# >$
# f_{\d{X_1 + X_2}}\P{t} = \begin{cases}
# \mu^2 t e^{-\mu t}, & \text{if }\mu_1 = \mu_2 = \mu\\[0.6em]
# \ffrac{\mu_1\mu_2\P{\exp\CB{-\mu_2t} - \exp\CB{-\mu_1t}}} {\mu_1 - \mu_2}, &\text{if } \mu_1 \neq \mu_2
# \end{cases}$
#
# $Remark$
#
# >When calculate $f_{\d{ X_1 + X_2}}\P{t}$, $t$ is no longer a given constant.
#
# ***

# ## Computing Expectation by Conditioning
#
# Denote $\EE{X \mid Y}$ as the *function* of the $r.v.$ $Y$ whose value at $Y = y$ is $\EE{X \mid Y = y}$. An extremely important property of conditional expectation is that for all $r.v.$ $X$ and $Y$, 
#
# $$\EE{X} = \EE{\EE{X \mid Y}} = \begin{cases}
# \d{\sum_y} \EE{X \mid Y = y} \cdot P\CB{Y = y}, & \text{if } Y \text{ discrete}\\[0.5em]
# \d{\int_{-\infty}^{\infty}} \EE{X \mid Y = y} \cdot f_Y\P{y}\;\dd{y}, & \text{if } Y \text{ continuous}
# \end{cases}$$
#
# We can interpret this as that when we calculate $\EE{X}$ we may take a *weighted average* of the conditional expected value of $X$ given $Y = y$, each of the terms $\EE{X \mid Y = y}$ being weighted by the probability of the event on which it is conditioned.
#
# **e.g.** The Expectation of the Sum of a Random Number of Random Variables
#
# The expected number of unqualified cookie products per week at an industrial plant is $n$, and the number of broken cookies in each product are independent $r.v.$ with a common mean $m$. Also assume that the number of broken cookies in each product is independent of the number of unqualified products. Then, what's the expected number of broken cookies during a week?
#
# >Letting $N$ denote the number of unqualified cookie products and $X_i$ the number of broken cookies inside the $i\texttt{-th}$ product. Then the total broken cookies is $\sum X_i$. Now to bring the sum operation out of the expecation (even linear operation, however $N$ is a $r.v.$), we need to condition that on $N$
# >
# >$\bspace \d{\EE{\sum\nolimits_{i=1}^{N} X_i} = \EE{\EE{\sum\nolimits_{i=1}^{N} X_i \mid N}}}$
# >
# >But by the independence of $X_i$ and $N$ , we can derive that:
# >
# >$\bspace \d{\EE{\sum_{i=1}^{N}X_i \mid N =n} = \EE{\sum_{i=1}^{n} X_i} = n\cdot\EE{X}}$,
# >
# >which yields the function for $N$: $\d{\EE{\sum\nolimits_{i=1}^{N}X_i\mid N} = N \cdot \EE{X}}$ and thus:
# >
# >$\bspace \d{\EE{\sum_{i=1}^{N}X_i} = \EE{N\cdot \EE{X}} = \EE{N} \cdot \EE{X} = mn}$
#
# $Remark$
#
# >***Compound Random Variable***, as those the sum of a random number (like the preceding $N$) of $i.i.d.$ $r.v.$ (like the preceding $X_i$) that are also independent of $N$.

# **e.g.** The Mean of a Geometric Distribution
#
# Before, we use derivatives or 错位相减 to obtain that $\EE{X} = \d{\sum_{n=1}^{\infty} n \cdot p(1-p)^{n-1}} = \ffrac{1} {p}$. Now a new method can be applied here:
#
# >Let $N$ be the number of trials required and define $Y$ as
# >
# >$Y = \bspace \begin{cases}
# 1, &\text{if the first trial is a success} \\[0.6em]
# 0, &\text{if the first trial is a failure} \\
# \end{cases}$
# >
# >Then $\EE{N} = \EE{\EE{N\mid Y}} = \EE{N\mid Y = 1}\cdot P\CB{Y = 1} + \EE{N \mid Y = 0}\cdot P\CB{Y=0}$. However, $\EE{N \mid Y = 1} = 1$ (no more trials needed) and $\EE{N \mid Y = 0} = 1 + \EE{N}$. Substitute these back we have the equation:
# >
# >$\bspace \EE{N} = 1\cdot p + \P{1 + \EE{N}}\cdot \P{1-p} \space \Longrightarrow \space \EE{N} = 1/p$

# **e.g.** Multinomial Covariances
#
# Consider $n$ independent trials, each of which results in one of the outcomes $1, 2, \dots, r$, with respective probabilities $p_1, p_2, \dots, p_r$, and $\sum p_i = 1$. If we let $N_i$ denote the number of trials that result in outcome $i$, then $\P{N_1, N_2, \dots, N_r}$ is said to have a ***multinomial distribution***. For $i \neq j$, let us compute $\Cov{N_i, N_j} = \EE{N_i N_j} - \EE{N_i} \EE{N_j}$
#
# > Each trial independently results in outcome $i$ with probability $p_i$, and it follows that $N_i$ is binomial with parameters $\P{n, p_i}$, given that $\EE{N_i}\EE{N_j} = n^2 p_i p_j$. Then to compute $\EE{N_i N_j}$, condition on $N_i$ we can obtain:
# >
# >$\bspace \begin{align}
# \EE{N_i N_j}&=\sum_{k=0}^{n} \EE{N_i N_j \mid N_i = k}\cdot P\CB{N_i = k} \\
# &= \sum\nolimits_{k=0}^{n} k\EE{N_j \mid N_i = k} \cdot P\CB{N_i = k}
# \end{align}$
# >
# >Now given that only $k$ of the $n$ trials result in outcome $i$, each of the other $n-k$ trials independently results in outcome $j$ with probability: $P\P{j \mid \text{not }i} = \frac{p_j} {1-p_i}$, thus showing that the conditional distribution of $N_j$, given that $N_i = k$, is binomial with parameters $\P{n-k,\ffrac{p_j} {1-p_i}}$ and its expectation is: $\EE{N_j \mid N_i = k} = \P{n-k} \ffrac{p_j} {1-p_i}$.
# >
# >Using this yields:
# >$\bspace \begin{align}
# \EE{N_i N_j} &= \sum_{k=0}^{n} k\P{n-k} \ffrac{p_j} {1-p_i} P\CB{N_i = k} \\
# &= \ffrac{p_j} {1-p_i} \P{n \sum_{k=0}^{n} kP\CB{N_i = k} - \sum_{k=0}^{n} k^2 P \CB{N_i = k}} \\
# &= \ffrac{p_j} {1-p_i}\P{n\EE{N_i} - \EE{N_i^2}}
# \end{align}$
#
# >And $N_i$ is a binomial $r.v.$ with parameters $\P{n,p_i}$, thus, $\EE{N_i^2} = \Var{N_i} + \EE{N_i}^2 = np_i\P{1-p_i} + \P{np_i}^2$. Hence, $\EE{N_iN_j} = \ffrac{p_j} {1-p_i} \SB{n^2 p_i - np_i\P{1-p_i} - n^2p_i^2} = n\P{n-1}p_ip_j$, which yields the result:
# >
# >$\bspace \Cov{N_i N_j} = n\P{n-1}p_ip_j - n^2p_ip_j = -np_ip_j$

# **(V)e.g.** The Matching Rounds Problem from the example of last chapter, the one of randomly choosing hat. Now for those who have already chosen their own hats, leave the room. And then mix the wrongly-matched hats again and reselect. This process continues until each individual has his own hats.
#
# $\P{1}$ Let $R_n$ be the number of rounds that are necessary when $n$ individuals are initially present. Find $\EE{R_n}$.
#
# >Follow the results from last example. For each round, on average there'll be only *one* match, no matter how many candidates remain. So intuitively, $\EE{R_n} = n$. Here's an induction proof. Firstly, it's obvious $\EE{R_1} = $, then we assume that $\EE{R_k} = k$ for $k = 1,2,\dots,n-1$, then we find $\EE{R_n}$ by conditioning on $X_n$, which is the number of matches that occur in the first round:
# >
# >$\bspace \EE{R_n} = \d{\sum_{i=0}^{n} \EE{R_n \mid X_n = i}} \cdot P\CB{X_n = i}$. Now given that there're totally $i$ matches in the first round, then we have $\EE{R_n \mid X_n = i} = 1 + \EE{R_{n-i}}$.
# >
# >$\bspace \begin{align}
# \EE{R_n} &= \sum_{i=0}^{n} \P{1 + \EE{R_{n-i}}} \cdot P\CB{X_n = i} \\
# &= 1 + \EE{R_n} P\CB{X_n = 0} + \sum_{i=1}^{n} \EE{R_{n-i}} \cdot P\CB{X_n = i} \\
# &= 1 + \EE{R_n} P\CB{X_n = 0} + \sum_{i=1}^{n} \P{n-i} \cdot P\CB{X_n = i}, \; \text{as the induction hypothesis}\\
# &= 1 + \EE{R_n} P\CB{X_n = 0} + n\P{1-P\CB{X_n = 0}} - \EE{X_n}, \; \P{\EE{X_n} = 1 \text{ as the result before}}\\[0.6em]
# &= \EE{R_n} P\CB{X_n = 0} + n\P{1-P\CB{X_n = 0}}\\[0.7em]
# & \bspace \text{then we solve the equation,}\\[0.7em]
# \Longrightarrow& \space\EE{R_n} = n
# \end{align}$
#
# $Remark$
#
# >Assuming something happened in the first trial...
#
# $\P{2}$ Let $S_n$ be the total number of selections made by the $n$ individuals for $n \geq 2$. Find $\EE{S_n}$
#
# >Still we condition on $X_n$, which gives:
# >
# >$\bspace \begin{align}
# \EE{S_n} &= \sum_{i=0}^{n} \EE{S_n \mid X_n = i} \cdot P\CB{X_n = i} \\
# &= \sum_{i=0}^{n} \P{n + \EE{S_{n-i}}} \cdot P\CB{X_n = i} = n + \sum_{i=0}^{n} \EE{S_{n-i}} \cdot P\CB{X_n = i}
# \end{align}$
# >
# >And since $\EE{S_0} = 0$ we rewrite it as $\EE{S_n} = n + \EE{S_{n-X_n}}$. To solve this, we first make a guess. What if there were exactly one matach in each round?.
#
# >Thus, totally there'll be $n+\cdots+1  = n\P{n+1}/2$ selections. So, for $n \geq 2$, we assume that
# >
# >$\bspace an + bn^2 = n + \EE{a\P{n-X_n} + b\P{n-X_n}^2} = n + a\P{n-\EE{X_n}} + b\P{n^2 - 2n\EE{X_n} + \EE{X_n^2}}$
# >
# >Following the results before that $\EE{X_n} = \Var{X_n} = 1$, we can solve this that $a=1$ and $b = 1/2$. So that maybe, $\EE{S_n} = n + n^2/2$. What a guess (2333)! Now we prove it by induction on $n$.
# >
# > For $n=2$, the number of rounds is a geometric random variable with parameter $p = 1/2$. And it's obvious that the number of selections is twice the number of rounds. Thus, $\EE{S_n} = 4$. Right!
# >
# >Hence, upon assuming $\EE{S_0} = \EE{S_1} = 0$ and $\EE{S_k} = k+k^2/2$ for $k=2,3,\dots,n-1$:
# >
# >$\bspace \begin{align}
# \EE{S_n} &= n + \EE{S_n} \cdot P\CB{X_n = 0} + \sum_{i=1}^{n} \SB{n-i+\P{n-i}^2}\cdot P\CB{X_n=i}\\
# &= n + \EE{S_n}\cdot P\CB{X_n = 0} + \P{n+n^2/2}\P{1-P\CB{X_n = 0}} - \P{n+1}\EE{X_n} + \ffrac{\EE{X_n^2}} {2}\\[0.7em]
# & \bspace \text{then we solve the equation by using }\EE{X_n} = 1 \text{ and } \EE{X_n^2} = 2\\[0.7em]
# \Longrightarrow& \space\EE{S_n} = n+n^2/2
# \end{align}$
#
# $\P{c}$ Find the expected number of false selections made by one of the $n$ people for $n \geq 2$.
#
# >Let $C_j$ denote the number of hats chosen by person $j$, then we have $\sum C_j = S_n$. Then taking the expectation, using the fact that each $C_j$ takes the same mean, $\EE{C_j} = \EE{S_n}/ n = 1 + n/2$. Thus, the result is $\EE{C_j - 1} = n/2$.
#
# $\P{d}$ Suppose the first round, what if the first person cannot meet a match? Given that, find the conditional expected number of matches. 
#
# >Let $Y$ equal $1$ if the first person has a match and $0$ otherwise. Let $X$ denote the number of matches. Then, with the result before we have
# >
# >$\bspace \begin{align}
# 1 = \EE{X} &= \EE{X\mid Y=1} P\CB{Y=1} + \EE{X\mid Y=0} P\CB{Y=0} \\
# &= \ffrac{\EE{X\mid Y=1}} {n} + \ffrac{n-1} {n}\EE{X \mid Y = 0}
# \end{align}$
# >
# >Now given that $Y=1$, then the rest $n-1$ people will choose $n-1$ hats, thus $\EE{X\mid Y=1} = 1+1=2$, thus, the result is $\EE{X \mid Y=0} = \P{n-2}/\P{n-1}$

# **(V)e.g.** Consecutive success
#
# Independent trials, each of which is a success with probability $p$, are performed until there are $k$ consecutive success. What's the mean of necesssary trials?
#
# >Let $N_k$ denote the number of necessary trials to obtain $k$ consecutive success and $M_k = \EE{N_k}$. Then we might write: $N_k = N_{k-1} + \texttt{something}$... And actually that something is the number of additional trials needed to go from have $k-1$ successes in a row to having $k$ in a row. We denote that by $A_{k-1,k}$. Then we take the expectation and obtain:
#
# >$\bspace M_k = M_{k-1} + \EE{A_{k-1,k}}$. Wanna know what's $\EE{A_{k-1,k}}$? There're only two possible result, the $k\texttt{-th}$ trial is a success, or not, then:
# >
# >$\bspace \EE{A_{k-1,k}} = 1 \cdot p + \P{1+M_k}\cdot\P{1-p} = 1+\P{1-p}M_k \Rightarrow M_k = \ffrac{1} {p} + \ffrac{M_{k-1}} {p}$
# >
# >Well, what's $M_1$? Obviously $N_1$ is a geometric with parameter $p$, thus $M_1 = 1/p$ and recursively we have:
# >
# >$\bspace M_k = \ffrac{1} {p} + \ffrac{1} {p^2} + \cdots \ffrac{1} {p^k}$

# **(V)e.g.** Quick-Sort Algorithm
#
# Given a set of $n$ distinct values, sort them increasingly. The quick-sort algorithm is defined reursively as: When $n=2$, compare the two values and puts them in appropriate order. When $n>2$, randomly shoose one of the $n$ values, say, $x_i$ and then compares each of the other $n-1$ values with $x_i$, noting which are smaller and which are larger than $x_i$. Letting $S_i$ denote the set of elements smaller than $X_i$ and $\bar{S}_i$ the set of elements greater than $X_i$. Then sort the set $S_i$ and $\bar{S}_i$. That's it.
#
# One measure of the effectiveness of this algorithm is the expected number of comparison that it makes. Denote by $M_n$ the expected number of comparisons needed by the q-s algorithm to sort a set of $n$ distinct values. To obtain a recursion for $M_n$ we condition on the rank of the initial value selected to obtain
#
# $$M_n = \sum_{j=1}^{n} \EE{\text{number of comparisons}\mid \text{value selected is actually j}\texttt{-th}\text{ smallest}}\cdot \ffrac{1} {n}$$
#
# So $M_n = \d{\sum_{j=1}^{n} \P{n-1 + M_{j-1} + M_{n-j}}\cdot\frac{1} {n}} = n-1 + \ffrac{2} {n} \sum_{k=1}^{n-1} M_k$ ($M_0 = 0$), or equivalently, $nM_n = n\P{n-1} + 2\d{\sum_{k=1}^{n-1}}M_k$.
#
# 我们用一点数列知识。。。
#
# $\bspace \P{n+1}M_{n+1} - mM_n = 2n+2M_n \Longrightarrow M_n = 2\P{n+2}\sum\limits_{k=0}^{n-1}\ffrac{n-k} {\P{n+1-k}\P{n+2-k}} = 2\P{n+2}\sum\limits_{i=1}^{n} \ffrac{i} {\P{i+1}\P{i+2}}$ for $n \geq 1$.
#
# $$\begin{align}
# M_{n+1} &= 2\P{n+2}\SB{\sum_{i=1}^{n}\ffrac{2} {i+2} - \sum_{i=1}^{n}\ffrac{1} {i+1}} \\
# &\approx 2\P{n+2}\SB{\int_{3}^{n+2} \ffrac{2} {x} \;\dd{x} - \int_{2}^{n+1} \ffrac{1} {x} \;\dd{x}}\\
# &= 2\P{n+2}\SB{\log\P{n+2} + \log\P{\ffrac{n+1} {n+2}} + \log 2 -2\log 3}\\
# &\approx 2\P{n+2}\log\P{n+2}
# \end{align}$$

# ### Computing Variances by Conditioning
#
# Here we first gonna use $\Var{X} = \EE{X^2} - \EE{X}^2$ while using the condioning to obtain both the $\EE{X^2}$ and $\EE{X}$.
#
# **e.g.** Variance of the Geometric $r.v.$
#
# Independent trials, each resulting in a success with probability $p$ and are performed in sequence. Let $N$ be the trial number of the first success. Find $\Var{N}$.
#
# >Still we condition on the first trial: let $Y=1$ if the first trial is a success, and $0$ otherwise.
# >
# >$\bspace\begin{align}
# \EE{N^2} &= \EE{\EE{N^2\mid Y}} \\
# &= \EE{N^2 \mid Y=1}\cdot P\P{Y=1} + \EE{N^2 \mid Y=0}\cdot P\P{Y=0}\\
# &= 1 \cdot p + \EE{\P{1+N}^2} \cdot \P{1-p}\\
# &= 1 + \EE{2N+N^2} \cdot \P{1-p} \\
# &= 1 + 2 \P{1-p}\EE{N} + \EE{N^2}\cdot \P{1-p}
# \end{align}$
# >
# >And from **e.g.** The Mean of a Geometric Distribution, we've acquired that $\EE{N} = 1/p$, thus we can substitute this back and then solve the equation and get: $\EE{N^2} = \ffrac{2-p} {p^2}$. Then
# >
# >$\bspace \Var{N} = \ffrac{2-p} {p^2} - \P{\ffrac{1} {p}}^2 = \ffrac{1-p} {p^2}$

# ***
#
# Then how about (a drink?) $\Var{X \mid Y}$? Here's the proposition.
#
# $Proposition$ ***conditional variance formula***
#
# $\bspace \Var{X} = \EE{\Var{X \mid Y}} + \Var{\EE{X \mid Y}}$
#
# $Proof$
#
# >$\bspace \begin{align}\EE{\Var{X \mid Y}} &= \EE{\EE{X^2 \mid Y} - \P{\EE{X\mid Y}}^2} \\
# &= \EE{\EE{X^2 \mid Y}} - \EE{\P{\EE{X\mid Y}}^2} \\
# &= \EE{X^2} - \EE{\P{\EE{X\mid Y}}^2}
# \end{align}$
# >
# >$\bspace \begin{align}
# \Var{\EE{X \mid Y}} &= \EE{\P{\EE{X \mid Y}}^2} - \P{\EE{\EE{X \mid Y}}}^2\\
# &= \EE{\P{\EE{X \mid Y}}^2} - \P{\EE{X}}^2
# \end{align}$
# >
# >Therefore, $\EE{\Var{X \mid Y}} + \Var{\EE{X \mid Y}} = \EE{X^2} - \P{\EE{X}}^2 = \Var{X}$

# **e.g.** The Variance of a Compound $r.v.$
#
# Let $X_1,X_2,\dots$ be $i.i.d.$ $r.v.$ with distribution $F$ having mean $\mu$ and variance $\sigma^2$, and assume that they are independent of the nononegative integer valued $r.v.$ $N$. Here the **compound $r.v.$** is $S = \sum_{i=1}^{N}X_i$. Find its variance.
#
# >You can directly condition on $N$ to obtain $\EE{S^2}$, well.
# >
# >$\bspace \Var{S\mid N=n} = \Var{\sum\limits_{i=1}^{n} X_i} = n\sigma^2$
# >
# >and with the similar reasoning, we have $\EE{S \mid N=n} = n\mu$. Thus, $\Var{S\mid N} = N\sigma^2$ and $\EE{S \mid N} = N \mu$ and the conditional variance formula gives
# >
# >$\bspace \Var{S} = \EE{N\sigma^2} + \Var{N\mu} = \sigma^2 \EE{N} + \mu^2 \Var{N}$
#
# $Remark$
#
# >CANNOT directly write $\Var{S\mid N} = \EE{\P{S\mid N}^2}-\cdots$, because it's not well defined. So the correct way is to first find $\Var{S\mid N = n}$. Then convert this to the variable $\Var{S\mid N} = f\P{N}$
# ***

# **e.g.** The Variance in the Matching Rounds Problem
#
# Following the previous definition, $R_n$ is the number of rounds that are necesssary when $n$ individuals are initially present. Let $V_n$ be its variance. Show that $V_n = n$ for $n \geq 2$.
#
# > Actually when you try $n=2$, as shown before, it's a geometric with parameter $p = 1/2$ thus $V_2 = \ffrac{1-p} {p^2} = 2$. So the assumption here is $V_j = j$ for $2\leq j \leq n-1$. And when there're $n$ individuals. still we condition that on the first round, or more specificly, let $X$ be the number of matches in the first round. Thus $\EE{R_n \mid X} = 1 + \EE{R_{n-X}}$ and by the previous result, we have $\EE{R_n \mid X} = 1 + n - X$. Also with $V_0 = 0$, we have $\Var{R_n \mid X} = \Var{R_{n-X}} = V_{n-X}$. Hence by the **conditional variance formula**,
# >
# >$\bspace \begin{align}
# V_n &= \EE{\Var{R_n \mid X}} + \Var{\EE{R_n \mid X}} \\[0.6em]
# &= \EE{V_{n-X}} + \Var{1+n-X} \\[0.5em]
# &= \sum_{j=0}^{n} V_{n-j}\cdot P\CB{X=j} + \Var{X} \\
# &= V_n \cdot P \CB{X=0} + \sum_{j=1}^{n} \P{n-j}\cdot P\CB{X=j} + \Var{X} \\
# &= V_n \cdot P \CB{X=0} + n \P{1-P\CB{X=0}} - \EE{X} + \Var{X}
# \end{align}$
# >
# >Here $\EE{X}$ is given in a example from Chapter 2 and as for $\Var{X}$, with the similar method, we have
# >
# >$\bspace \begin{align}
# \Var{X} &= \sum\Var{X_i} + 2\sum_{i=1}^{N}\sum_{j>i} \Cov{X_i,X_j} \\
# &= N\P{\EE{X_i^2} - \P{\EE{X_i}}^2} + 2\sum_{i=1}^{N}\sum_{j>i} \P{\EE{X_iX_j} - \EE{X_i} \EE{X_j}} \\
# &= N\P{\ffrac{1} {N} - \ffrac{1} {N^2}} + 2 \ffrac{N\P{N-1}} {2} \P{\ffrac{1} {N\P{N-1}} - \ffrac{1} {N^2}} =1
# \end{align}$
# >
# >Thus we substitute the value into the last equation and solve is. Then it's proved.

# ## Computing Probabilities by Conditioning
#
# We've already know that by conditioning we can easily calculate the expectation and variance. Now we present how to use this method to find certain probabilities. First we define the ***indicator $r.v.$***:
#
# $\bspace X = \begin{cases}
# 1, &\text{if } E \text{ occurs}\\
# 0, &\ow
# \end{cases}$
#
# Then $\EE{X} = P\P{E}$ and $\EE{X\mid Y=y} = \P{E\mid Y=y}$ for any $r.v.$ $Y$. Therefore,
#
# $\bspace P\P{E} = \begin{cases}
# \d{\sum_y P\CB{E \mid Y=y} \cdot P\CB{Y=y}}, & \text{if }Y\text{ is discrete}\\
# \d{\int_{-\infty}^{\infty} P\CB{E \mid Y=y} \cdot f_Y\P{y}\;\dd{y}}, & \text{if }Y\text{ is continuous}\\
# \end{cases}$
#
# **e.g.** The probability of a $r.v.$ is less than another one
#
# Let $X$ and $Y$ be two independent continuous $r.v.$ with densities $f_X$ and $f_Y$ respectively. Compute $P\CB{X < Y}$
#
# > $\bspace \begin{align}
# P\CB{X < Y} &= \int_{-\infty}^{\infty} P\CB{X<Y \mid Y=y} \cdot f_Y\P{y} \;\dd{y} \\
# &= \int_{-\infty}^{\infty} P\CB{X<y} \cdot f_Y\P{y} \;\dd{y} \\
# &= \int_{-\infty}^{\infty} F_X\P{y} \cdot f_Y\P{y} \;\dd{y} \\
# \end{align}$

# **e.g.**
#
# A possion $r.v.$ with parameter $\lambda$, and each time it happens the result split into two, success and failure, with probability $p$ and $1-p$. Find the joint probability of exactly $n$ successes and $m$ failures.
#
# >Let $T$ be the total times it happens. We can directly write that 
# >
# >$\bspace \begin{align}
# P\CB{S=n,F=m} &= P\CB{S=n,F=m,T=n+m}\\
# &= P\CB{S=n,F=m \mid T = n+m} \cdot P\CB{T = n+m}
# \end{align}$
# >
# >or by 
# >
# >$\bspace \begin{align}
# P\CB{S=n,F=m} &= \sum\limits_{t=0}^{\infty}P\CB{S=n,F=m \mid T = t} \cdot P\CB{T =t} \\
# &= 0 + \CB{S=n,F=m \mid T = n+m} \cdot P\CB{T = n+m}
# \end{align}$
# >
# >Thus, since it's just a binomial probability of $n$ successes in a $n+m$ trials, we have
# >
# >$\bspace \begin{align}
# P\CB{S=n,F=m} &= \binom{n+m} {n} p^n \P{1-p}^{m} e^{-\lambda} \ffrac{\lambda^{n+m}} {\P{n+m}!}\\
# &= \ffrac{\P{n+m}!} {n!m!} p^n \P{1-p}^{m} \lambda^n \lambda^m \ffrac{e^{-\lambda p}e^{-\lambda\P{1-p}}} {\P{n+m}!}\\
# &= e^{-\lambda p} \ffrac{\P{\lambda p}^{n}} {n!}\cdot e^{-\lambda \P{1-p}} \ffrac{\P{\lambda \P{1-p}}^{m}} {m!}
# \end{align}$
# >
# >That's it.
#
# $Remark$
#
# >It's also can be regarded as the product of two independent terms who are only rely on $n$ and $m$ respectively. It follows that $S$ and $F$ are independent. Moreover,
# >
# >$\bspace P\CB{S=n} = \sum\limits_{m=0}^{\infty}P\CB{S=n,F=m} = e^{-\lambda p} \ffrac{\P{\lambda p}^{n}} {n!}$
# >
# >And similar for $P\CB{F=m} = e^{-\lambda \P{1-p}} \ffrac{\P{\lambda \P{1-p}}^{m}} {m!}$
#
# $Remark$
#
# >We can also generalize the result to the case where each of a Poisson distributed number of events, $N$, with mean $\lambda$ is independently classified as being one of $k$ types with the probability that it is type $i$ being $p_i$. And $N_i$ is the number that are classified as type $i$, then:
# >
# > $N_i$ for $i = 1,2,\dots,k$ are independent Poisson $r.v.$ with respective means $\lambda p_1,\lambda p_2,\dots, \lambda p_k$, and this follows that:
# >
# >$\bspace \begin{align}
# &P\CB{N_1 = n_1, N_2 = n_2,\dots, N_k = n_k} \\
# =\;& P\CB{N_1 = n_1, N_2 = n_2,\dots, N_k = n_k \mid N = n} \cdot P\CB{N = n} \\[0.5em]
# =\;& \binom{n} {n_1,n_2,\dots,n_k} \cdot e^{-\lambda} \ffrac{\lambda^n} {n!} \\
# =\;& \prod_{i=1}^{k} e^{-\lambda p_i} \ffrac{\P{\lambda p_i}^{n_i}}{n_i!}
# \end{align}$

# **e.g.** The Distribution of the Sum of Independent Bernoulli $r.v.$
#
# Let $X_i$ be independent Bernoulli $r.v.$ with $P\CB{X_i = 1} = p_i$. What's the pmf of $\sum X_i$? Here's a recursive way to obtain all these.
#
# > First let $P_k\P{j} = P\CB{X_1 + X_2 + \cdots + X_k = j}$ and note that $P_k\P{0} = \prod\limits_{i=1}^{k} q_i$, and $P_k\P{k} = \prod\limits_{i=1}^{k} p_i$. Then we condition $P_k\P{j}$ on $X_k$. (We don't contion that on the first event this time, cause we are doing a recursion! RECURSION! F\*\*\*)
# >
# > $\bspace \begin{align}
# P_k\P{j} &= P\CB{X_1 + X_2 + \cdots + X_k = j \mid X_k = 1} \cdot p_k + P\CB{X_1 + X_2 + \cdots + X_k = j \mid X_k = 0} \cdot q_k \\
# &= P_{k-1}\P{j-1}  \cdot p_k + P_{k-1}\P{j} \cdot q_k
# \end{align}$

# **e.g.** The Best Prize Problem
#
# $n$ girls appeared in my life in sequence. I have to confess once if I met her or never would I got another chance. The only information I have when deciding whether to confess is the relative rank of that girl compared to ones alreay met. My wish is to maximize the probability of obtaining the best lover. Assuming all $n!$ ordering of the girls are equally likely, how do we do?
#
# > Strategy: fix a value $k$ and only confess to the first girl after that is better than all first $k$ girls. Using this, we denote $P_k\P{\text{best}}$ as the probability that the best girl is confessed by me.
# >And to find that we condition that on $X$, the position of best girl. This gives:
# >
# >$\bspace \begin{align}
# P_k\P{\text{best}} &= \sum_{x=1}^{n} P_k\P{\text{best}\mid X =x}\cdot P\CB{X = x} \\
# &= \ffrac{1} {n}\P{\sum_{x=1}^{k} P_k\P{\text{best}\mid X =x} +\sum_{x=k+1}^{n} P_k\P{\text{best}\mid X =x}}\\
# &= \ffrac{1} {n}\P{0 + \sum_{x=k+1}^{n}\ffrac{k} {i-1}}\\
# &\approx \ffrac{k} {n}\int_{k}^{n-1} \ffrac{1} {x} \;\dd{x} \approx \ffrac{k} {n} \log\P{\ffrac{n} {k}}
# \end{align}$
#
# >To find its maximum, we differentiate $g\P{x} = \ffrac{x} {n} \log\P{\ffrac{n} {x}}$ and get $x_{\min} = \ffrac{n} {e}$

# **e.g.** Hat match game
#
# $n$ men with their hats mixed up and then each man randomly select one. What's the probability of no matches? or exactly $k$ matches?
#
# >We are finding this by conditioning on whether or not the first man selects his own hat, $M$ or $M^c$. Let $E$ denote the event that no matches occur. Then
# >
# >$\bspace P_n = P\P{E} = P\P{E\mid M} \cdot P\P{M} + P\P{E\mid M^c} \cdot P\P{M^c}=P\P{E\mid M^c}\ffrac{n-1} {n}$
# >
# >Following that, since it's given that the first man doesn't get a hat, then there're only $n-1$ men left and thus
# >
# >$\bspace P\P{E\mid M^c} = P_{n-1} + \ffrac{1} {n-1} P_{n-2}$
# >
# >saying that it's equal to the condition when the second person find his hat, or not.
# >
# >Then since $P_1 = 0$, $P_2 = 0.5$ we can find all of them recursively.

# **e.g.** The Ballot Problem
#
# In an election, candidate $A$ have received $n$ votes, and $B$, $m$ votes with $n>m$. Assuming that all orderings are equally likely, show that the probability that $A$ is always ahead in the count of votes is $\P{n-m}/\P{n+m}$.
#
# >Let $P_{n,m}$ denote the desired probability then:
# >
# >$\begin{align}
# P_{n,m} &= P\CB{A \text{ always ahead}\mid A \text{ receive last vote}} \cdot \ffrac{n} {n+m} \\
# & \bspace + P\CB{A \text{ always ahead}\mid B \text{ receive last vote}} \cdot \ffrac{m} {n+m} \\
# &= \ffrac{n} {n+m} \cdot P_{n-1,m} + \ffrac{m} {n+m} \cdot P_{n,m-1} 
# \end{align}$
# >
# >Then by induction, done! $P_{n,m} = \ffrac{n} {n+m} \cdot \ffrac{n-1-m} {n-1+m} + \ffrac{m} {n+m} \cdot \ffrac{n-m+1} {n+m-1} = \ffrac{n-m} {n+m}$
#
# ***

# **e.g.**
#
# Let $U_1,U_2,\dots$ be a sequence of independent uniform $\P{0,1}$ $r.v.$, and let $N = \min\CB{n \geq 2: U_n > U_{n-1}}$ and $M = \min\CB{n \geq 1: U_1 + U_2 + \dots + U_n > 1}$. Surprisingly, $N$ and $M$ have the same probability distribution, and their common mean is $e$! Prove it!
#
# > For $N$ since all the possible ordering or $U_1,\dots,U_n$ are equally likely, we have:
# >
# >$\bspace P\CB{U_1 > U_2 > \cdots > U_n} = \ffrac{1} {n!} = P\CB{N > n}$.
# >
# >For $M$, to use induction method, we intend to prove $P\CB{M\P{x} > n} = x^n/n!$ where $M\P{x} = \min\CB{n\geq 1: U_1 + U_2 + \cdots + U_n > x}$, for $0 < x \leq 1$. When $n=1$,
#
# > $\bspace P\CB{M\P{x} > 1} = P\CB{U_1 \leq x} = x$
# >
# >Then assume that holds true for all $n$ to determine $P\CB{M\P{x} > n+1}$ we condition that on $U_1$ to obtain:
# >
# >$\bspace \begin{align}
# P\CB{M\P{x} > n+1} &= \int_{0}^{1} P\CB{M\P{x} > n+1\mid U_1 = y}\;\dd{y} \\
# & \bspace\text{since }y \text{ cannot exceed }x\text{ , we change the upper limit of integral} \\
# &= \int_{0}^{x} P\CB{M\P{x} > n+1\mid U_1 = y}\;\dd{y} \\
# &= \int_{0}^{x} P\CB{M\P{x-y} > n}\;\dd{y} \\
# &\bspace \text{induction hypothesis}\\
# &= \int_{0}^{x} \ffrac{\P{x-y}^n} {n!}\;\dd{y} \\
# &\using{u=x-y} \int_{0}^{x} \ffrac{u^n} {n!} \;\dd{u} \\
# &= \ffrac{x^{n+1}} {\P{n+1}!}
# \end{align}$
# >
# >Thus $P\CB{M\P{x} > n} = x^n/n!$ and let $x=1$ and we can draw the final conclusion that $P\CB{M > 1} = 1/n!$, so that $N$ and $M$ have the same distribution. Finally, we have:
# >
# >$$\EE{M} = \EE{N} = \QQQ \sum_{n=0}^{\infty} 1/n! = e$$

# **e.g.** 
#
# Let $X_1, X_2,\dots,X_n$ be independent continuous $r.v.$ with a common distribution function $F$ and density $f = F'$, suppose that they are to be observed one at a time in sequence. Let $N = \min\CB{n\geq 2: X_n = \text{second largest of }X_1,X_2,\dots,X_n}$ and $M = \min\CB{n\geq 2: X_n = \text{second smallest of }X_1,X_2,\dots,X_n}$. Which one tends to be larger?
#
# > To find $X_N$ it's natural to condition on the value of $N$. We first let $A_i = \CB{X_i \neq \text{second largest of }X_1,X_2,\dots,X_i}, i\geq 2$. Thus
# >
# > $$\newcommand{\void}{\left.\right.}P\CB{N=n} = P\P{A_2A_3\cdots A_{n-1}A^c} = \ffrac{1} {2}\ffrac{2} {3}\cdots\ffrac{n-2} {n-1} \ffrac{1} {n} = \ffrac{1} {n\P{n-1}}$$
# >
# >Here $A_i$ being independent is because $X_i$ are $i.i.d.$. Then we condition that on $N$ and obtain:
# >
# >$$\begin{align}
# f_{X_{\void_N}}\P{x} &= \sum_{n=2}^{\infty} \ffrac{1} {n\P{n-1}} f_{X_{\void_N}\mid N} \P{x\mid n} \\
# &= \sum_{n=2}^{\infty} \ffrac{1} {n\P{n-1}} \ffrac{n!} {1!\P{n-2}!} \P{F\P{x}}^{n-2}\cdot f\P{x} \cdot \P{1-F\P{x}} \\
# &= f\P{x} \cdot \P{1-F\P{x}} \sum_{n=0}^{\infty} \P{F\P{x}}^i \\
# &= f\P{x}
# \end{align}$$
# >
# >We are almost there. Now we think their opposite number. Let $W_i = -X_i$, then $M = \min\CB{n\geq 2: X_n = \text{second largest of }W_1,W_2,\dots,W_n}$. So similiarly, $W_M$ has the same distribution with $W_1$ just like $X_N$ and $X_1$. Then we drop the minus sign so that $X_M$ has the same distribution with $X_1$. So they all are of the same distribution.
#
# $Remark$
#
# >This is a special case for ***Ignatov's Theorem***, where second could be $k\texttt{th}$ largest/smallest. Still the distribution is $F$, for all $k$!
#
# ***

# **(V)e.g.**
#
# A population consists of $m$ families. Let $X_j$ denote the size of family $j$ and suppose that $X_1,X_2,\dots,X_m$ are independent $r.v.$ having the common pmf: $p_k = P\CB{X_j = k}, \sum_{i=1}^{\infty}p_k = 1$ with mean $\mu = \sum\limits_k k\cdot p_k$. Suppose a member of whatever family is chosen randomly, and let $S_i$ be the event that the selected individual is from a family of size $i$. Prove that $P\P{S_i} \to \ffrac{ip_i} {\mu}$ as $m \to \infty$.
#
# > This time we need to condition on a vector of $r.v.$. Let $N_i$ be the number of familier that are of size $i$: $N_i = \#\CB{k:k=1,2,\dots,m:X_k = i}$; and then condition on $\mathbf{X} = \P{X_1,X_2,\dots,X_m}$:
# >
# >$$P\P{S_i\mid \mathbf{X}} = \ffrac{iN_i} {\sum_{i=1}^{m} X_k}$$
# >
# >$$P\P{S_i} = \EE{P\P{S_i\mid X}} 
# = \EE{\ffrac{iN_i} {\sum_{i=1}^{m} X_k}} 
# = \EE{\ffrac{iN_i/m} {\sum_{i=1}^{m} X_k/m}}$$
# >
# >$\bspace$This follows by the **strong law of large numbers** that $N_i/m$ would converges to $p_i$ as $m \to \infty$, and $\sum_{i=1}^{m} X_k/m \to \EE{X} = \mu$. Thus: $P\P{S_i} \to \EE{\ffrac{ip_i} {\mu}} = \ffrac{ip_i} {\mu}$ as $m \to \infty$
#
# ***

# **e.g.**
#
# Consider $n$ independent trials in which each trials results in one of the outcomes $1,2,\dots,k$ with respective probabilities $p_i$ and $\sum p_i = 1$. Suppose further that $n > k$, and that we are interested in determining the probability that each outcome occurs at least once. If we let $A_i$ denote the event that outcome $i$ dose not occur in any of the $n$ trials, then the desired probability is $1 - P\P{\bigcup_{i=1}^{k} A_i}$ and by the inclusion-exclusion theorem, we have
#
# $$\begin{align}
# p\P{\bigcup_{i=1}^{k} A_i} =& \sum_{i=1}^{k} P\P{A_i} - \sum_i\sum_{j>i} P\P{A_iA_j} \\
# &\bspace + \sum_i\sum_{j>i}\sum_{k>j} P\P{A_iA_jA_k} - \cdots + \P{-1}^{k+1} P\P{A_1 \cdots A_k}
# \end{align}$$
#
# where
#
# $$\begin{align}
# P\P{A_i} &= \P{1-p_i}^{n} \\
# P\P{A_iA_j} &= \P{1-p_i - p_j}^{n}, \bspace i < j\\
# P\P{A_iA_jA_k} &= \P{1-p_i - p_j - p_k}^{n}, \bspace i < j < k\\
# \end{align}$$
#
# How to solve this by conditioning on whatever something?
#
# > Note that if we start by conditioning on $N_k$, the number of times that outcome $k$ occurs, then when $N_k>0$ the resulting conditional probability will equal the probability that all of the outcomes $1,2,\dots,k-1$  occur at least once when $n-N_k$ trails are performed, and each results in outcome $i$ with probability $p_i/\sum_{j=1}^{k-1} p_j$, for $i = 1, 2,\dots,k-1$. Then we could use a similar conditioning step on these terms.
# >
# >Follow this idea, we let $A_{m,r}$, for $m\leq n, r\leq k$, denote the event that each of the outcomes $1,2,\dots,r$ occurs at least once when $m$ independent trails are performed, where each trial results in one of the outcomes $1,2,\dots,r$ with respective probabilities $p_1/P_r, \dots,p_r/P_r$, where $P_r = \sum_{j=1}^{r}p_j$. Then let $P\P{m,r} = P\P{A_{m,r}}$ and note that $P_{n,k}$ is the desired probability. To obtain the expression of $P\P{m,r}$, condition on the number of times that outcome $r$ occurs. This gives rise to:
# >
# >$\bspace\begin{align}
# P_{m,r} &= \sum_{j=0}^{m} P\CB{A_{m,r} \mid r \text{ occurs }j \text{ times}} \binom{m}{j} \P{\ffrac{p_r} {P_r}}^j \P{1 - \ffrac{p_r} {P_r}}^{m-j} \\
# &= \sum_{j=1}^{m-r+1} P_{m-j,r-1}\binom{m}{j} \P{\ffrac{p_r} {P_r}}^j \P{1 - \ffrac{p_r} {P_r}}^{m-j}
# \end{align}$
# >
# >Starting with $P\P{m,1} = 1$ for $m \geq 1$ and $P\P{m,1} = 0$ for $m=0$.
# >
# >And this's how this recursion works. We can first find the $P\P{m,2}$ for $m = 2,3,\dots,n-\P{k-2}$ and then $P\P{m,3}$ for $m = 2,3,\dots,n-\P{k-3}$ and so on, up to $P\P{m,k-1}$ for $m = k-1,k,\dots,n-1$. Then we use the recursion to compute $P\P{n,k}$.
#
# ***

# Now we extend our conclusion of how to calculate certain expectations using the conditioning fashion. Here's another formula for this:
#
# $\bspace\EE{X \mid Y = y} = \begin{cases}
# \d{\sum_{w} \EE{X \mid W = w, Y = y} \cdot P\CB{W = w \mid Y = y}}, & \text{if } W \text{ discrete} \\
# \d{\int_{w} \EE{X \mid W = w, Y = y} \cdot f_{W \mid Y}P\P{w \mid y} \;\dd{w}}, & \text{if } W \text{ continuous}
# \end{cases}$
#
# and we write this as $\EE{X \mid Y} = \EE{\EE{X \mid Y,W}\mid Y}$
#
# **e.g.**
#
# Automobile insurance company classifies its policyholders as one of the types $1, 2, \dots, k$. It supposes that the numbers of accidents that a type $i$ policyholder has in the following years are independent Poisson random variables with mean $\lambda_i$. For a new policyholder, the probability that he being type $i$ is $p_i$.
#
# Given that a policyholder had $n$ accidents in her first year, what is the expected number that she has in her second year? What is the conditional probability that she has $m$ accidents in her second year?
#
# >Let $N_i$ denote the number of accidents the policyholder has in year $i$. To obtain $\EE{N_2 \mid N_1 = n}$, condition on her risk type $T$.
#
# >$$\begin{align}
# \EE{N_2 \mid N_1 = n} &= \sum_{j=1}^{k} \EE{N_2\mid T = j, N_1 = n} \cdot P\CB{T = j \mid N_1 = n} \\
# &= \sum_{j=1}^{k} \EE{N_2\mid T = j} \cdot \ffrac{P\CB{T = j, N_1 = n}} {P\CB{N_1 = n}} \\
# &= \ffrac{\sum\limits_{j=1}^{k} \lambda_j \cdot P\CB{N_1 = n \mid T = j} \cdot P\CB{T = j}} {\sum\limits_{j=1}^{k} P \CB{ N_1 = n \mid T = j}\cdot P\CB{T = j}} \\
# &= \ffrac{\sum\limits_{j=1}^{k} e^{-\lambda_j} \lambda_j^{n+1}p_j} {\sum\limits_{j=1}^{k} e^{-\lambda_j} \lambda_j^{n} p_j}
# \end{align}$$
# >
# >$$\begin{align}
# P\CB{N_2 = m \mid N_1 = n} &= \sum_{j=1}^{k} P\CB{N_2 = m \mid T = j, N_1 = n} \cdot P\CB{T = j \mid N_1 = n} \\
# &= \sum_{j=1}^{k} e^{-\lambda_j} \ffrac{\lambda_j^m} {m!} \cdot P\CB{T = j \mid N_1 = n} \\
# &= \ffrac{\sum\limits_{j=1}^{k} e^{-2\lambda_j} \lambda_j^{m+n} p_j} {m! \sum\limits_{j=1}^{k} e^{-\lambda_j} \lambda_j^n p_j}
# \end{align}$$
#
# $Remark$
#
# $\bspace P\P{A \mid BC} = \ffrac{P\P{AB \mid C}} {P\P{B \mid C}}$
# ***

# ## Some Applications
# See the extended version later if possible.😥
#
# ## An Identity for Compound Random Variables
#
# Let $X_1,X_2,\dots$ be a sequence of $i.i.d.$ $r.v.$ and let $S_n = \sum_{i=1}^{n} X_i$ be the sum of the first $n$ of them, $n \geq 0$, where $S_0 = 0$. Then the **compound random variable** is defined as $S_N = \sum\limits^N X_i$ with the distribution of $N$ called the **compounding distribution**.
#
# To find $S_N$, first define $M$ as a $r.v.$ that is independnet of the sequence $X_1,X_2,\dots$, and which is such that $P\CB{M = n} = \ffrac{nP\CB{N = n}} {\EE{N}}$.
#
# $Proposition.5$ The Compound $r.v.$ Identity
#
# $\bspace$For any function $h$, $\EE{S_N h\P{S_N}} = \EE{N} \cdot \EE{X_1 h\P{S_M}}$
#
# $Proof$
#
# $$\begin{align}
# \EE{S_N h\P{S_N}} &= \EE{\sum_{i=1}^{N} X_i h\P{X_N}} \\
# &= \sum_{n=0}^{\infty} \EE{\sum_{i=1}^{N} X_i h\P{X_N}\mid N = n} \cdot P\CB{N = n} \\
# &= \sum_{n=0}^{\infty} \EE{\sum_{i=1}^{n} X_i h\P{X_N}\mid N = n} \cdot P\CB{N = n} \\
# &  \bspace\text{by the independence of }N \text{ and }X_1,X_2,\dots \\
# &= \sum_{n=0}^{\infty} \EE{\sum_{i=1}^{n} X_i h\P{X_N}} \cdot P\CB{N = n} \\
# &= \sum_{n=0}^{\infty} \sum_{i=1}^{n} \EE{X_i h\P{S_n}} \cdot P\CB{N = n} \\
# &  \bspace\EE{X_ih\P{X_1 + X_2 + \cdots + X_n}} \text{ are symmetric} \\
# &= \sum_{n=0}^{\infty} n \EE{X_1 h\P{S_n}} \cdot P\CB{N = n} \\
# &= \EE{N} \sum_{n=0}^{\infty} \EE{X_1 h\P{S_n}} \cdot P\CB{M = n} \\
# &= \EE{N} \sum_{n=0}^{\infty} \EE{X_1 h\P{S_n} \mid M = n} \cdot P\CB{M = n} \\
# &  \bspace\text{independence of  }M \text{ and }X_1,X_2,\dots, X_n \\ 
# &= \EE{N} \sum_{n=0}^{\infty} \EE{X_1 h\P{S_M} \mid M=n} \cdot P\CB{M = n} \\
# &= \EE{N} \EE{X_1 h\P{S_M}}
# \end{align}$$

# $Corollary.6$
#
# Suppose $X_i$ are positive integer valued $r.v.$, and let $\alpha_j = P\CB{X_1 = j}$, for $j > 0$. Then:
#
# $\bspace\begin{align}
# P\CB{S_N = 0} &= P\CB{N = 0} \\
# P\CB{S_N = k} &= \ffrac{1}{k} \EE{N} \sum_{j=1}^{k} j \alpha_j P\CB{S_{M-1} = k-j}, k > 0
# \end{align}$
#
# $Proof$
#
# >For $k$ fixed, let
# >
# >$\bspace h\P{x} = \begin{cases}
# 1, & \text{if } x = k \\
# 0, & \text{if } x \neq k
# \end{cases}$
# >
# >and then $S_N h\P{S_N}$ is either equal to $k$ if $S_N = k$ or is equal to $0$ otherwise. Therefore,
# >
# >$$\EE{S_Nh\P{S_N}}  = k P\CB{S_N = k}$$
# >
# >and the compound identity yields:
# >
# >$$\begin{align}
# kP\CB{S_N = k} &= \EE{N} \EE{X_1 h\P{S_M}} \\
# &= \EE{N} \sum_{j=1}^{\infty} \EE{X_1 h\P{S_M} \mid X_1 = j} \alpha_j \\
# &= \EE{N} \sum_{j=1}^{\infty} j \EE{h\P{S_M} \mid X_1 = j} \alpha_j \\
# &= \EE{N} \sum_{j=1}^{\infty} j P\CB{S_M = k \mid X_1 = j} \alpha_j \\
# \end{align}$$
#
# >And now, 
# >
# >$$\begin{align}
# P\CB{S_M = k \mid X_1 = j} &= P\CB{\sum_{i=1}^{M} X_i = k \mid X_1 = j} \\
# &= P\CB{j + \sum_{i=2}^{M} X_i = k \mid X_1 = j} \\
# &= P\CB{j + \sum_{i=1}^{M-1} X_i = k} \\
# &= P\CB{S_{M-1} = k-j}
# \end{align}$$
#
# $Remark$
#
# That's almost the end. Later we will show how to use this relationship to solve the problem using recursion.

# ### Poisson Compounding Distribution
#
# Using $Proposition.5$, if $N$ is the Poisson distribution with mean $\lambda$, then
#
# $\bspace\begin{align}
# P\CB{M-1 = n} &= P\CB{M = n+1} \\
# &= \ffrac{\P{n+1}P\CB{N = n+1}} {\EE{N}}\\
# &= \ffrac{1} {\lambda} \P{n+1} e^{-\lambda} \ffrac{\lambda^{n+1}} {\P{n+1}!} \\
# &= e^{-\lambda} \ffrac{\lambda^n} {n!}
# \end{align}$
#
# Thus with $P_n = P\CB{S_N = n}$, the recursion given by $Corollary.6$ can be written as
#
# $\bspace\begin{align}
# P_0 = P\CB{S_N = 0} &= P\CB{N = 0} = e^{-\lambda} \\
# P_k = P\CB{S_N = k} &= \ffrac{1}{k} \EE{N} \sum_{j=1}^{k} j \alpha_j P\CB{S_{M-1} = k-j} = \ffrac{\lambda} {k} \sum_{j=1}^{k} j \alpha_j P_{k-j}, \bspace k > 0
# \end{align}$
#
# $Remark$
#
# When $X_i$ are chosen to be identical $1$, then the preceding expressions are reduced to a **Poisson** $r.v.$
#
# $\bspace\begin{align}
# P_0 &= e^{-\lambda} \\
# P_n &= \ffrac{\lambda} {n} P\CB{N = n-1}, \bspace k > 0
# \end{align}$
# ***

# **e.g.**
#
# Let $S$ be a compound **Poisson** $r.v.$ with $\lambda = 4$ and $P\CB{X_i = i} = 0.25, i=1,2,3,4$.
#
# >$\bspace\begin{align}
# P_0 &= e^{-\lambda} = e^{-4} \\
# P_1 &= \lambda\alpha_1 P_0 = e^{-4} \\
# P_2 &= \ffrac{\lambda} {2} \P{\alpha_1 P_1 + 2 \alpha_2 P_0} = \ffrac{3} {2} e^{-4} \\
# P_3 &= \ffrac{\lambda} {3} \P{\alpha_1 P_2 + 2 \alpha_2 P_1 + 3 \alpha_3 P_0} = \ffrac{13} {6} e^{-4} \\
# P_4 &= \ffrac{\lambda} {4} \P{\alpha_1 P_3 + 2 \alpha_2 P_2 + 3 \alpha_3 P_1 + 4 \alpha_4 P_0} = \ffrac{73} {24} e^{-4} \\
# P_5 &= \ffrac{\lambda} {5} \P{\alpha_1 P_4 + 2 \alpha_2 P_3 + 3 \alpha_3 P_2 + 4 \alpha_4 P_1 + 5 \alpha_5 P_0} = \ffrac{381} {120} e^{-4} \\
# \end{align}$

# ### Binomial Compounding Distribution
#
# Suppose $N$ is a binomial $r.v.$ with parmeter $r$ and $p$, then
#
# $\bspace\begin{align}
# P\CB{M-1 = n} &= \ffrac{\P{n+1}P\CB{N = n+1}} {\EE{N}}\\
# &= \ffrac{n+1} {rp} \binom{r} {n+1} p^{n+1} \P{1-p}^{r-n-1} \\
# &= \ffrac{\P{r-1}!} {\P{r-1-n}!n!} p^n \P{1-p}^{r-1-n}
# \end{align}$
#
# Thus $M-1$ is also a binomial $r.v.$ with parameters $r-1$, $p$.
# ***
# The missing part in this Charpter might be included in future bonus content... I need to carry on to the next chapter, the Markov Chain

StarcoderdataJupyterScriptsDedupFiltered