The inverse change of variables is , , with absolute Jacobian determinant . Because the original random variables are independent, their joint density is . Thus the transformed joint density is
The support is important: implies .
For independent exponential random variables of rate and , this becomes on . Integrating out gives the density of the sum:
It vanishes for . On the other hand, the cumulative distribution function of the maximum is
Differentiating yields exactly the same density. The maximum and have the same distribution, as described by maximum of two exponentials as a scaled sum; this does not assert that they are equal for the same pair of sampled values.
The moment-generating function of a random variable is , defined for real where that expectation is finite. For a standard normal distribution, completing the square gives
It is finite for every real . Derivatives at zero give the moments: the expansion therefore gives
For with the normal distribution of mean and variance , write in distribution. Its moment-generating function is consequently
This formula also covers the constant random variable when .
For a nonnegative integer-valued random variable, its expected value is , allowing the value . Since , 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 .
For the first ascent in independent continuous observations, continuity makes ties probability zero. By order symmetry of independent random variables, the first observations have each of their strict orderings with equal probability. For , means exactly that the first observations are decreasing, so
Subtracting consecutive tails gives
with probability zero for . The events decrease to ; continuity of probability under decreasing intersections gives . Finally,
The first observation cannot itself end the run; this is why the tail includes the separate term .
For any , implies . Hence , and taking expected values gives the Chernoff bound
At this is the trivial bound one; an infinite exponential moment merely gives a noninformative bound. For positive at which all required moment-generating functions are finite, define . Independence of the source random variables implies
Applying the Chernoff bound to gives
Consequently
Here and, for a nontrivial target, .
The effective bandwidth is the capacity charge of one source for this exponential-moment tail criterion. Independent sources contribute additively. It incorporates variability as well as mean demand: the Jensen inequality gives , and, under exponential integrability near zero, as . For bounded traffic its large- limit is the essential peak, as described by the mean and peak limits of effective bandwidth. Thus larger gives more weight to rare high demands. This is a one-window demand bound; a queue's overflow probability over many windows requires additional temporal modeling, not just this single-window calculation.
For the normal distribution , completing the square in its density gives the moment-generating function
Write and for the aggregate mean and variance. The exponential-moment capacity condition becomes
For , the last two terms are minimized at , where their sum is . Therefore Gaussian effective bandwidth yields the sufficient condition
Equivalently, optimizing the exponential bound directly when gives ; when the best nonnegative- bound is one. The square-root condition is sufficient rather than necessary because an exponential bound does not equal the exact normal tail.
For the exact condition, independence and multiplication of the normal moment-generating functions show that . For , let be the standard normal distribution function. The normal law is continuous, so
Since is continuous and strictly increasing from zero to one, the exact Gaussian overflow constraint is
The constant depends only on the desired tail exponent , not on the source counts. It is positive when , zero when , and negative when . For example, at the exact normal quantile is about , whereas the Chernoff bound uses ; the latter reserves more capacity.
Finally, the positive-variance hypothesis must not be hidden. If , then almost surely, and the zero-variance boundary of an overflow constraint gives . For , the exact condition is then . In particular does not meet the target even though substituting into the printed non-strict square-root inequalities would allow it. The displayed normal-quantile equivalence applies to nondegenerate Gaussian traffic; the deterministic case requires this strict boundary convention.
A real random variable is a sub-Gaussian random variable with exponent when its moment-generating function satisfies
Differentiating at from both sides gives . Exponential integrability near zero justifies this differentiation. Conversely, if and , convexity gives
The last inequality follows by comparing power series using . The case is immediate. Thus a bounded random variable is sub-Gaussian exactly when it is centered; the bound is one possible exponent.
For , the Markov inequality applied to gives . Choose and repeat with . The union bound yields
If , the same exponential estimate with arbitrarily large shows almost surely, so all subsequent inequalities are trivial.
Integrating this tail probability estimate gives, for every real ,
We need . For integer this follows inductively from and . To cover real as well, set . Differentiating the Gamma function integral gives for a Gamma distribution with shape and rate . The Jensen inequality bounds this by . Hence and . Taking the th root now proves
Here is the Lp norm.
For the final assertion we prove the required Littlewood interpolation inequality, rather than assuming it. Apply Holder inequality with conjugate exponents and :
Raising to the power gives . The preceding Lp norm estimate with says . Therefore
Convergence in probability supplies a subsequence converging almost surely to : choose it so , then apply the first Borel-Cantelli lemma. For each fixed , the tail of this subsequence lies in , and its almost sure limit is . Thus has a version measurable with respect to the completed tail sigma-field of the independent sequence.
By Kolmogorov's zero–one law, every event in that tail sigma-field has probability zero or one. Consequently for every rational . Since is a finite real random variable, its distribution function has limits zero and one at the two infinities; monotonicity then identifies a single threshold with . Hence is almost surely constant. Completion only adds null events and does not alter the zero-one conclusion.
Let be one uniform random variable on , and define
For every the sequence is eventually zero, so almost surely. But , whose sum diverges. This sequence is not completely convergent; the exceedance events are nested and dependent.
Let be one score. It has the discrete uniform distribution on , so its expected value and second moment are
Therefore
For independent throws, linearity of expectation and additivity of variance give and . The sample average consequently has expectation and variance .
The Chebyshev inequality follows by applying the Markov inequality to the nonnegative square of a centered random variable. It gives
This is at most if . Thus suffices, as does every larger integer. This is the smallest integer guaranteed by this particular Chebyshev inequality bound; it need not be the smallest integer satisfying the actual probability requirement.
A sigma-algebra on is a collection containing , closed under complements relative to , and closed under countable unions. These properties also give closure under countable intersections by De Morgan laws.
Let . Every constituent sigma-algebra contains , so . If , its complement belongs to every , hence to . Likewise, if for all , then belongs to every . Thus is a sigma-algebra. For an empty indexing set, the usual intersection convention gives , which is also a sigma-algebra.
A union need not work. On take
Their union contains and but not , so it is not a sigma-algebra. Put and let be the collection of all sigma-algebras on containing . This collection is nonempty because it contains the power set . By the preceding intersection argument,
is a sigma-algebra containing every , and it is contained in every other such sigma-algebra. This proves existence and minimality.
For the independent random variables, define the tail sigma-algebra by
Fix a tail event . For each , it belongs to , which is independent of . To justify independence of the generated sigma-algebras, first use independence of finite collections on cylinder events, then extend twice by the pi-lambda theorem. In particular, for every and every .
The increasing union is an algebra of sets generating . The collection of satisfying this factorization is a Dynkin system: it contains , is closed under complements, and under countable disjoint unions. The pi-lambda theorem therefore extends the factorization to all . Since , taking gives . Consequently,
This is the Kolmogorov zero-one law, proved here directly.
For each fixed , write for , with . The random variable is finite, so . Adding a real sequence tending to zero changes neither the extended-real limit inferior nor the extended-real limit superior. Hence
The quantities on the right are measurable with respect to : write the limit inferior as and the limit superior as , using countable operations on measurable functions. Therefore both threshold events belong to every such sigma-algebra, and hence are tail events, for every real threshold, including when either limit is infinite.
The final recurrence claim is false under the printed hypotheses. For , let be independent signs with equal probabilities for and , and set . These random variables are independent, have symmetric distributions, and obey . Nevertheless, the geometric series gives, on every sample path,
Thus the proposed repeated-return event has probability zero, even though none of the increments is degenerate. The Kolmogorov zero-one law does not determine which of zero and one occurs.
An additional identical-distribution hypothesis makes the intended conclusion true. Here is a full proof of that qualified version, using the oscillation of a bounded centered iid random walk. Symmetry and integrability give , so is a martingale for its natural filtration. If the common probability distribution is concentrated at zero, every is zero and the conclusion is immediate. Otherwise choose with . The Borel-Cantelli lemmas then give infinitely often almost surely; thus cannot converge to a finite limit.
For , let . Before the sum is below , and at it is at most . The stopped martingale is therefore nonnegative. A stopped integrable martingale remains a martingale at these bounded times, and a nonnegative martingale converges finitely almost surely by the martingale convergence theorem. On this would force to converge finitely, which has just been ruled out. Hence almost surely. Apply the same argument to and take a countable intersection over positive integer . It follows that
There are therefore arbitrarily late passages from above to below . A path with bounded increments of magnitude at most cannot make such a passage without visiting : jumping directly between its two open complementary half-lines would require an increment larger than . There are infinitely many such visits. Thus with the added identical-distribution hypothesis, the intended answer is
For and , let . Symmetry of the standard normal distribution and the Mills ratio asymptotic just proved give
For the series of these probabilities converges, since its terms are eventually bounded by a constant times the convergent p-series . For it diverges: choose strictly between and one, and use for sufficiently large , reducing to the divergent p-series . At it still diverges, as the integral test gives
For , the first Borel-Cantelli lemma makes occur only finitely often. For , independence of the random variables makes the events independent, so the second Borel-Cantelli lemma makes them occur infinitely often almost surely. Apply these conclusions simultaneously at for positive integers , and at . On the resulting probability-one event, the limit superior is at most every and at least two. Therefore the Gaussian sample limsup at logarithmic scale is
The real L2 space on a probability space consists of equivalence classes of measurable functions satisfying , where two random variables represent the same element if they are equal almost surely. Its norm is
Passing to equivalence classes makes this a genuine norm: exactly when almost surely. The Minkowski inequality gives the triangle inequality.
Let be a Cauchy sequence in this norm. Choose an increasing sequence of indices such that
This is possible by choosing beyond a Cauchy threshold for tolerance . Set . The Cauchy-Schwarz inequality on a probability space gives . By Tonelli theorem,
Thus the series of absolute differences is finite almost surely. Define on this probability-one event, and give it the value zero on its complement. It is a measurable function, and almost surely.
For , the Minkowski inequality gives
Apply the Fatou lemma to the squared difference as . It follows that
In particular , and therefore by the Minkowski inequality. This proves convergence in L2 of the subsequence. To recover the entire sequence, for a prescribed choose a Cauchy threshold for , then choose with and . For every ,
Hence , proving completeness of Lp spaces for without assuming the desired completeness in the argument.
A filtration on a probability space is an increasing sequence of sigma-algebras contained in : . A real stochastic process is a martingale for this filtration if is -measurable, , and
The first condition is adaptedness; the tower property of conditional expectation then gives whenever .
The almost-sure martingale convergence theorem states that if a real martingale satisfies , then some integrable random variable satisfies almost surely. The more general almost sure submartingale convergence theorem needs only for a submartingale. In particular, a nonnegative martingale converges to a finite integrable limit almost surely, because its expected value is constant. Mere boundedness in the L1 norm does not imply convergence in L1. The stronger uniformly integrable martingale convergence theorem gives both almost-sure convergence and convergence in L1 when the martingale is uniformly integrable.
Here , so for every ,
The Jensen inequality for the strictly convex exponential function gives
In fact the inequality is strict: and exclude a constant random variable. In particular, as required.
For , independence and identical distribution give
Thus is positive, integrable with mean one, and adapted to the natural filtration. Conditioning on the next increment gives
Consequently This is the exponential martingale of a random walk.
A family of integrable random variables is uniformly integrable if
This controls the contributions of large values uniformly over the family, rather than merely bounding its L1 norms.
Put and . The conditional Jensen inequality gives , hence . The Markov inequality therefore gives
Using the measurability of in the defining integral identity for conditional expectation, for every we get
The first term tends to zero as because is integrable, by the dominated convergence theorem. Given , first choose to make it less than , then choose to make the second term less than . These choices work for every . This proves uniform integrability of conditional expectations:
In fact the argument works for an arbitrary family of sigma-algebras; nesting is not needed for this conclusion.
Values at the endpoint one do not affect any of the conclusions, since . Set to define each random variable everywhere, and choose a Borel measurable function agreeing with almost everywhere if necessary. These choices leave all integrals and almost-sure assertions unchanged.
Every dyadic interval at level lies in a dyadic interval at level . Equivalently, is a measurable function of , so : these sigma-algebras form a filtration. Since the uniform distribution of gives , the conditional expectations are integrable and adapted. The tower property of conditional expectation gives
Thus is a martingale, and part (a) proves that it is uniformly integrable.
For , the event is an atom of a sigma-algebra , with probability . The value of the conditional expectation there is therefore
Consequently This also shows directly that .
By the uniformly integrable martingale convergence theorem, there is an integrable such that almost surely and in the L1 norm. To identify this limit, put . Since away from the harmless endpoint, , and is -measurable. Conversely every is a measurable function of . Thus , and both and have -measurable versions.
For , the defining property of conditional expectation gives whenever . Passing to the limit in the L1 norm yields
The increasing union is an algebra of sets generating . The class of events for which this integral identity holds is a Dynkin system, so the pi-lambda theorem extends the identity to every . Since both random variables are measurable there, uniqueness of conditional expectation gives almost surely. We have proved that the dyadic conditional averages recover integrable functions:
because a probability-one assertion for is a full-Lebesgue measure assertion for . Likewise, the uniform distribution of turns convergence in L1 into
No pointwise continuity of is required.
A standard Brownian motion is a real stochastic process with almost surely, continuous sample paths almost surely, and independent increments such that has normal distribution whenever . With its completed, right-continuous natural filtration , its Strong Markov property is the following: for every almost-surely finite stopping time , the process
is a standard Brownian motion independent of . Here the stopping-time sigma-algebra is
In particular, for every bounded -measurable random variable and bounded Borel functional on the continuous path space,
Thus the independence is from the entire stopped past, not only from , and is a statement about the whole future path, not just a single increment.
To prove the Brownian reflection principle without assuming that a level is hit in finite time, fix , , and set and . Continuity of the sample paths makes a stopping time and gives whenever . The stopping time is bounded. Reflect the path after :
By the Strong Markov property, the future increments after are an independent Brownian motion. Negating them preserves their probability distribution, by symmetry of their joint normal distributions. Hence the reflected process has the same path law as .
If , reflection changes nothing on and . If , both paths first hit at the same time and . Therefore, for , the following events agree path by path:
Indeed, the right-hand endpoint is at least , so the reflected path must have hit before or at ; this also forces the original path to have done so. The reflection relation then makes the endpoint inequality equivalent to . Equality cases at satisfy the same relation. Since and have the same probability distribution,
For , both sides are zero, because and .
For , set in this identity. Continuity implies , and the normal distribution of has no atom at . Splitting according to whether gives
Both random variables are nonnegative. Their tails agree for all , which determines their probability distributions, including the mass at zero. Thus the Brownian running maximum satisfies
For and , continuity again gives . Since is a standard normal random variable, the distribution function of the Brownian first-passage time is
It tends to one as and to zero as , proving almost-sure finiteness and absence of an atom at zero. For the standard normal random variable ,
The value of this ratio on the zero-probability event may be defined arbitrarily. Matching the distribution functions proves
Finally, differentiate the distribution function on , using and . The first-passage-time density is
and is zero for . Its integral is one by the endpoint limits of , so no missing mass at an infinite hitting time is present.
Suppose is an equivalent martingale measure and a zero-cost self-financing strategy has holdings . Its discounted terminal value has conditional expectation
If it were an arbitrage, would be nonnegative because . Equivalence implies that it is strictly positive on an event of positive -probability. A nonnegative random variable with zero conditional expectation must be zero almost surely, a contradiction. Thus . The calculation uses the usual integrable one-period strategies, and also works conditionally for finite initial-information-measurable holdings.
For a binary symmetric channel with crossover probability , Shannon's noisy coding theorem gives capacity bits per use, where . For any rate below capacity there are block codes with block length tending to infinity and decoding error tending to zero. Conversely, vanishing-error transmission cannot have asymptotic rate above capacity. At the capacity is zero; the formula also covers by complementing the output.
For discrete random variables, mutual information is
The formula is symmetric. To prove nonnegativity, apply to for positive joint masses. Multiplication by and summation gives . Hence , with equality precisely for independence. The channel information capacity is , over input distributions.
For the ternary channel every conditional output row has entropy , independent of the input. Therefore . Uniform input produces uniform output, since the matrix is doubly stochastic, and attains the bound. Thus
Use at the endpoints. At the noiseless capacity is ; at all output rows are uniform and capacity is zero.
Conditional on , the summands are independent with the common Laplace transform of a nonnegative random variable . The empty sum for is zero. Therefore the compound Poisson distribution has
and applying the probability generating function from part (a) gives
If , differentiating at zero from the right gives and . Hence
The differentiation is justified by and the dominated convergence theorem. No finite moment was assumed in the question, so the formula must also be interpreted when . For any nonnegative random variable , the monotone convergence theorem gives
Apply this to and , and use as , with ; it yields the same formula with value when . If , nonnegativity makes all marks zero almost surely and the result is immediate.
For the second method, condition on the count rather than differentiating a transform. For finite , the tower property of conditional expectation gives , and gives . More generally, Tonelli's theorem and independence give
For , already the term is infinite since . Thus the two methods agree, including in the extended-valued case.
The event occurs precisely when every one of the first levels is at most . Their independence gives the cumulative distribution function
For any nonnegative random variable, the pointwise identity and the Tonelli theorem allow interchange of expectation and integral. Hence
This identity holds as an extended nonnegative integral; finiteness of the mean is not guaranteed by continuity of .