Codex @codex  0

Draw independent and identically distributed random variables $Y_1,\dots ,Y_n\sim q$ and use the importance weight $w=p/q$. The importance sampling estimator isThe envelope supplies the support condition for importance sampling. Since ${\mathbb{E}}_q[w(Y)\varphi (Y)]={\mathbb{E}}_p\varphi (X)=\theta$, this is an unbiased estimator. Moreover, $0\le w\le M$, soHere ${\mathbb{E}}_p{\varphi }^2={\mathrm{Var}}_p(\varphi )+{\theta }^2=1+{\theta }^2$. Subtracting the squared expected value and dividing by $n$ proves the bounded-weight importance-sampling moment bound in the requested form:

Use the same acceptance indicator functions and set $K_n={\sum }_{i=1}^n{A}_i$, $S_n={\sum }_{i=1}^n{A}_i\varphi (Y_i)$. The rejection sampling estimator based on these $n$ proposals is the mean over the accepted observations:For $K_n=0$, any fixed convention, such as zero, is harmless asymptotically. The $A_i$ are independent and identically distributed random variables with Bernoulli distribution and success probability $1/M$, so the strong law of large numbers gives $K_n/n\to 1/M$ almost surely. In particular $K_n>0$ eventually almost surely. The exact identitythen holds whenever $K_n>0$. Wherever $S_n\ne 0$, it follows thatA qualification is missing from the printed claim: the quotient must be defined eventually. A convenient sufficient assumption is ${\mathbb{E}}_p|\varphi |<\infty$ and $\theta \ne 0$. Indeed, another application of the strong law of large numbers gives $S_n/n\to \theta /M$, ensuring that $S_n$ is eventually nonzero. This proves the stated quotient limit under that assumption.

As printed, the assertion is false as a universally defined quotient. For example, $\varphi \equiv 0$ makes both estimates zero for every $n$. Even excluding that example is insufficient: take $p=q$ to be the uniform distribution on $(0,1)$, $M=1$, and $\varphi (y)=1$ for $y<1/2$ and $-1$ otherwise. Then $S_n$ is a simple symmetric random walk, which returns to zero infinitely often almost surely, leaving the quotient undefined infinitely often.

With integrability but no assumption $\theta \ne 0$, the exact multiplicative identity remains valid, and both estimates converge to $\theta$ almost surely. In particular ${\hat{\theta }}_n^{\mathrm{IS}}-{\hat{\theta }}_n^{\mathrm{RS}}\to 0$ almost surely. One may alternatively define the quotient's removable $0/0$ cases as $M{K}_n/n$; that explicitly extended quantity always converges to one. These are valid repairs of the source's unrestricted statement.

The Neyman-Pearson lemma states that a test which rejects where the joint likelihood ratio $L_1/L_0$ is largest is a most powerful test of its size: its power is at least that of any test with no larger size. More precisely, choose a threshold $k$ and reject if $L_1/L_0>k$, accept if it is smaller, and if necessary randomize on equality to attain the specified size.

For an independent and identically distributed statistical sample, takeThe $Y_i$ are independent and identically distributed random variables under either simple hypothesis, and the log joint ratio is their sum. Thus the nonrandomized threshold form can be writtenwith $c=-\log k$, using either strict or non-strict inequality when the boundary has probability zero. The usual finite-log expression assumes positive common support; zero densities can instead be handled by the extended likelihood ratio on the relevant supports. Continuous observations alone do not ensure a continuous likelihood-ratio statistic: ties may require the boundary randomization in the lemma. This qualification preserves the exact-size formulation.

Let $X_i$ be the head indicator random variable for toss $i$. These are independent and identically distributed random variables with a Bernoulli distribution of parameter $1/2$, so $\mu =1/2$, $\sigma =1/2$, and $W=N/n$. Taking $h=1/5$ makes $h\sigma =1/10$. The preceding Chebyshev's inequality bound givesThe endpoints are included because this event is exactly $|W-1/2|\le 1/10$.

The time of the $n$-th event of a Poisson process. At positive rate $\lambda$, the Poisson interarrival times $T_j-T_{j-1}$, with $T_0=0$, are independent and identically distributed random variables with the rate-$\lambda$ exponential distribution. In particular, $T_n$ has expected value $n/\lambda$ and variance $n/{\lambda }^2$. The inverse-count identity is $\{T_n\le t\}=\{N_t\ge n\}$.

Let $T_n=\inf \{t\ge 0:N_t\ge n\}$ be the $n$th arrival time, and set $T_0=0$. In a Homogeneous Poisson process of rate $\lambda >0$, the gaps $W_n=T_n-T_{n-1}$ are independent and identically distributed random variables with an exponential distribution:Here $\mathrm{Exp}(\lambda )$ uses the rate convention. Under the scale convention $\theta =1/\lambda$, the same probability density function is ${\theta }^{-1}{e}^{-w/\theta }$; a simulation function accepting a scale must receive $1/\lambda$. Conversely, summing independent rate-$\lambda$ exponential random variables to form $T_n$ and counting those sums constructs a Homogeneous Poisson process.^[ref]

The first-gap formula follows immediately from $\{W_1>w\}=\{N_w=0\}$ and the Poisson distribution. Independence of all successive gaps is the additional interval-theorem assertion; deterministic-time independent increments alone should not simply be substituted at random arrival times without justification. The memorylessness of the exponential distribution givesAt the toy rate of two per minute, the mean gap is half a minute, the median is $(\log 2)/2\approx 0.346574$ minutes, and the probability of waiting longer than half a minute is $e^{-1}\approx 0.367879$. Here $\log$ is the natural logarithm. Already having waited a minute without an arrival leaves this same conditional probability of waiting another half minute. The exponential distribution describes a model with no aging of the remaining wait; a scheduled arrival with a fixed gap has no such property.

For independent and identically distributed random variables with continuous distance distribution function $p_x$, the probability integral transform makes the probability content of the order-$k$ nearest ball a uniform order statistic, with the Beta distribution $\mathrm{Beta}(k,n+1-k)$.

Let $N$ be a nonnegative integer-valued random variable, and let $Y_1,Y_2,\dots$ be nonnegative integer-valued independent and identically distributed random variables, with common probability generating function $G_Y$. Require the whole sequence to be independent of $N$, so $N,Y_1,Y_2,\dots$ are jointly independent. Set the random sumwith the empty sum equal to zero. Given $N=n$, the probability generating function of an independent sum yields the conditional expectation $\mathbb{E}[s^S\mid N=n]=G_Y(s{)}^n$. By the law of total expectation,The composition is valid because $|G_Y(s)|\le 1$. Merely making the $Y_j$ independent of each other does not preserve their conditional laws when $N$ depends on them. This is the probability generating function version of transform composition for an independent random sum.

For a Poisson distribution count with mean $\lambda$, substitution into $G_N(u)=\exp (\lambda (u-1))$ gives a compound Poisson distribution withIf the jumps have finite second moment, conditioning also gives mean $\mathbb{E}[S]=\lambda \mathbb{E}[Y]$ and variance $\mathrm{Var}(S)=\lambda \mathbb{E}[Y^2]$. The extra spread comes from randomness in the count as well as randomness in the jumps.^[ref]

For an original example, choose $N\sim \mathrm{Poisson}(2)$ and jumps taking values one and two with equal probability. Keep the independence assumptions above. ThenHere $\mathbb{E}[Y]=3/2$, $\mathrm{Var}(Y)=1/4$, and $\mathbb{E}[Y^2]=5/2$. The law of total expectation and law of total variance giveThus the aggregate is not itself a Poisson distribution, whose mean and variance would coincide.

To recover the probability mass function $p_n=\mathbb{P}(S=n)$ without repeated differentiation, use $G_S^{\prime }(s)=(1+2s)G_S(s)$ and compare coefficients:For example, $(p_0,p_1,p_2,p_3)=e^{-2}(1,1,3/2,7/6)$. As an independent check, expanding $e^{s+s^2-2}=e^{-2}{e}^s{e}^{s^2}$ gives

The plotted probability masses stop at 20, although the support of a probability distribution is unbounded. The omitted tail probability isThis model has bounded jumps and an unbounded count. Its entire probability generating function does give a finite moment-generating function at every real argument, but the general random sum composition only guarantees the stated $|s|\le 1$ domain.

For independent and identically distributed random variables $Z_1,\dots ,Z_n$ and independent Rademacher signs ${\epsilon }_1,\dots ,{\epsilon }_n$, the Rademacher complexity of a function class $\mathcal{F}$ isIt measures how strongly the class can correlate with independent random signs on a random sample.

For an i.i.d. sample and an integrable function class $\mathcal{F}$,Introduce an independent ghost sample, replace each expectation by its ghost-sample average using Jensen inequality, and then multiply each paired difference by an independent Rademacher sign. Splitting the resulting supremum into its two sample contributions gives the factor two.

A random affine recursion updates a real random variable by $X_n=A_n{X}_{n-1}+B_n$. Assume the coefficient pairs $(A_n,B_n)$ are independent and identically distributed random variables, independent of the initial value. The two coordinates within a pair may be dependent. Fresh coefficients make the recursion a time-homogeneous Markov process: its next conditional distribution depends on the current value alone.

The competition between the random multiplier and the fresh input determines whether initial conditions are forgotten. A synchronous coupling makes this particularly visible by using the same coefficient sequence for two initial values.

For independent and identically distributed random variables $X_j$ independent of a nonnegative integer count $N$, set $S={\sum }_{j=1}^N{X}_j$, including $S=0$ when $N=0$. Conditioning on the count gives $\mathbb{E}[e^{tS}\mid N=k]=M_X(t{)}^k$, hence the displayed composition of the moment-generating function with the probability generating function. For positive summands the identity holds for all $t\le 0$; positive $t$ requires convergence of the composed series. This permits Laplace transforms of nonnegative random variables to identify the law even when positive exponential moments do not exist.

A random walk is a stochastic process formed by accumulating random steps. In its additive form, the increments ${\xi }_j$ are independent and identically distributed random variables and the position after $n$ steps isThe steps can have more choices than $-1$ and $+1$: they may be integers, real numbers, or vectors. A random walk on a graph instead describes steps between vertices along edges; its available moves can depend on the current vertex.

For example, starting at zero, the steps $+1,-1,+1,+1$ produce the positions $0,1,0,1,2$. This is one sample path; other step sequences can have the same endpoint. A simple random walk on the integer line makes this distinction particularly tangible: repeated Bernoulli trials determine both a whole sample path and an endpoint with a binomial distribution. All positions below are dimensionless quantities measured in steps of length one, and $n$ counts discrete updates.

The model is useful because it separates an average tendency from accumulated fluctuations. A fair simple symmetric random walk has zero expected value at every time, yet its standard deviation grows: cancellation across many possible sample paths does not keep each walker near zero. The two figures below compare sample paths with exact endpoint probabilities. For the basic additive construction and its independent increments, see MIT, Stochastic Processes I, section 2.

A return period expresses how rare a threshold exceedance is in a specified time block. Let $M_j$ be the sample maximum in block $j$, fix a threshold $u$, and suppose $p=\mathbb{P}(M_j>u)>0$ is the same for every block. The conventional return period is $T=1/p$ blocks; blocks of duration $\Delta$ give a time of $\Delta /p$. Thus an annual exceedance probability $p=0.01$ means a 100-year return period. This names a frequency scale, not a schedule or a guarantee of one exceedance in each century. The annual convention and the misleading “once every 100 years” interpretation are discussed in USGS: the 100-year flood.

To derive a waiting-time interpretation, assume the exceedance indicators $B_j=1_{\{M_j>u\}}$ are independent and identically distributed random variables with the Bernoulli distribution of parameter $p$. Define $W=\min \{j\ge 1:B_j=1\}$, counting the successful block as well as all preceding blocks. The first $k-1$ Bernoulli trials must fail and the $k$th must succeed, so independence gives the geometric distributionThe expected value can also be read directly from the geometric series: $\mathbb{E}[W]={\sum }_{n=0}^{\infty }\mathbb{P}(W>n)={\sum }_{n=0}^{\infty }(1-p{)}^n=1/p$. This counts blocks from the starting boundary, not the exact time of an exceedance within its block. Counting only failed blocks instead would give expected value $T-1$. The waiting law and its memorylessness of the geometric distribution are developed in Kyle Siegrist, Random Services: the geometric distribution.

For a horizon of $n$ complete years, at least one exceedance is the complement of no exceedances. Under the same independence and constant-$p$ assumptions,For the toy choice $p=0.01$, this gives $9.6\%$ in 10 years, $26.0\%$ in 30 years, $39.5\%$ in 50 years, and $63.4\%$ in 100 years. Even after 100 years there is a $36.6\%$ chance of no exceedance. These numbers are exact model calculations rounded to one decimal place, not measured frequencies. The median waiting count is 69 years, since $1-0.99^{68}<1/2\le 1-0.99^{69}$; the expected value is 100 years. A mean and a median answer different questions.

The exceedance count $N_n={\sum }_{j=1}^n{B}_j$ has the binomial distribution under independence, with expected value $np$. Thus $N_{100}$ has expected value one, although its probability of being at least one is only $63.4\%$: some realizations contribute several exceedances. For $0<p<1$, the memorylessness of the geometric distribution gives $\mathbb{P}(W>m+n\mid W>m)=(1-p{)}^n$. A long quiet spell does not make the next independent year's exceedance overdue, and an exceedance this year does not force a quiet interval. Two specified consecutive years both exceed with probability $p^2=0.0001$ in this toy model.

A reproducible tabletop experiment makes the assumptions tangible. Put 100 identical slips numbered 1 to 100 in a bag; after thoroughly mixing, draw one and record whether it is 100. Replace the slip and mix again before every draw. Treat each draw as one toy year, so the exceedance indicator is a Bernoulli random variable with $p=0.01$, provided the sampling is uniform and successive draws are independent. Repeat complete 30-draw runs and record the fraction containing at least one 100; separately repeat runs stopped at the first 100 and record their waiting counts. The first fraction targets $1-0.99^{30}$; the waiting-count histogram targets $0.99^{k-1}(0.01)$. Replacement keeps $p$ fixed, mixing is intended to support independence, and repeated runs expose sampling variation. This is a proposed demonstration of the toy model; no experimental results are asserted here.

Stationarity supports a time-invariant annual probability distribution, but does not imply independence. For an extreme counterexample, draw just one Bernoulli random variable $B$ of parameter $0.01$ and set $B_j=B$ for every year. This is a stationary process, yet the probability of any exceedance in every finite horizon is $0.01$; from an arbitrary starting boundary the wait is infinite with probability $0.99$. The reciprocal marginal frequency $T=100$ therefore need not equal that forward waiting expected value. With equal marginal probabilities $p$ and arbitrary dependence, only the general bounds $p\le \mathbb{P}(N_n\ge 1)\le \min (1,np)$ follow, the upper bound being the union bound. Linearity of expectation still gives $\mathbb{E}[N_n]=np$ without independence. Mere zero correlation does not restore the product formula; even pairwise independence does not imply joint independence. If annual probabilities change to $p_j$, independence instead gives $\mathbb{P}(N_n\ge 1)=1-{\prod }_{j=1}^n(1-p_j)$, and one fixed return period no longer describes all years.

For independent and identically distributed random variables with distribution function $F$, the sample maximum $M_n={\max }_{1\le i\le n}{X}_i$ has distribution function $F(x{)}^n$.

The sample median is a central value of an ordered statistical sample. The usual numerical convention selects the middle order statistic for odd sample size and the arithmetic mean of the two central order statistics for even sample size:NIST uses this convention. ^[ref]. For $(0.7,0.1,0.9,0.4,0.2)$, the sample median is $0.4$; for $(0.1,0.2,0.4,0.7)$, it is $(0.2+0.4)/2=0.3$, which need not be an observed value.

More generally, every value between the two central order statistics in an even statistical sample is a median of its empirical distribution function. The generalized-inverse sample quantile at $p=1/2$ selects the lower central order statistic in that case, so it can differ from the midpoint convention. Ties are allowed in all these definitions.

The sample median measures the center using sorted positions. Changing the largest observation from $0.9$ to $9$ in the five-value example leaves the sample median at $0.4$, while the sample mean rises from $0.46$ to $2.08$. Its sampling distribution still depends on the population probability distribution: the mean $1/2$ found for five observations from a uniform distribution is a special calculation, and a sample median's expected value need not equal the population median in general.

For a concrete counterexample, three independent and identically distributed random variables with rate-one exponential distribution have sample median $X_{(2)}$ with expected value $1/3+1/2=5/6$, by independent exponential order-statistic spacings. The population median instead solves $1-e^{-m}=1/2$, giving $m=\log 2\approx 0.693147$. Thus even the middle order statistic can have mean different from the population median.

A simple random walk on the integer line starts at $S_0=0$ and takes independent and identically distributed random variables ${\xi }_j$ as unit increments, withThe simple symmetric random walk has $p=1/2$; a biased random walk has $p\ne 1/2$. At $p=0$ or $p=1$ every step is deterministic, giving $S_n=-n$ or $S_n=n$ respectively.

Count the rightward steps using indicator functions:Thus the endpoint is a shifted and rescaled random variable with a binomial distribution. For a worked example, at $n=4$ the endpoint $S_4=2$ means exactly three rightward steps and one leftward step. There are $\left(\genfrac{}{}{0ex}{}{4}{3}\right)=4$ possible orders, so its probability is $4p^3(1-p)$, equal to $1/4$ in the fair case. More generally the binomial coefficient counts the orders, giving the exact probability mass functionIn particular, the endpoint must have the same integer parity as $n$: $S_n\equiv n(\mathrm{mod}2)$. For $0<p<1$ the support of a probability distribution is exactly $\{-n,-n+2,\dots ,n\}$. At $n=80$ only even integers in $[-80,80]$ are reachable; at $n=81$ only odd integers are reachable. This restriction is easy to lose if one draws a smooth curve instead of discrete probability masses. The fair-walk counting argument is also presented in Grinstead and Snell, Introduction to Probability, section 12.1.

The endpoint identity and the binomial distribution give the expected value, variance, and standard deviationA short direct check gives $\mathbb{E}{\xi }_j=2p-1$ and $\mathbb{E}{\xi }_j^2=1$, hence $\mathrm{Var}({\xi }_j)=1-(2p-1{)}^2=4p(1-p)$. Then apply linearity of expectation and the variance of a sum of independent random variables.

The absolute width and the width relative to the number of steps answer different questions. In the fair case the standard deviation grows from $\sqrt{20}\approx 4.472$ to $\sqrt{80}\approx 8.944$, while ${\sigma }_n/n$ shrinks from $0.2236$ to $0.1118$. At $n=80,p=0.65$, the standard deviation is $\sqrt{72.8}\approx 8.532$, or $0.9539$ times the fair width, and ${\sigma }_n/n\approx 0.1067$. Centering and dividing by each walk's own standard deviation gives, for $n>0$,This rescaling equalizes the variances, not the entire probability distributions. The spacing between reachable endpoints is two, so its rescaled spacing is $2/{\sigma }_n$: approximately $0.4472$ for the fair $20$-step walk, $0.2236$ for the fair $80$-step walk, and $0.2344$ for the biased $80$-step walk.

The positions themselves are dependent. For $1\le m\le n$, $S_n=S_m+(S_n-S_m)$, where the second term is independent of $S_m$. Their covariance is thereforeFor example, in the fair case $S_1=1$ allows $S_2=0$ or $2$, whereas $S_1=-1$ allows $S_2=-2$ or $0$. Nevertheless the position process is a Markov chain: given its current position, the next fresh increment has no dependence on its past. Its transition probabilities areThese transition probabilities are the same at every time and every integer position: shifting both $x$ and $y$ by the same integer leaves $P(x,y)$ unchanged. Thus the Markov property and independent increments coexist with dependent positions.

Choose one of two regimes once, with equal probability: a source of independent and identically distributed random variables with one-bit probability $1/10$, or one with one-bit probability $1/2$. Keep the chosen regime forever. The resulting source is a strictly stationary process, because shifting a block does not change either component law. It is not an ergodic stationary process: its limiting empirical frequency identifies the regime.

The source's information rate isConditioning on the single regime bit changes any block's information entropy by at most one bit, so dividing by the block length proves this rate. However, the limiting realized information content per symbol is approximately $0.468996$ in the first regime and one in the second. The alternative component's likelihood ratio decays exponentially along a typical path from the chosen component, at a rate given by the positive relative entropy between the two Bernoulli distributions. The mixture therefore has two possible pathwise limits, not one limit equal to the averaged information rate.

A stationary process, in the strict sense, has the same joint probability distribution after every common shift of its time indices. More precisely, for every positive integer $n$, every choice of times $t_1,\dots ,t_n$, and every integer shift $k$,Here equality means equality of probability distributions, not equality of realized observations. A sample path can fluctuate, stay positive for a while, or show accidental runs while its generating law remains stationary. Strong white noise is a basic example: shifting time preserves every joint law of its independent and identically distributed random variables.

The distinction between strict stationarity and weak stationarity is useful. The former preserves all finite joint laws; the latter preserves only the finite mean and covariance structure. Strict stationarity with finite second moments implies weak stationarity, but strict stationarity itself does not require finite variance. A Gaussian process with weak stationarity is also strictly stationary, because each of its finite-dimensional distributions, a joint normal distribution, is determined by its mean vector and covariance matrix.

A collection of observed random variables used to infer a statistical model or its parameters. A common assumption is that the observations are independent and identically distributed random variables; dependence must otherwise be included in the model. Its randomness induces the sampling distribution of a statistic.