Improved cross-entropy and original cross-entropy methods

1. Formula
   Observation

   The notebook text states `gamma = 5` and the problem statement uses `P(X > gamma)`.

2. Audio
   Observation

   The narrator says the example estimates when a standard normal variable exceeds a large threshold gamma.

$\gamma$

Threshold defining the rare event $X>\gamma$.

Real number; in this example $\gamma=5$.

1. Formula
   Observation

   The notebook states `X ~ Normal(0, 1)`.

2. Audio
   Observation

   The narrator refers to a standard normal variable.

X

Random variable whose exceedance probability is being estimated.

$X \sim \mathrm{Normal}(0,1)$.

1. Formula
   Observation

   The notebook writes `$g*(x) = P$($X = x$ | X > gamma)`.

2. Audio
   Observation

   The narrator calls it the zero-variance density $g^*$ and explains it as the distribution of $X$ conditioned on the rare event happening.

1. The displayed notation uses `P($X = x$ | X > gamma)` for a continuous random variable; the video does not discuss this notational issue.

g^*

Zero-variance importance-sampling density, equal to the conditional distribution of $X$ given $X>\gamma$.

Density over $x>\gamma$.

1. Formula
   Observation

   The code computes `mu = np.mean(Xs)` under the comment about fitting the IS proposal distribution.

2. Audio
   Observation

   The narrator says the proposal density is created by finding maximum likelihood estimates for mu and sigma.

$\mu$

Mean parameter of the fitted Normal importance-sampling proposal distribution.

Real number estimated from the retained $g^*$ samples.

1. Formula
   Observation

   The code computes `sigma = np.sqrt(np.mean((Xs-mu)**2))`.

2. Audio
   Observation

   The narrator says the proposal density is created by finding maximum likelihood estimates for mu and sigma.

$\sigma$

Standard deviation parameter of the fitted Normal importance-sampling proposal distribution.

Positive real number estimated from the retained $g^*$ samples.

1. Formula
   Observation

   The first simulation cell sets `$R = 5 * 10$**8` before drawing `rng.normal(size=R)`.

2. Audio
   Observation

   The narrator says they simulate five by ten to the eighth samples of X's.

R

Number of raw standard-normal draws used for rejection sampling to obtain $g^*$ samples.

In the first cell, $R=5\times 10^8$.

1. Formula
   Observation

   The final estimation cell sets `$R = 10$**6` before drawing `normals = rng.normal(mu, sigma, R)`.

1. The same symbol name `R` is reused with a different value in a later cell.

R

Number of samples drawn from the fitted importance-sampling proposal distribution.

In the final cell, $R=10^6$.

1. Formula
   Observation

   The code computes `lrs = stats.norm.pdf(normals, 0, 1) / stats.norm.pdf(normals, mu, sigma)`.

2. Audio
   Observation

   The narrator says they proceed with a normal importance sampling estimation.

lrs

Likelihood ratios (importance weights) $f(x)/g(x)$ evaluated at proposal samples.

Positive real values for each sampled `normals` point.

1. Formula
   Observation

   The code computes `ests = lrs * (normals > gamma)`.

ests

Weighted indicator estimates for the rare event, equal to the likelihood ratio when the proposal sample exceeds $\gamma$ and zero otherwise.

Nonnegative real array.

1. Formula
   Observation

   The code computes `lHat = ests.mean()` and prints `ICE estimate`.

2. Audio
   Observation

   The narrator says they print out the probability estimate L hat.

$\hat{L}$

Importance-sampling estimate of $P(X>\gamma)$, computed as the sample mean of `ests`.

Real number; printed value is approximately $2.8499557494141556\times 10^{-7}$.

1. Formula
   Observation

   The code computes `oHat = ests.std()`.

$\hat{o}$

Sample standard deviation of the weighted estimator array `ests`, used to form the confidence-interval half-width.

Nonnegative real number.

1. Formula
   Observation

   The code computes `widthCI = 1.96 * oHat / np.sqrt(R)`.

2. Audio
   Observation

   The narrator says the estimate has a confidence interval width in the order of ten to the minus ten.

1. The code labels this quantity `widthCI`, but numerically it is the half-width of a symmetric interval because it is added to and subtracted from `lHat`.

widthCI

Half-width of the reported confidence interval for the importance-sampling estimate.

Positive real number; printed value is approximately $8.28267698086911\times 10^{-10}$.

1. Formula
   Observation

   The notebook heading reads `Improved cross-entropy method` and the text states `Use the improved cross-entropy method to estimate P(X > gamma) where X ~ Normal(0, 1) and gamma = 5. Consider importance sampling distributions of the form Normal(mu, sigma^2).`

2. Audio
   Observation

   The narrator introduces a simple example estimating the probability that a standard normal variable exceeds a large threshold gamma, and says they will find the best importance sampling density within the family of normal distributions.

The segment defines the target quantity as the exceedance probability $P(X>\gamma)$ for a standard normal random variable, with $\gamma=5$, and restricts the importance-sampling proposal family to Normal distributions parameterized by $(\mu,\sigma^2)$.

1. The original distribution is standard normal.

2. The rare event is $X>\gamma$.

3. The proposal family is restricted to Normal distributions.

1. Formula
   Observation

   The notebook text states `First, to sample from $g*(x) = P$($X = x$ | X > gamma), just sample lots of X's and extract those X > gamma.`

2. Audio
   Observation

   The narrator says the first step is to sample from the zero-variance density $g^*$, which is the distribution of $X$ conditioned on the rare event happening.

1. The displayed formula uses `P($X = x$ | X > gamma)` for a continuous variable; the video does not clarify this notation.

The video identifies the ideal importance-sampling density $g^*$ as the conditional distribution of $X$ given that the rare event occurs, i.e. given $X>\gamma$. This is the density that would make the importance-sampling estimator have zero variance.

1. Applies to the rare-event probability $P(X>\gamma)$.

2. $g^*$ is supported only on the event region $x>\gamma$.

1. Problem setup for rare-event estimation

1. Formula
   Observation

   The code cell performs `Xs = rng.normal(size=R)` followed by `Xs = Xs[Xs > gamma]`.

2. Audio
   Observation

   The narrator says they can sample lots of X's and just keep those which exceed the threshold, and explicitly names this procedure rejection sampling.

Because $g^*$ is the conditional law of $X$ given $X>\gamma$, the video obtains approximate $g^*$ samples by drawing many raw standard-normal variates and retaining only those larger than the threshold. The retained subset is then treated as samples from $g^*$.

1. Requires direct sampling from the original distribution $X\sim\mathrm{Normal}(0,1)$.

2. The acceptance rule is $X_i>\gamma$.

3. The retained samples are used to estimate the parameters of the proposal distribution.

1. Zero-variance density as the conditional law given the rare event

1. Formula
   Observation

   The code computes `mu = np.mean(Xs)` and `sigma = np.sqrt(np.mean((Xs-mu)**2))` under the comment `# Fit our IS proposal distribution to these g* samples`.

2. Audio
   Observation

   The narrator says they create the importance sampling proposal density by finding the maximum likelihood estimates for mu and sigma given these samples.

After obtaining samples from $g^*$, the video fits a Normal importance-sampling proposal by setting its mean to the sample mean and its standard deviation to the square root of the sample second central moment of those retained samples.

1. The fitted proposal family is Normal.

2. The data used for fitting are the retained samples satisfying $X>\gamma$.

3. The estimator for $\sigma$ uses division by $n$, matching the code `np.mean((Xs-mu)**2)` rather than an unbiased sample variance.

1. Rejection sampling to obtain samples from $g^*$
2. Problem setup for rare-event estimation

1. Formula
   Observation

   The code computes `lrs = stats.norm.pdf(normals, 0, 1) / stats.norm.pdf(normals, mu, sigma)`, then `ests = lrs * (normals > gamma)`, then `lHat = ests.mean()`.

2. Audio
   Observation

   The narrator says the improved cross-entropy algorithm is complete and supplies a good importance sampling proposal distribution, after which they proceed with a normal importance sampling estimation and print the probability estimate L hat.

Using the fitted proposal density, the video estimates the rare-event probability by averaging likelihood ratios times the rare-event indicator over samples drawn from the proposal. This is the standard importance-sampling estimator specialized to the indicator event $X>\gamma$.

1. $f$ is the standard normal density.

2. $q$ is the fitted Normal proposal density.

3. Samples $Z_j$ are drawn from $q$, not from $f$.

4. The event indicator is $\mathbf{1}_{\{Z_j>\gamma\}}$.

1. Maximum likelihood fit of the Normal proposal to the $g^*$ samples
2. Problem setup for rare-event estimation

1. Formula
   Observation

   The code computes `oHat = ests.std()` and `widthCI = 1.96 * oHat / np.sqrt(R)`, then prints low and upper bounds as `lHat-widthCI` and `lHat+widthCI`.

1. The video does not verbally justify the use of 1.96 or state the normal approximation assumption behind the interval.

The notebook reports a symmetric interval around the estimate using 1.96 times the sample standard deviation of the weighted estimator divided by the square root of the number of proposal samples. The printed bounds are therefore $\hat{L}\pm$ `widthCI`.

1. Uses the sample standard deviation of `ests`.

2. Uses the same $R$ as the number of proposal samples in the final cell.

3. The interval is presented as a numerical summary; the video does not derive its coverage properties.

1. Normal importance-sampling estimator for $P(X>\gamma)$

1. Audio
   Observation

   The speaker introduces the original cross-entropy method as a way around the problem that direct rejection sampling would take too long.

2. Formula
   Observation

   Markdown heading reads `Cross-entropy method` and states `Use the cross-entropy method to estimate P(X > gamma) where X ~ Normal(0, 1) and gamma = 5`.

The video presents the original cross-entropy method as an adaptive Monte Carlo strategy for rare-event probability estimation. Instead of sampling directly from a target proposal distribution, it constructs a sequence of proposal distributions that improve iteratively until one is good enough for estimating $\mathbb{P}(X>\gamma)$.

1. Used when direct sampling from a good proposal distribution is impractical or too slow.

2. Applied here to estimate a tail probability for a normal random variable.

1. Audio
   Observation

   The speaker says the idea is to construct a sequence of proposal distributions which get better and better, and to stop when we get a proposal distribution which is good enough.

The cross-entropy method builds a sequence of proposal distributions rather than relying on one fixed proposal. Each iteration refines the parameters so the proposal becomes more effective for the rare-event region, and the process stops once the proposal is deemed sufficient.

1. Requires an update rule for proposal parameters.

2. Stopping criterion is based on whether the iteration threshold reaches the target rare-event level.

1. Purpose of the original cross-entropy method

1. Formula
   Observation

   Markdown states `Use the cross-entropy method to estimate P(X > gamma) where X ~ Normal(0, 1) and gamma = 5`.

2. Formula
   Observation

   Code sets `$u = (0, 1)$` and compares against `stats.norm.sf(gamma)`.

The worked example estimates the upper-tail probability $\mathbb{P}(X>5)$ for $X\sim\mathrm{Normal}(0,1)$. The original distribution is encoded by `$u=(0,1)$`, and the theoretical benchmark is computed with `stats.norm.sf(gamma)`.

1. Original distribution is standard normal.

2. Target event is exceedance of a fixed threshold $\gamma$.

1. Purpose of the original cross-entropy method

1. Audio
   Observation

   The speaker says once CE has finished, they take the proposal distribution it has found and run a normal important sampling estimation.

2. Formula
   Observation

   Second code cell samples `normals = rng.normal(v[0], v[1], R)` and computes `ests = lrs * (normals > gamma)`.

After the cross-entropy loop identifies a proposal distribution, the video performs a separate importance-sampling estimate from that proposal. Samples are drawn from the converged normal proposal, likelihood ratios relative to the original distribution are computed, and the indicator of the rare event is averaged with those weights.

1. Uses the final proposal parameters stored in `v` after the CE loop.

2. Requires computing likelihood ratios between original and proposal densities.

1. Iterative construction of proposal distributions
2. Normal tail-probability estimation example

1. Formula
   Observation

   Visible code computes `lrs`, then `ests = lrs * (normals > γ)`, then `fHat = ests.mean()` and `widthCI = 1.96 * oHat / np.sqrt(R)`.

2. Formula
   Observation

   Output prints `CE estimate`, `CE low bound`, `CE upp bound`, and `Theoretical`.

This clip shows a Monte Carlo implementation in which samples are drawn from a normal proposal, likelihood ratios between two normal densities are computed, and those ratios are multiplied by the indicator of the rare event `normals > γ`. The estimator is the sample mean of these weighted indicators, and an approximate confidence interval is built from the sample standard deviation divided by `sqrt(R)` and multiplied by `1.96`.

1. Samples are drawn from a normal proposal with parameters `v[0]`, `v[1]`.

2. Likelihood ratios use normal densities with parameters `u` and `v`.

3. The rare event is defined by the threshold `γ`.

4. `R` is the number of samples.

1. Audio
   Observation

   Speaker says, 'Let's visualize the sequence of proposal distributions that the CE method constructed.'

2. Formula
   Observation

   Code loops over `vs` and assigns `ys[:,i] = stats.norm.pdf(xs, v[0], v[1])`.

3. Diagram
   Observation

   A plot later displays multiple colored bell-shaped curves shifting rightward and narrowing.

The speaker explains that the cross-entropy method stores each parameter vector `v` in a list called `vs`. By looping through `vs` and evaluating `stats.norm.pdf(xs, v[0], v[1])` on a common grid `xs`, one can plot the entire sequence of proposal densities generated during the algorithm.

1. `vs` contains the stored proposal parameter vectors.

2. `xs` is a fixed grid of x-values.

1. Cross-entropy weighted estimator and confidence interval

1. Audio
   Observation

   The narrator says: `The improved cross entropy algorithm is now complete, and it has supplied us with a good importance sampling proposal distribution.`

1. The claim that the proposal is `good` is qualitative and not accompanied by a formal criterion in this clip.

After fitting $(\hat{\mu},\hat{\sigma})$ to the retained $g^*$ samples, the improved cross-entropy procedure has produced the importance-sampling proposal distribution used for estimation.

1. The rare-event model is $X\sim\mathrm{Normal}(0,1)$ and the target is $P(X>\gamma)$.

2. Samples from $g^*$ have been obtained by rejection sampling.

3. A Normal proposal has been fitted by maximum likelihood to those samples.

For the worked example in this notebook segment.

1. Formula
   Observation

   The output block prints `ICE estimate: 2.8499557494141556e-07 (+/- 8.28267698086911e-10)` and `Theoretical: 2.866515718791933e-07`.

2. Audio
   Observation

   The narrator says the rare event has probability two point eight by ten to the minus seven and the estimate has a confidence interval width in the order of ten to the minus ten.

1. The spoken `two point eight by ten to the minus seven` rounds the displayed value; the exact displayed estimate is visible on screen.

For this example, the importance-sampling estimate of the rare-event probability is about $2.85\times 10^{-7}$, with reported half-width about $8.28\times 10^{-10}$, and the theoretical benchmark is about $2.87\times 10^{-7}$.

1. $\gamma=5$.

2. The proposal was fitted as described in the notebook.

3. The final estimate uses $R=10^6$ proposal samples.

For the specific simulation shown in the output cells.

1. Audio
   Observation

   The speaker says that in the earlier example they kind of cheated because the rare event was not very rare, so they could sample from g star directly using rejection sampling, but in general this would take too long.

When the rare event is sufficiently rare, directly sampling from the ideal proposal distribution by rejection sampling is computationally impractical.

1. The target event is rare enough that direct acceptance from the ideal proposal is inefficient.

General practical claim stated verbally without formal proof.

1. Audio
   Observation

   The speaker says the threshold for this iteration is set to be the 95% threshold of the X samples, and if this is above the overall goal of gamma, they stop iterating.

2. Formula
   Observation

   Code shows `gamma_i = np.quantile(Xs, 1-p)` and `if gamma_i >= gamma: break` with `$p = 0.05$`.

In this implementation, the iteration stops when the empirical elite threshold $\gamma_i$ is at least the target threshold $\gamma$.

1. Samples `Xs` are drawn from the current proposal.

2. `$p = 0.05$`, so `$1-p = 0.95$`.

3. The target threshold is `gamma = 5`.

For each iteration $i$, if $\gamma_i\ge \gamma$, then break.

1. Audio
   Observation

   The speaker says they update the v parameters to be the maximum likelihood estimates of the elite samples, and must weight the samples by their likelihood ratios.

2. Formula
   Observation

   Code shows weighted averages for `mu_i` and `sigma_i` using `weights=eliteLRs`.

1. The spoken justification says maximum likelihood estimates, but the displayed variance formula centers on `eliteXs.mean()` rather than `mu_i`.

The next proposal parameters are obtained from the elite samples using likelihood-ratio weights, with the mean updated by a weighted average and the scale updated by a weighted standard-deviation-type expression.

1. Elite samples are those with values above $\gamma_i$.

2. Likelihood ratios are computed as original density divided by proposal density.

Applied at each cross-entropy iteration before updating `v`.

1. Audio
   Observation

   Speaker says, 'since in this very simple case we do know its normalizing constant l'.

2. Formula
   Observation

   Code sets `l = stats.norm.sf(γ)`.

For the target distribution plotted here, the normalizing constant is known and equals `l = stats.norm.sf(γ)`.

1. The example uses a standard normal baseline density.

2. The target is restricted to the tail region `$x > γ$`.

In this specific simple case.

1. Formula
   Observation

   The notebook text says `to sample from $g*(x) = P$($X = x$ | X > gamma), just sample lots of X's and extract those X > gamma`.

2. Audio
   Observation

   The narrator explains that because $g^*$ is the distribution of $X$ conditioned on the rare event happening, one can sample many $X$'s and keep only those exceeding the threshold.

1. Expression

   $$$$
   Explanation

   Start from the definition of the zero-variance density as the conditional law of $X$ given the rare event.

   Justification

   Notebook text and narration identify $g^*(x)=\mathbb{P}(X=x\mid X>\gamma)$.

   Shown in the video
2. Expression

   $$$$
   Explanation

   Draw a large batch of unconditioned standard-normal samples $X_i\sim\mathrm{Normal}(0,1)$.

   Justification

   This is implemented by `Xs = rng.normal(size=R)`.

   Shown in the video
3. Expression

   $$$$
   Explanation

   Retain only the samples satisfying $X_i>\gamma$.

   Justification

   This is implemented by `Xs = Xs[Xs > gamma]` and described verbally as keeping those which exceed the threshold.

   Shown in the video
4. Expression

   $$$$
   Explanation

   Treat the retained samples as samples from $g^*$.

   Justification

   By definition, conditioning a random variable on the event $X>\gamma$ yields exactly the distribution of accepted draws under this rejection rule.

   Derived from the video

Rejection sampling from the original standard normal law produces samples from the conditional density $g^*$ needed to fit the proposal.

1. Formula
   Observation

   The code first computes `mu = np.mean(Xs)` and `sigma = np.sqrt(np.mean((Xs-mu)**2))`, then samples `normals = rng.normal(mu, sigma, R)`, computes `lrs`, `ests`, `lHat`, `oHat`, and `widthCI`.

2. Audio
   Observation

   The narrator says the proposal density is created by maximum likelihood estimates for mu and sigma, then says they proceed with a normal importance sampling estimation and print the estimate and confidence intervals.

1. The video does not explicitly write the likelihood function being maximized; the MLE interpretation is inferred from the narration plus the sample-mean and sample-second-moment formulas.

1. Expression

   $$$$
   Explanation

   Use the retained $g^*$ samples to estimate the Normal proposal parameters by sample mean and sample root second central moment.

   Justification

   The code implements `mu = np.mean(Xs)` and `sigma = np.sqrt(np.mean((Xs-mu)**2))`; the narration calls these maximum likelihood estimates.

   Shown in the video
2. Expression

   $$$$
   Explanation

   Draw $R=10^6$ samples from the fitted Normal proposal $\mathrm{Normal}(\hat{\mu},\hat{\sigma}^2)$.

   Justification

   Implemented by `normals = rng.normal(mu, sigma, R)`.

   Shown in the video
3. Expression

   $$$$
   Explanation

   For each proposal sample, compute the likelihood ratio $f(Z_j)/q(Z_j)$ using the standard normal density in the numerator and the fitted normal density in the denominator.

   Justification

   Implemented by `lrs = stats.norm.pdf(normals, 0, 1) / stats.norm.pdf(normals, mu, sigma)`.

   Shown in the video
4. Expression

   $$$$
   Explanation

   Multiply each likelihood ratio by the indicator that the sample exceeds the threshold, forming `ests = lrs * (normals > gamma)`.

   Justification

   This is the importance-sampling integrand for the event probability $P(X>\gamma)$.

   Shown in the video
5. Expression

   $$$$
   Explanation

   Average `ests` to obtain `lHat`, and use its sample standard deviation together with `1.96 / sqrt(R)` to form the reported interval half-width.

   Justification

   Implemented by `lHat = ests.mean()`, `oHat = ests.std()`, and `widthCI = 1.96 * oHat / np.sqrt(R)`.

   Shown in the video

The fitted proposal is then used in a standard importance-sampling estimator, and the notebook reports both the point estimate and a symmetric confidence interval.

1. Audio
   Observation

   The speaker walks through the loop: sample from the current proposal, compute the iteration threshold, stop if it exceeds gamma, otherwise extract elite samples, compute likelihood ratios, and update v.

2. Formula
   Observation

   Code block shows the full loop from `for i in range(maxIter):` through `vs.append(v)`.

1. Expression

   $$X_s \sim \mathrm{Normal}(v[0], v[1]),\quad |X_s|=R$$
   Explanation

   At iteration $i$, draw a batch of $R$ samples from the current proposal distribution parameterized by `v`.

   Justification

   Observed in code as `Xs = rng.normal(v[0], v[1], R)` and described verbally as sampling from the current proposal distribution.

   Shown in the video
2. Expression

   $$\gamma_i = Q_{1-p}(X_s)$$
   Explanation

   Compute the iteration-specific threshold as the empirical $(1-p)$-quantile of the sampled batch.

   Justification

   Observed in code as `gamma_i = np.quantile(Xs, 1-p)`; the speaker identifies this as the 95% threshold because `$p = 0.05$`.

   Shown in the video
3. Expression

   $$\text{if } \gamma_i \ge \gamma,\ \text{stop}$$
   Explanation

   If the elite threshold has reached or exceeded the target rare-event level, terminate the adaptation loop.

   Justification

   Observed in code as `if gamma_i >= gamma: break` and stated verbally as the stopping rule.

   Shown in the video
4. Expression

   $$\text{eliteXs} = \{x\in X_s : x > \gamma_i\}$$
   Explanation

   Otherwise, select the elite samples, namely those current samples lying above the iteration threshold.

   Justification

   Observed in code as `eliteXs = Xs[Xs > gamma_i]` and described verbally as pulling out the elite Xs above gamma i.

   Shown in the video
5. Expression

   $$w(x)=\frac{f_u(x)}{f_v(x)}$$
   Explanation

   For each elite sample, compute the likelihood ratio between the original distribution and the current proposal distribution.

   Justification

   Observed in code as `eliteLRs = stats.norm.pdf(eliteXs, u[0], u[1]) / stats.norm.pdf(eliteXs, v[0], v[1])`; the speaker explicitly calls these likelihood ratios.

   Shown in the video
6. Expression

   $$\mu_i = \frac{\sum_{x\in \text{eliteXs}} w(x)x}{\sum_{x\in \text{eliteXs}} w(x)}$$
   Explanation

   Update the proposal mean as the weighted average of elite samples.

   Justification

   Observed in code as `mu_i = np.average(eliteXs, weights=eliteLRs)` and justified verbally as a maximum likelihood estimate from elite samples.

   Shown in the video
7. Expression

   $$\sigma_i = \sqrt{\frac{\sum_{x\in \text{eliteXs}} w(x)(x-\bar{x}_{\text{elite}})^2}{\sum_{x\in \text{eliteXs}} w(x)}}$$
   Explanation

   Update the proposal scale from a weighted second moment of the elite samples.

   Justification

   Observed in code as `sigma_i = np.sqrt(np.average((eliteXs-eliteXs.mean())**2, weights=eliteLRs))`.

   Shown in the video
8. Expression

   $$v \leftarrow (\mu_i,\sigma_i),\quad vs\leftarrow vs\cup\{v\}$$
   Explanation

   Replace the current proposal parameters by the updated pair and record the new parameter vector in the history list.

   Justification

   Observed in code as `v = (mu_i, sigma_i)` followed by `vs.append(v)`.

   Shown in the video

The displayed algorithm iteratively adapts a normal proposal toward the rare-event region by thresholding samples, weighting elite points by likelihood ratios, and updating the proposal parameters until the elite threshold reaches the target level.

1. Audio
   Observation

   The speaker says once CE has finished, they take the proposal distribution it has found and run a normal important sampling estimation.

2. Formula
   Observation

   Second code cell computes `normals`, `lrs`, `ests`, `fHat`, `oHat`, and `widthCI`, then prints them along with `stats.norm.sf(gamma)`.

1. Expression

   $$Y_j \sim \mathrm{Normal}(v[0], v[1]),\quad j=1,\dots,R$$
   Explanation

   After adaptation, draw a fresh sample batch from the final proposal distribution stored in `v`.

   Justification

   Observed in code as `normals = rng.normal(v[0], v[1], R)` and described verbally as running a normal important sampling estimation.

   Shown in the video
2. Expression

   $$\ell_j = \frac{f_u(Y_j)}{f_v(Y_j)}$$
   Explanation

   Compute likelihood ratios for the fresh samples under the original versus final proposal densities.

   Justification

   Observed in code as `lrs = stats.norm.pdf(normals, u[0], u[1]) / stats.norm.pdf(normals, v[0], v[1])`.

   Shown in the video
3. Expression

   $$Z_j = \ell_j\mathbf{1}_{\{Y_j>\gamma\}}$$
   Explanation

   Form the weighted rare-event contributions by multiplying each likelihood ratio by the indicator that the sample exceeds the target threshold.

   Justification

   Observed in code as `ests = lrs * (normals > gamma)`.

   Shown in the video
4. Expression

   $$\hat{p} = \frac{1}{R}\sum_{j=1}^{R} Z_j$$
   Explanation

   Estimate the rare-event probability as the sample mean of the weighted indicators.

   Justification

   Observed in code as `fHat = ests.mean()`.

   Shown in the video
5. Expression

   $$\widehat{\mathrm{SE}} = \frac{s_Z}{\sqrt{R}},\quad \text{widthCI}=1.96\,\widehat{\mathrm{SE}}$$
   Explanation

   Report an approximate 95% confidence half-width using the sample standard deviation of the weighted terms.

   Justification

   Observed in code as `oHat = ests.std()` and `widthCI = 1.96 * oHat / np.sqrt(R)`.

   Shown in the video
6. Expression

   $$p_{\text{theory}} = \mathbb{P}(X>\gamma)=\texttt{stats.norm.sf(gamma)}$$
   Explanation

   Compare the Monte Carlo estimate against the exact survival function of the standard normal distribution.

   Justification

   Observed in code as `print(f"Theoretical:\t{stats.norm.sf(gamma)}")`.

   Shown in the video

The final numerical estimate is produced by ordinary importance sampling from the converged proposal, with an approximate confidence interval and a direct comparison to the theoretical tail probability.

1. Formula
   Observation

   Code lines show sampling, likelihood-ratio computation, weighting by `(normals > γ)`, averaging, standard deviation, and CI width.

2. Formula
   Observation

   Output lines show numerical values for `CE estimate`, bounds, and `Theoretical`.

1. Expression

   $$normals = rng.normal(v[0], v[1], R)$$
   Explanation

   Draw `R` samples from the proposal normal distribution with mean `v[0]` and standard deviation `v[1]`.

   Justification

   Directly shown in the code cell.

   Shown in the video
2. Expression

   $$lrs = stats.norm.pdf(normals, u[0], u[1]) / stats.norm.pdf(normals, v[0], v[1])$$
   Explanation

   Compute the likelihood ratio between the normal density with parameters `u` and the proposal density with parameters `v` at each sampled point.

   Justification

   Directly shown in the code cell.

   Shown in the video
3. Expression

   $$ests = lrs * (normals > γ)$$
   Explanation

   Multiply each likelihood ratio by the indicator of the rare event `normals > γ`.

   Justification

   Directly shown in the code cell.

   Shown in the video
4. Expression

   $$fHat = ests.mean(); oHat = ests.std(); widthCI = 1.96 * oHat / np.sqrt(R)$$
   Explanation

   Take the sample mean as the probability estimate, the sample standard deviation for variability, and form an approximate 95% confidence half-width.

   Justification

   Directly shown in the code cell.

   Shown in the video
5. Expression

   $$CE estimate: 2.8433488092847927e-07 (+/- 1.1057152778688466e-08); Theoretical: 2.866515718791933e-07$$
   Explanation

   The printed output gives the numerical estimate, interval half-width, and theoretical comparison value.

   Justification

   Directly visible in the output block.

   Shown in the video

The visible code implements a likelihood-ratio-weighted Monte Carlo estimator and reports both the estimate and a theoretical comparison value.

1. Audio
   Observation

   Speaker says, 'If we loop through this list, we can calculate the PDF of each proposal distribution over some grid of x values.'

2. Formula
   Observation

   Code shows `xs = np.linspace(-2, 6.5, 500)`, `ys = np.empty((len(xs), len(vs)))`, and `ys[:,i] = stats.norm.pdf(xs, v[0], v[1])`.

1. Expression

   $$xs = np.linspace(-2, 6.5, 500)$$
   Explanation

   Create a fixed grid of 500 x-values spanning roughly -2 to 6.5.

   Justification

   Directly shown in the code cell.

   Shown in the video
2. Expression

   $$ys = np.empty((len(xs), len(vs)))$$
   Explanation

   Allocate a matrix to store one column of PDF values per proposal distribution.

   Justification

   Directly shown in the code cell.

   Shown in the video
3. Expression

   $$for i, v in enumerate(vs): ys[:,i] = stats.norm.pdf(xs, v[0], v[1])$$
   Explanation

   For each stored parameter vector `v`, evaluate its normal PDF on the same grid and store the result in column `i`.

   Justification

   Directly shown in the code cell and explained in the audio.

   Shown in the video
4. Expression

   $$plt.plot(xs, ys)$$
   Explanation

   Plot all stored columns against the common x-grid, producing multiple overlaid proposal curves.

   Justification

   Directly shown in the code cell.

   Shown in the video

The plot of proposal distributions is obtained by evaluating each stored normal density on a shared x-grid and drawing all curves together.

1. Formula
   Observation

   Code shows `xOverGamma = xs[xs > γ]`, `l = stats.norm.sf(γ)`, `gStar = stats.norm.pdf(xOverGamma) / l`, and `plt.plot(xOverGamma, gStar)`.

2. Audio
   Observation

   Speaker says they will plot the target distribution `g star` because its normalizing constant `l` is known.

1. Expression

   $$xOverGamma = xs[xs > γ]$$
   Explanation

   Restrict the plotting grid to the tail region where `$x > γ$`.

   Justification

   Directly shown in the code cell.

   Shown in the video
2. Expression

   $$l = stats.norm.sf(γ)$$
   Explanation

   Compute the normalizing constant as the standard normal survival function at `γ`.

   Justification

   Directly shown in the code cell and identified in the audio as the known normalizing constant.

   Shown in the video
3. Expression

   $$gStar = stats.norm.pdf(xOverGamma) / l$$
   Explanation

   Normalize the standard normal density on the tail region by dividing by `l`.

   Justification

   Directly shown in the code cell.

   Shown in the video
4. Expression

   $$plt.plot(xOverGamma, gStar)$$
   Explanation

   Plot the resulting normalized target density over the tail region.

   Justification

   Directly shown in the code cell.

   Shown in the video

The target curve shown in the figure is the standard normal density restricted to `$x > γ$` and normalized by `l = stats.norm.sf(γ)`.

1. Formula
   Observation

   The notebook states the full worked example: estimate `P(X > gamma)` where `X ~ Normal(0, 1)` and `gamma = 5`, using proposals of the form `Normal(mu, sigma^2)`.

2. Audio
   Observation

   The narrator introduces this as a very simple example demonstrating the improved cross-entropy method.

Estimate $P(X>\gamma)$ for $X\sim\mathrm{Normal}(0,1)$ with $\gamma=5$ using the improved cross-entropy method and Normal importance-sampling proposals.

1. $X\sim\mathrm{Normal}(0,1)$.

2. $\gamma=5$.

3. Proposal family is $\mathrm{Normal}(\mu,\sigma^2)$.

4. First rejection-sampling batch size is $R=5\times 10^8$.

5. Final importance-sampling batch size is $R=10^6$.

Obtain a numerical estimate of the rare-event probability and a confidence interval, and compare with the theoretical value.

1. Expression

   $$$$
   Explanation

   Set the threshold to $\gamma=5$.

   Justification

   Shown in the notebook cell `gamma = 5`.

   Shown in the video
2. Expression

   $$$$
   Explanation

   Generate $5\times 10^8$ standard-normal samples and keep only those greater than $5$.

   Justification

   Implemented by `Xs = rng.normal(size=R)` and `Xs = Xs[Xs > gamma]`; the narrator calls this rejection sampling.

   Shown in the video
3. Expression

   $$$$
   Explanation

   The retained sample count is 152.

   Justification

   Output line reads `Number of g* samples: 152`.

   Shown in the video
4. Expression

   $$$$
   Explanation

   Fit a Normal proposal to those 152 retained samples using their sample mean and sample root second central moment.

   Justification

   Implemented by `mu = np.mean(Xs)` and `sigma = np.sqrt(np.mean((Xs-mu)**2))`; narration identifies this as maximum likelihood estimation.

   Shown in the video
5. Expression

   $$$$
   Explanation

   Draw $10^6$ samples from the fitted Normal proposal.

   Justification

   Implemented by `$R = 10$**6` and `normals = rng.normal(mu, sigma, R)`.

   Shown in the video
6. Expression

   $$$$
   Explanation

   Compute likelihood ratios and weighted indicators, then average them to get the estimate.

   Justification

   Implemented by `lrs = stats.norm.pdf(normals, 0, 1) / stats.norm.pdf(normals, mu, sigma)`, `ests = lrs * (normals > gamma)`, and `lHat = ests.mean()`.

   Shown in the video
7. Expression

   $$$$
   Explanation

   Report the estimate, interval bounds, and theoretical benchmark.

   Justification

   Output lines show `ICE estimate`, `ICE low bound`, `ICE upp bound`, and `Theoretical`.

   Shown in the video

The notebook prints `ICE estimate: 2.8499557494141556e-07 (+/- 8.28267698086911e-10)`, `ICE low bound: 2.841672802433268e-07`, `ICE upp bound: 2.8582381563950423e-07`, and `Theoretical: 2.866515718791933e-07`.

The estimate is compared directly against the theoretical standard-normal survival probability printed in the same output block.

1. Formula
   Observation

   Markdown states the task: estimate `P(X > gamma)` where `X ~ Normal(0, 1)` and `gamma = 5`.

2. Formula
   Observation

   First code cell implements the cross-entropy loop with `$R = 10$**5`, `$p = 0.05$`, `maxIter = 50`, `$u = (0, 1)$`, and `$v = u$`.

3. Formula
   Observation

   Second code cell performs final importance sampling with `$R = 10$**6` and prints the results.

4. Audio
   Observation

   The speaker explains the loop, the stopping rule, the likelihood ratios, the parameter update, and the final importance-sampling estimate.

1. The exact intermediate proposal parameters after convergence are not shown numerically in the visible output within this clip.

2. The displayed variance update uses `eliteXs.mean()` rather than `mu_i`, creating a small mismatch with the verbal description of maximum likelihood estimation.

Use the cross-entropy method to estimate the rare-event probability $\mathbb{P}(X>\gamma)$ where $X\sim\mathrm{Normal}(0,1)$ and $\gamma=5$.

1. Original distribution parameters `$u = (0, 1)$`.

2. Initial proposal `$v = u$`.

3. Cross-entropy loop sample size `$R = 10$**5`.

4. Elite fraction `$p = 0.05$`.

5. Maximum iterations `maxIter = 50`.

6. Final importance-sampling sample size `$R = 10$**6`.

7. Target threshold `gamma = 5`.

Compute a Monte Carlo estimate of $\mathbb{P}(X>5)$, obtain an approximate confidence interval, and compare with the theoretical value.

1. Expression

   $$v_0 \leftarrow u=(0,1)$$
   Explanation

   Initialize the proposal distribution to the original standard normal distribution.

   Justification

   Observed in code as `$v = u$` after `$u = (0, 1)$`.

   Shown in the video
2. Expression

   $$\text{repeat for } i=0,\dots,49$$
   Explanation

   Run up to 50 adaptive iterations.

   Justification

   Observed in code as `for i in range(maxIter):` with `maxIter = 50`.

   Shown in the video
3. Expression

   $$X_s \sim \mathrm{Normal}(v[0],v[1]),\ |X_s|=10^5$$
   Explanation

   Draw 100,000 samples from the current proposal at each iteration.

   Justification

   Observed in code as `Xs = rng.normal(v[0], v[1], R)` with `$R = 10$**5`.

   Shown in the video
4. Expression

   $$\gamma_i = Q_{0.95}(X_s)$$
   Explanation

   Set the elite cutoff to the empirical 95th percentile of the current sample batch.

   Justification

   Observed in code as `gamma_i = np.quantile(Xs, 1-p)` with `$p = 0.05$`; the speaker calls this the 95% threshold.

   Shown in the video
5. Expression

   $$\text{if }\gamma_i\ge 5,\ ext{break}$$
   Explanation

   Stop adapting once the elite cutoff reaches the target threshold.

   Justification

   Observed in code as `if gamma_i >= gamma: break`.

   Shown in the video
6. Expression

   $$\text{eliteXs}=\{x\in X_s:x>\gamma_i\}$$
   Explanation

   Keep only the elite samples above the iteration cutoff.

   Justification

   Observed in code as `eliteXs = Xs[Xs > gamma_i]`.

   Shown in the video
7. Expression

   $$w(x)=\frac{\phi(x;0,1)}{\phi(x;v[0],v[1])}$$
   Explanation

   Compute likelihood ratios between the original standard normal density and the current proposal density on the elite samples.

   Justification

   Observed in code as `eliteLRs = stats.norm.pdf(eliteXs, u[0], u[1]) / stats.norm.pdf(eliteXs, v[0], v[1])`.

   Shown in the video
8. Expression

   $$v \leftarrow (\mu_i,\sigma_i)$$
   Explanation

   Update the proposal parameters from weighted elite-sample summaries and store the new pair in the history list.

   Justification

   Observed in code as `mu_i = np.average(...)`, `sigma_i = np.sqrt(np.average(...))`, `v = (mu_i, sigma_i)`, and `vs.append(v)`.

   Shown in the video
9. Expression

   $$Y_j \sim \mathrm{Normal}(v[0],v[1]),\ j=1,\dots,10^6$$
   Explanation

   After convergence, draw one million fresh samples from the final proposal distribution.

   Justification

   Observed in the second code cell as `normals = rng.normal(v[0], v[1], R)` with `$R = 10$**6`.

   Shown in the video
10. Expression

    $$\hat{p}=\frac{1}{10^6}\sum_{j=1}^{10^6}\frac{\phi(Y_j;0,1)}{\phi(Y_j;v[0],v[1])}\mathbf{1}_{\{Y_j>5\}}$$
    Explanation

    Estimate the tail probability by averaging likelihood-ratio-weighted rare-event indicators.

    Justification

    Observed in code as `lrs = ...`, `ests = lrs * (normals > gamma)`, and `fHat = ests.mean()`.

    Shown in the video
11. Expression

    $$\text{widthCI}=1.96\frac{s}{\sqrt{10^6}}$$
    Explanation

    Report an approximate 95% confidence half-width from the sample standard deviation of the weighted terms.

    Justification

    Observed in code as `oHat = ests.std()` and `widthCI = 1.96 * oHat / np.sqrt(R)`.

    Shown in the video

The visible printed result is `CE estimate: 2.8433488092847927e-07 (+/- 1.1057152778688466e-08)`, with bounds `2.732772014979008e-07` and `2.9539203370716776e-07`, compared to `Theoretical: 2.866515718791933e-07`.

The example is checked against the exact standard-normal survival probability `stats.norm.sf(5)`, which is printed as `2.866515718791933e-07`; the speaker also remarks that the estimate is about `2.8 by 10 to the minus 7` but the confidence interval width is much wider.

1. Formula
   Observation

   Output block shows `CE estimate: 2.8433488092847927e-07 (+/- 1.1057152778688466e-08)`, `CE low bound: 2.732772014979008e-07`, `CE upp bound: 2.953920337016776e-07`, and `Theoretical: 2.866515718791933e-07`.

2. Formula
   Observation

   Code above computes these quantities from `normals`, `lrs`, and `ests`.

Estimate the rare-event probability using the displayed cross-entropy/importance-sampling style code and compare it with the theoretical value.

1. `$R = 10$**6`

2. Proposal samples drawn from `rng.normal(v[0], v[1], R)`

3. Likelihood ratio uses `stats.norm.pdf(normals, u[0], u[1]) / stats.norm.pdf(normals, v[0], v[1])`

4. Rare-event indicator is `(normals > γ)`

Obtain the CE estimate, confidence bounds, and theoretical comparison.