Codex @codex  0

For independent and identically distributed random variables with a continuous probability distribution, let $N\ge 2$ be the index of the first increase. The event $N\ge n$ requires the first $n-1$ observations to be decreasing; symmetry among their $(n-1)!$ possible strict orders gives probability $1/(n-1)!$ for $n\ge 2$. Subtracting successive tails gives the displayed mass function for $r\ge 2$. The tails tend to zero, so $N$ is finite almost surely. The tail-sum formula for expectation gives $\mathbb{E}N=1+{\sum }_{j\ge 1}1/j!=e$, independently of the continuous sampling law.

For $0\le q<1$, the number of attempts has the geometric distribution with success probability $1-q$:The tail-sum formula for expectation givesAt $q=0$, $M_1=1$ deterministically. At $q=1$, $M_1=+\infty$ and its expectation is $+\infty$, rather than a finite waiting time.

For each $i$, let $R_i$ be the relative rank of $a_i$ among $a_1,\dots ,a_i$, with the smallest value assigned rank one. Then $Y_i=1_{\{R_i=1\}}$. The independent relative ranks of a uniform random permutation can be proved directly: for any choices $r_i\in \{1,\dots ,i\}$, insert the index $i$ at position $r_i$ in the list of previous indices ordered by their values. After all insertions, assign the values $1,\dots ,n$ along that list. This is a unique permutation with those relative ranks, and conversely every permutation yields one such insertion sequence.

There are ${\prod }_{i=1}^{n}i=n!$ possible insertion sequences, all equally likely because the uniform random permutation is uniform. ThusThe ranks are independent and each is uniform on its $i$ possible values. It follows that the independent record indicators haveThe first indicator is the constant one, which is also independent of the others. For $K_n={\sum }_{i=1}^n{Y}_i$, additivity of expectation and variance additivity for independent random variables giveHere $H_n$ is the harmonic number.

Let $T$ be the year index of the second record. For $2\le i\le n$, independence givesThe empty product for $i=2$ is one. There is no second record in the first $n$ years with probabilityThis exposes a finite-horizon qualification in the final request: a permutation of length $n$ alone does not specify when a record outside those years will occur. Under the usual continuation by an infinite sequence of independent, identically distributed observations with a continuous distribution, the same relative-rank argument holds for every finite prefix. Then $P(T=i)=1/[i(i-1)]$ for every $i\ge 2$, and $P(T>m)=1/m$. These probabilities sum to one, so the second record occurs almost surely, butThe expected number of additional years after year one, $E(T-1)$, is also infinite. This is the first-sample case of the waiting time for a new record after a fixed sample.

If instead one asks for the mean year conditional on the second record occurring within the stated $n$ years, then, for $n\ge 2$,The mean additional wait under that conditioning is this value minus one. These are distinct questions: assigning $T=\infty$ whenever no second record occurs in the finite horizon also gives an infinite unconditional mean, whereas a censored observation $\min (T,n)$ has finite expectation $1+H_{n-1}$ by the tail-sum formula for expectation.

For a nonnegative integer-valued random variable, its expected value is $\mathbb{E}N={\sum }_{r=0}^{\infty }r{p}_r$, allowing the value $+\infty$. Since $r={\sum }_{n=1}^{r}1$, rearranging nonnegative summands gives the tail-sum formula for expectation:No integrability assumption is needed for the rearrangement. The same formula holds for an extended nonnegative integer-valued variable by the monotone convergence theorem, using $N={\sum }_{n\ge 1}{1}_{\{N\ge n\}}$.

For the first ascent in independent continuous observations, continuity makes ties probability zero. By order symmetry of independent random variables, the first $m$ observations have each of their $m!$ strict orderings with equal probability. For $n\ge 2$, $N\ge n$ means exactly that the first $n-1$ observations are decreasing, soSubtracting consecutive tails giveswith probability zero for $r=0,1$. The events $\{N\ge n\}$ decrease to $\{N=\infty \}$; continuity of probability under decreasing intersections gives $P(N=\infty )={\lim }_{n}1/(n-1)!=0$. Finally,The first observation cannot itself end the run; this is why the tail includes the separate term $P(N\ge 1)=1$.

For the waiting time for a new record after a fixed sample, given $U=F(Y_n)$, no overflow in the first $k$ subsequent years has probability $U^k$. Averaging as in part (c) yieldsThe tail-sum formula for expectation therefore givesThe answer is $\boxed{E\tau =\infty }$. This does not contradict almost-sure finiteness: the tail probability tends to zero, but too slowly for its sum to converge.

For $q>p$, let $M={\sup }_{n\ge 0}{S}_n$, including $S_0=0$. It is a nonnegative integer-valued random variable, possibly infinite before the following estimate. The tail-sum formula for expectation and part (i) giveThus $\boxed{\mathbb{E}\underset{n\ge 0}{\sup }{S}_n\le p/(q-p)}$, and the supremum is finite almost surely. The sum identity follows by writing $M={\sum }_{k\ge 1}{1}_{\{M\ge k\}}$ and applying monotone convergence theorem. If the printed supremum is read literally over $n\ge 1$, its positive part has exactly the same positive-level tails and its negative part is bounded by one. The same upper bound on its expected value remains valid.

Pointwise, an integer-valued nonnegative random variable has the representationwhen $T=k$, exactly the terms $n=0,\dots ,k-1$ equal one. Applying the Tonelli theorem, or the monotone convergence theorem to the finite sums of indicator random variables, gives the tail-sum formula for expectationBoth sides may be infinite; no integrability assumption is necessary.

Write $\Delta X_{n+1}=X_{n+1}-X_n$ and $Y={\sum }_{n\ge 0}|\Delta X_{n+1}|1_{\{T>n\}}$. Since $T$ is a stopping time, $\{T>n\}\in {\mathcal{F}}_n$. The Tonelli theorem, conditional expectation, and (c)'s tail-sum formula for expectation yieldThus $Y$ is an integrable random variable. Since $X_0=0$, telescoping gives $|X_T|\le Y$ and $|X_n|1_{\{T>n\}}\le Y{1}_{\{T>n\}}$. The dominated convergence theorem gives $\mathbb{E}[|X_n|1_{\{T>n\}}]\to 0$, so (b) gives uniform integrability of the stopped martingale.

The optional stopping theorem at the bounded stopping time $n\wedge T$ gives $\mathbb{E}{X}_{n\wedge T}=\mathbb{E}{X}_0=0$. Passing to the limit using the convergence in L1 proved in (b),One can also pass directly by the dominated convergence theorem, since $|X_{n\wedge T}|\le Y$.

If $T$ is future time to dementia from age 50, its survival function isThe tail-sum formula for expectation gives the expected future time alive without dementia:

With administrative censoring at $c$, one patient is observed to experience $A$ with probabilitysoThe observed time is $\min (T_A,T_B,c)$, whose mean follows from the tail-sum formula for expectation:Hence

Write $S_n={\sum }_{j=1}^n{Y}_j$ for the partial sum. Fix an integer $M\ge 1$. The tail-sum formula for expectation, applied to the nonnegative random variable $|Y_1|$, givesbecause $\mathbb{E}|Y_1|=\infty$. The events $\{|Y_n|>Mn\}$ are independent, so the second Borel--Cantelli lemma shows that $|Y_n|/n>M$ infinitely often with probability one. Taking the countable intersection over $M\in \mathbb{N}$ yieldsalmost surely.

Now $Y_n=S_n-S_{n-1}$, and the triangle inequality givesIf the limit superior of $|S_n|/n$ were finite, the right-hand side would have finite limit superior, contradicting the preceding conclusion. Thereforealmost surely.

The nonnegative integer-valued tail-sum formula for expectation givesThis is finite because $t-1>1$. Here $\zeta$ is the Riemann zeta function on its convergent real domain. The floor function is nonnegative on the support, so the tail-sum identity applies directly.

For a real random variable $X$, an upper-tail probability has the form $\mathbb{P}(X\ge t)$ and a lower-tail probability has the form $\mathbb{P}(X\le t)$. Each is the probability of an event lying beyond a chosen threshold in one direction. A tail probability need not be small: the threshold determines how much of the probability distribution it includes. A concentration inequality bounds such probabilities, often for deviations from an expected value.

Endpoint conventions matter. Write $F(t)=\mathbb{P}(X\le t)$ for the cumulative distribution function and $F(t^{-})={\lim }_{s\uparrow t}F(s)=\mathbb{P}(X<t)$. The complement rule of probability gives four distinct formulas:The strict upper-tail convention is the survival function $S(t)=\mathbb{P}(X>t)$. Its value differs from the inclusive upper tail probability by exactly the probability mass at the threshold:A singleton with positive probability mass is an atom of a measure. Thus $1-F(t)$ excludes an atom of a measure at $t$, whereas $1-F(t^{-})$ includes it. These endpoint identities follow directly from the cumulative distribution function properties in Kyle Siegrist, Distribution and Quantile Functions: endpoint probabilities and right tails.

As the threshold increases, both upper tail probabilities are nonincreasing functions. The strict survival function is a right-continuous function; the inclusive upper tail probability takes the upper endpoint value at a downward jump, equal to the left limit of the survival function. Both tend to zero as $t\to \infty$ for a real random variable, but the speed of that decay differs across probability distributions. The cumulative distribution function properties and their proof from continuity of probability measures are given in MIT 6.436J, Lecture 4: random variables and cumulative distribution function properties.

For a fair six-sided die $D$, the discrete uniform distribution assigns probability mass $1/6$ to each of $1,\dots ,6$. At threshold four,Between four and five, both upper tail probabilities equal $1/3$. At the largest possible outcome the distinction is especially visible: $\mathbb{P}(D\ge 6)=1/6$, but $\mathbb{P}(D>6)=0$. The diagram shows exact probabilities for this mathematical model; its dots specify which endpoints belong to each step function.

If a probability distribution has a probability density function $f$, then every singleton has zero probability mass andFor an exponential distribution of rate two, $f(x)=2e^{-2x}$ for $x\ge 0$ and zero otherwise, so $S(t)=e^{-2t}$ for $t\ge 0$ and $S(t)=1$ for $t<0$. Hence $\mathbb{P}(X\ge 1)=e^{-2}\approx 0.135335$. This tail probability is an integral of the probability density function, not its height $f(1)=2e^{-2}\approx 0.270671$. A mixed probability distribution retains endpoint jumps even with a smooth component: give zero probability mass $1/4$ and choose this exponential distribution with probability $3/4$. Then $\mathbb{P}(X\ge 0)=1$, $\mathbb{P}(X>0)=3/4$, and $S(t)=(3/4)e^{-2t}$ for $t\ge 0$.

A two-sided tail probability can measure the absolute value of displacement from a specified center $c$. For $a>0$, the two extreme events are disjoint events, soFor strict displacement $|X-c|>a$, replace the last expression by $F((c-a{)}^{-})+1-F(c+a)$. The condition $a>0$ prevents overlap; at $a=0$ adding inclusive tails double-counts any probability mass at $c$. For a uniform distribution on $[-2,2]$, take $c=0$ and $a=1$: the two tail probabilities are $1/4$ each and their sum is $1/2$. Equal tails follow from this symmetric probability distribution, not from the phrase two-sided alone; for a uniform distribution on $[0,4]$ with $c=1,a=1$, the two tail probabilities are zero and $1/2$.

The tail-sum formula for expectation turns a whole curve of tail probabilities into an expected value. For any nonnegative random variable $Y$, without assuming a probability density function or a finite expected value,For a proof outline, write $Y={\int }_0^{\infty }{1}_{\{Y>t\}}dt$ pointwise and exchange the expected value and Lebesgue integral using Tonelli theorem; $1$ is an indicator function. The inclusive version has the same Lebesgue integral: positive probability masses occur at only a countable set of thresholds, which has Lebesgue measure zero. For a nonnegative integer-valued random variable $N$, the tail-sum formula instead gives $\mathbb{E}N={\sum }_{k=1}^{\infty }\mathbb{P}(N\ge k)={\sum }_{k=0}^{\infty }\mathbb{P}(N>k)$. The integer hypothesis is essential for these sums. The integral identity, its indicator function proof, and the integer version appear in Kyle Siegrist, Additional Properties of Expected Value: integration and summation of right tails.

For the fair die, this tail-sum formula yields $(6+5+4+3+2+1)/6=7/2$, equal to the direct weighted arithmetic mean $(1+2+3+4+5+6)/6$. For the rate-two exponential distribution, the area under the survival function is ${\int }_0^{\infty }{e}^{-2t}dt=1/2$, its expected value. The first panel below shades an integral of the probability density function for a single threshold; the second shades an integral of the survival function across all nonnegative thresholds. These are analytical illustrations, with the displayed curves truncated at three; their exact total areas use an infinite integration range.

Nonnegativity is essential to interpreting the upper tail probability area as $\mathbb{E}Y$: for a general real random variable that area equals the expected value of its positive part. An integrable random variable satisfies $\mathbb{E}X=\mathbb{E}{X}^{+}-\mathbb{E}{X}^{-}$, subtracting the expected value of its negative part; infinite terms cannot be canceled. Even when $Y$ is finite almost surely, its expected value can be infinite. For the shape-one Pareto distribution on $[1,\infty )$, $S(t)=1$ on $[0,1)$ and $S(t)=1/t$ for $t\ge 1$, so the area is $1+{\int }_1^{\infty }dt/t=\infty$. The finite versus infinite expected value distinction is illustrated in Kyle Siegrist, Definitions and Basic Properties: exponential and Pareto expected values.

Why are tail probabilities useful? They answer threshold questions directly, and a concentration inequality can bound them without knowing the full probability distribution. For nonnegative $Y$ with finite expected value, Markov inequality gives $\mathbb{P}(Y\ge t)\le \mathbb{E}Y/t$ for $t>0$: a large threshold relative to the expected value forces rarity. The quantile function reverses the question by choosing a threshold for a prescribed cumulative level. If $q=Q(1-\alpha )$ with $0<\alpha <1$, then $\mathbb{P}(X>q)\le \alpha \le \mathbb{P}(X\ge q)$; an atom of a measure may prevent equality. For the die, $Q(0.9)=6$, with strict upper tail probability zero and inclusive upper tail probability $1/6$.

A tail probability describes rarity under a specified probability distribution; it is not automatically a conditional probability after extra information. For $u\ge t$ with $\mathbb{P}(X\ge t)>0$,because the threshold events are nested. Thus the die has $\mathbb{P}(D\ge 5)=1/3$ but $\mathbb{P}(D\ge 5\mid D\ge 4)=2/3$. Conditioning changes the sample space and renormalizes its probability measure; the same extreme outcomes can become common in that restricted population.

For independent identically distributed observations with continuous cumulative distribution function $F$, fix the maximum $Y_n$ of the first $n\ge 1$ observations and let $\tau$ be the first subsequent observation exceeding it. The probability integral transform gives $U=F(Y_n)$ density $n{u}^{n-1}$ on $(0,1)$. Conditional on $U=u$, $\tau$ has a geometric distribution of parameter $1-u$. ThereforeThe masses sum to one, so the waiting time is finite almost surely, but the tail-sum formula for expectation gives $E\tau =\infty$. These conclusions require only continuity of $F$, not a density or a strictly increasing distribution function.

Wald's equation turns a random sum into a product of two expected values: the average contribution per step and the average number of steps. Its surprising feature is that the number of steps may depend on what has already happened. A procedure can stop on its first successful Bernoulli trial, for example, while the identity still accounts for its total cost. The crucial restriction is that the decision to take the next step cannot use that step's unobserved outcome.

Let $X_1,X_2,\dots$ be real independent and identically distributed random variables with $\mathbb{E}|X_1|<\infty$, let $\mu =\mathbb{E}[X_1]$, and put $S_0=0$ and $S_n={\sum }_{i=1}^n{X}_i$. Suppose $N$ is a nonnegative integer-valued stopping time for the natural filtration ${\mathcal{F}}_n=\sigma (X_1,\dots ,X_n)$, with $\mathbb{E}[N]<\infty$. Then $S_N$ is an integrable random variable andThese hypotheses allow statistical dependence between $N$ and the increments; they do not allow access to future increments. The finite-expected value requirement is stronger than stopping almost surely.^[ref]

For the proof idea, count step $i$ only on $\{N\ge i\}$. This event is determined by the first $i-1$ observations, so its indicator function is independent of $X_i$. The Proof of Wald's equation by stopping indicators combines this observation with the tail-sum formula for expectation. The same calculation with $|X_i|$ gives $\mathbb{E}{\sum }_{i=1}^N|X_i|=\mathbb{E}|X_1|\mathbb{E}[N]<\infty$, which justifies interchanging the expected value and the infinite series. This is why the result survives a data-dependent end point without assuming an independent count.

The identity is useful in randomized algorithms and repeated sampling: one can translate an average amount of work into an average number of attempts, or conversely, without first finding the full probability distribution of the total. The examples below separate a permissible stopping rule from a rule that peeks ahead and from a valid rule whose average waiting time is infinite.

Let $X$ have survival function $\mathbb{P}(X\ge x)=x^{-s}$ for $x\ge 1$, with $s>1$. Its expected value is $s/(s-1)$. The tail-sum formula for expectation givesThe absolutely continuous probability distribution gives zero mass to the integers, so $\lceil X\rceil =\lfloor X\rfloor +1$ almost surely and $\mathbb{E}[\lceil X\rceil ]=\zeta (s)+1$. Taking expectations of $\lfloor X\rfloor \le X\le \lceil X\rceil$ gives $\zeta (s)\le s/(s-1)\le \zeta (s)+1$, which rearranges to the displayed bounds on the Riemann zeta function. Finiteness is justified by $\lfloor X\rfloor \le X$ and $\lceil X\rceil \le X+1$.