Using the indicator random variable, sum over the values of the discrete random variable :
Dividing by the positive probability proves . On the product vanishes, so no additional contribution is omitted.
Write and . Since , the latter expected value is finite. Conditional on the first move to or , total time is one plus the remaining time, while the terminal success indicator random variable is unchanged. The Markov property and linearity of expectation give
At either absorbing boundary the remaining time is zero, so .
Let . The linear term has zero second difference and has second difference . Consequently
which is exactly the required recurrence, and . Uniqueness follows as before: the difference of two solutions has zero second difference and zero endpoint values. Hence
This is the success-weighted duration underlying the duration of gambler's ruin conditioned on a chosen boundary.
A convenient choice for this irregular region is Monte Carlo integration. The region is contained in . For independent uniform points in that square, let
The indicator random variable incorporates the curved boundary directly. This estimator is unbiased; the integrand is bounded on the square, so its variance is finite. The variance of a sum of independent terms gives root mean square error in big O notation. This is a stochastic error rate. Applying a rectangular Simpson's rule to the indicator-weighted integrand would lose the smoothness required for its fourth-order error bound.
Let . The product of two distinct empty-box indicators in uniform allocation is the indicator random variable of both boxes being empty, so . Thus
Indeed for , and taking the positive integer power preserves this strict inequality. This proves the negative covariance directly.
Poisson distribution Created 2026-09-24 Updated 2026-10-14
For , a Poisson random variable has probability mass function
The exponential function series verifies normalization. At , define with certainty. The equality of mean and variance is a distinguishing model property, though it does not by itself characterize the law.
When counting events in a homogeneous Poisson process, distinguish its rate from the distribution parameter: an interval of duration has . A rate measured per minute times a duration measured in minutes gives a dimensionless expected count. This process assumes independent increments, a constant rate, and a negligible chance of multiple events relative to interval length in a sufficiently short interval. A rate alone does not establish a Poisson distribution. See Bertsekas and Tsitsiklis, chapter 6 summary, pages 46-47.
For a constructed arrival model with events per minute over minutes, . The mean and variance are both three, and
The probability of at least one event is . These results describe the specified process, not every arrival mechanism with the same average rate.
The Poisson limit theorem, often called the law of rare events, connects this law to the binomial distribution. Keep fixed and let for integers . For each fixed nonnegative integer and sufficiently large ,
There are more opportunities, each less likely to succeed, while the mean stays and the variance approaches . For , the probability of three successes is at , at , and at , approaching the Poisson distribution value .
Figure 1.
Binomial counts approach Poisson counts while their mean stays fixed at three
. Details.
The panels show the same count scale and the same Poisson distribution reference. At , is not especially small and the difference is visible. No universal trial-count cutoff guarantees an adequate approximation for every event.
The independence assumption matters even when every success is rare. For , if all indicator random variables equal one shared Bernoulli random variable of parameter , their sum is zero with probability and with probability . Its mean is three, yet its zero-count probability tends to one, not . Some dependent counts still admit approximation through the Stein-Chen method, but this requires additional control of dependence.
For historical orientation, the BnF records Poisson's original probability treatise, Recherches sur la probabilité des jugements, as published in Paris in 1837. This bibliographic fact alone does not establish when the modern distribution terminology arose. See BnF record of Poisson's 1837 treatise.
Random variable Created 2026-09-24 Updated 2026-10-14
A real-valued random variable is a measurable function from a probability space to the real numbers with their Borel sigma-algebra. More general targets give random elements. For every Borel set , measurability ensures that is an event, so the question "does the observed value lie in ?" has a defined probability.
The function is fixed; its input outcome is uncertain. This separates what we measure from how the uncertainty is modeled. A probability distribution is the resulting pushforward measure, . A cumulative distribution function, probability mass function, or probability density function describes that measure in an appropriate setting. The random variable and its probability distribution are different objects: the former also retains its relationship to other measurements on the same sample space.
For two independent uniform dice, let record their results and define and . The 36 ordered pairs are equally likely, but the resulting probability mass functions differ:
For the sum, count the diagonal of the outcome grid having total . For the maximum, subtract the pairs with both results below from the pairs with both results at most . These examples show how a deterministic function transforms a simple input probability distribution into a nonuniform output one.
Figure 1.
Different random variables on the same equally likely dice outcome space
. Details.
The corresponding expected values are and . The first follows immediately from linearity of expectation; the second follows from . Neither number must be an attainable result. An expected value describes an average under the probability measure, not a prediction that the next observation will equal it.
The distinction between a random variable and its probability distribution matters for dependence. and have the same discrete uniform distribution and are independent random variables. and a second copy of also have that same marginal probability distribution, but they always agree. Their joint probability distribution is concentrated on the diagonal; the marginals alone cannot say which relationship holds. This is why a model for several measurements must specify their joint law or an appropriate independence assumption.
Indicator random variables turn events into numbers: equals one on and zero elsewhere, and . This connects event counting with expected value and variance, and lets tools for random variables answer questions about probabilities. More complicated functions of observations can describe totals, waiting times, or estimation errors using the same framework.
Repeated singleton-removal allocation Created 2026-10-31 Updated 2026-11-05
Fix bins. In repeated uniform balls-in-bins allocation, throw each remaining ball independently into those same bins, remove every ball that is alone in its bin, and repeat with the survivors. Let be the number remaining before round .
Conditional on , a specified ball is alone with probability . Its survival probability is therefore , so linearity of expectation gives
For or the next count is zero. Here denotes the fixed bin count, not the current number of balls; confusing those two quantities changes the process.
The survival indicator random variables are generally dependent. For two initial balls and two bins, they survive together exactly when they choose the same bin, of probability each round. Hence and for . In particular, replacing the conditional formula by the same nonlinear function of would not be justified by linearity of expectation.
Reverse Fatou lemma 2026-10-31
If are random variables bounded above by an integrable function , with all relevant expectations well defined, Fatou's lemma applied to the nonnegative variables gives . In particular, bounded indicator random variables that tend almost surely to zero have probabilities tending to zero.
Second moment method Created 2026-09-24 Updated 2026-10-14
The second moment method uses a random variable's expected value and second moment to establish that a counted or measured quantity is positive with substantial probability. It is useful when a positive average alone could be caused by extremely large values on very rare outcomes. Controlling the variance rules out too much of that concentration in rare outcomes.
For a nonnegative random variable with and finite second moment, the second-moment bound for positivity gives
Equivalently, . The method also includes the simpler Chebyshev's inequality bound . Thus a sequence of such random variables with has with probability tending to one. These statements require no independence assumption. The variance argument and its use for random counts are developed in Zhao's lecture notes. [ref].
For an original toy count, let count successes in ten independent Bernoulli trials with success probability . The binomial distribution gives
Consequently . The exact probability is . The first moment method and union bound only give the upper bound here. First and second moments therefore answer complementary existence questions.
Figure 1.
The second moment method certifies a positive count, while statistical dependence can change the conclusion despite an unchanged mean
. Left: exact binomial distribution probabilities of at least one success and second-moment lower bounds for ten independent trials as the success probability varies. Right: the same ten trials with either occur independently or share one common Bernoulli outcome. Both counts have mean one, but the perfectly linked count has much larger variance and only probability of being positive. All data are original specified probability models. Details.
For a sum of indicator random variables, the variance of a sum is
Independence makes the covariances vanish, but the formula itself also covers dependent counts. For the same ten success probabilities, let every trial share a single Bernoulli random variable : then , with mean one, variance nine, and . The second-moment lower bound is exactly . Ignoring the positive covariances would produce the false independent-count conclusion. Zhao's discussion of sums of indicators explains why overlapping counted structures require these pairwise terms. [ref].
Separate chaining Created 2026-10-13 Updated 2026-10-20
With separate chaining, each hash bucket in a hash table contains a collection of records, often a linked list. Lookup computes the bucket index, then follows that chain until a key equality comparison succeeds or the chain ends. A hash collision therefore affects the search work without merging unequal keys. Deletion searches the same chain and unlinks the matching record; in a singly linked list, remembering the preceding record during the search permits the unlink.[ref]
For the four-key integer example in hash table, insert a new record at the head of its chain after checking that its key is absent. Inserting in that order makes hash bucket hold , hash bucket hold , and the other two hash buckets empty. All five subsequent operations below select hash bucket because :
Figure 1.
Separate chaining traces lookup, replacement, deletion and insertion through key equality
. Original deterministic model with . The table counts actual keys inspected, not elapsed machine time. Operations occur from top to bottom; only an absent key adds a new record, and the untouched record remains in hash bucket . Details.
get(5) rejects key , accepts key , and returns after two key equality comparisons. get(13) rejects and reports absence after three comparisons. put(5,B*) examines and replaces the value without changing . delete(9) examines just the head record, removes it, and gives . Finally, put(13,E) rejects before inserting the new head record; returns to and the chain is . The successive hash table load factors are . These counts follow from the stipulated chain order; a different insertion policy changes the successful-search counts.
For a chain of length , lookup and deletion by key take time complexity in Big O notation. The same applies to put before any resizing, since replacement semantics require checking for an existing equal key. Head insertion alone is if absence is already known; that is a different precondition. These bounds assume bucket-index hashing, array access, key equality comparisons, allocation and link updates. A long string or large integer can make hashing or comparison depend on its encoded length, so counting record visits alone does not establish constant running time.
Under simple uniform hashing, each distinct key's bucket index is an independent random variable with a uniform distribution on a finite set of indices. The keys and query are fixed independently of this random assignment. Then lookup has expected time complexity, where is the hash table load factor; it is expected when stays bounded. These are model assumptions, not an automatic consequence of using a deterministic hash function.[ref]
Here is the short calculation. For an absent query and stored keys , let be the indicator random variable of . The number of records inspected has expected value
by linearity of expectation. For a present fixed query, scanning its entire chain inspects at most itself plus all other colliding records, with expected value ; stopping at the match only decreases this upper bound. Adding constant hashing and bucket access yields expected for either query. The argument needs pairwise collision bounds; it does not require all the indicator random variables to be independent. A universal hash family can provide a related bound by random choice of a hash function for a fixed key set, as explained in that article.
The worst case remains , and an absent query takes comparisons if all records occupy its hash bucket. For instance, all collide under . Separate chaining remains correct, but a sequence of insertions that each checks the existing chain can take quadratic total work. Amortized analysis of resizing does not remove this search cost, and an adaptive choice of keys based on a known hash function is outside the stated simple uniform hashing model.
Choose one random variable with the continuous uniform distribution on , and reuse it in every event:
Each probability is , so their harmonic series diverges, just as in summable and harmonic event probabilities. But the events are decreasing: . For every outcome , all indices with fail. Only finitely many events occur on that outcome. The limsup of events is exactly , a zero-probability event. This is a concrete closed-interval version of the shrinking-interval dependence example.[ref]
The missing assumption is visible already in two events. For , their intersection is , hence
Moreover, the whole tail union is just , with probability . This calculation explains directly why divergence alone fails: overlapping events keep spending their individual probabilities on the same outcomes.
Let be the total number of occurrences, a sum of indicator random variables. Although almost surely, Tonelli theorem gives . More explicitly, for : very small positive values of give very long, but finite, initial runs. Infinite expected value does not imply a positive probability of an infinite count.
Figure 1.
Equal harmonic event probabilities with fresh independent inputs or one shared input
. Each row is one finite simulation of the indicator random variables of for ; a dot means the event occurred. Fresh independent random variables allow scattered returns; a shared uniform random variable yields an initial run followed by zeros. The horizontal axis uses a logarithmic scale to show early runs clearly. These finite simulations illustrate the two models and cannot prove infinitely many occurrences or eventual stopping. Details.
Stein-Chen bound with the Poisson Stein factor Created 2026-10-14 Updated 2026-11-05
Let and , where each indicator random variable is independent of all indicators outside jointly. Write and . For a test-event solution of the Poisson Stein equation, independence gives
Telescoping each difference and using bounds the total variation distance by that factor times . Directed dependence neighborhoods are allowed. If , the count is identically zero.
Stein-Chen method 2026-10-14
The Stein-Chen method compares an integer-valued count with a Poisson distribution by solving the Poisson Stein equation and estimating its expectation at the count. For sums of indicator random variables, dependency neighborhoods expose local overlap errors. This gives total variation distance bounds without having to compute the entire count distribution.
Tail-sum formula Created 2026-09-24 Updated 2026-10-18
The tail-sum formula expresses an expected value as the area under a survival function. For every nonnegative random variable ,
This Lebesgue integral and the expected value may both be ; a probability density function is unnecessary. For a random variable taking values in the nonnegative integers, the corresponding sum is
The events and coincide because takes integer values. Thus the strict sum starts at zero, while the inclusive sum starts at one.[ref]
For an original example, let the probability mass function of be
Its expected value computed directly is . The strict tail probabilities at thresholds are : their sum is again . There is no probability mass at two, yet the event still has probability . The survival function has heights on the successive intervals ; each interval has length one, so its integral is the same sum.
Figure 1.
The same expected value from probability masses and survival columns
. The exact constructed probability mass function assigns to . The contribution appears in one survival column, while the contribution appears in three. Filled endpoints give the strict survival function at its jumps; open endpoints show the preceding height. The shaded area is . Details.
The indexing matters numerically. Starting the inclusive sum at zero adds , giving for this example. Starting the strict sum at one omits , giving . For a general nonnegative random variable, replacing with inside the integral is harmless: the difference is , nonzero at only a countable set of thresholds. For each positive integer , at most thresholds can have probability mass at least ; their countable union contains all thresholds with positive probability mass and has Lebesgue measure zero. This reasoning concerns an integral, not equality of the two survival function conventions at every point.
For a continuous original example, take the uniform distribution on the interval . Its survival function is for and zero for . The area is a triangle of base four and height one:
Directly integrating against the probability density function gives the same expected value, . The integral of the probability density function alone is one; it is the survival function whose area is the expected value.
Figure 2.
A uniform density has total probability one and survival area two
. Exact curves for the uniform distribution on . The probability density function has integral one, while the survival function has integral two. Splitting the survival area at gives before the cap and beyond it, the expected values of and the positive part , respectively. Details.
The proof counts layers of each outcome. For a realized value , the indicator function equals one over an interval of length , so
Tonelli theorem permits the interchange because the indicator function is nonnegative; no finite expected value is assumed. Similarly, an outcome contributes one indicator random variable for each of the events that occur:
Again Tonelli theorem applies to the nonnegative sum, or equivalently the monotone convergence theorem applies to its partial sums. This exchanges counting layers within each outcome with averaging across outcomes. The existing integer-valued hypothesis in the tail-sum formula explains what changes when the values are not integers; the tail integral formula for moments weights the layers to obtain higher moments.
For an integrable random variable that can have either sign, apply the nonnegative formula separately to its positive part and negative part :
Integrability makes both integrals finite. More generally the difference defines an extended expected value when at least one is finite; if both are infinite, subtraction does not define an expected value.[ref]
Tail probabilities are often easier to measure or bound than a whole probability density function. For a device's survival time, the survival function records the probability of still operating at each threshold; its integral gives the mean operating time. A finite observation window naturally gives the expected value of a capped nonnegative random variable. For a mathematical bound, for all implies . The tail-sum formula turns control of a whole family of events into control of an average.