Discrete probability distribution

A discrete probability distribution is a probability distribution concentrated on a finite or countable set of possible values $S$: a random variable $X$ with this law satisfies $\mathbb{P}(X\in S)=1$. Its probability mass function assigns a probability to each value:Thus the probability of an event is obtained by adding masses, rather than integrating a probability density function. The possible values need not be equally spaced, or even integers. When the relevant moments are finite, its expected value and variance are

For a constructed example, assign values $0,2,5$ masses $0.5,0.3,0.2$. They sum to one; $\mathbb{P}(X\ge 2)=0.3+0.2=0.5$, $\mathbb{E}X=0(0.5)+2(0.3)+5(0.2)=1.6$, and $\mathbb{E}[X^2]=4(0.3)+25(0.2)=6.2$. Hence the variance is $6.2-1.6^2=3.64$. A mean can lie between possible values: no outcome here equals $1.6$.

The useful organizing question is what an experiment records. One yes/no indicator random variable gives a Bernoulli distribution; a success count in a fixed number of independent attempts gives a binomial distribution; the attempt number of the first success gives a geometric distribution. A Poisson distribution describes an event count under different assumptions. Naming the quantity first helps prevent selecting a familiar formula for the wrong experiment.

For $0<\theta <1$, this probability distribution on positive integers has mass $\mathbb{P}(X=k)={\theta }^k/(k[-\log (1-\theta )])$. The Taylor identity ${\sum }_{k\ge 1}{\theta }^k/k=-\log (1-\theta )$ proves normalization. Its expectation is $-\theta /((1-\theta )\log (1-\theta ))$, by summing the geometric series after multiplying the mass by $k$.

For an independent sample, the maximum-likelihood estimator solves the equation making this model mean equal to the sample mean. The model mean is strictly increasing: set $t=-\log (1-\theta )$ to obtain $(e^t-1)/t$, whose derivative is positive for $t>0$. Hence a sample mean greater than one determines a unique interior estimate. Pooling several categories changes the likelihood and generally changes this estimate; the ungrouped sample mean is no longer recoverable from the pooled category counts alone.

For a positive random variable $X$, let $D\in \{1,\dots ,9\}$ be its first nonzero base-ten digit. The Benford law is the discrete probability distribution with probability mass functionHere $X$ need not be an integer: $0.0042$, $4.2$ and $4200$ all have $D=4$. Multiplication by an integer power of ten changes the decimal point's position and leaves the first nonzero digit unchanged. Zero has no first nonzero digit, so exclude it. For negative inputs one may explicitly use their absolute values, still excluding zero; that convention must be stated rather than applying a logarithm to a negative number.

The Benford law favors small digits: $\mathbb{P}(D=1)={\log }_{10}2\approx 0.301029996$, whereas $\mathbb{P}(D=9)={\log }_{10}(10/9)\approx 0.04575749$. Thus the model assigns about $30.10\%$ to digit one and $4.58\%$ to digit nine. The masses are positive and their normalization is a finite telescoping series:

Why can digit one be so common? In a decimal significand interval $[1,10)$, the digit-one region $[1,2)$ occupies a larger fraction of the logarithmic scale than the digit-nine region $[9,10)$. The precise assumption is that the fractional part of the base-ten logarithm is distributed uniformly on $[0,1)$; Benford law from logarithmic uniformity turns those unequal interval lengths into probabilities. This makes a surprising digit pattern into a simple geometry of multiplicative size. The logarithmic explanation is also presented in Peter Sheridan Dodds, Benford's Law, essential story.

The Benford law is useful as a proposed model for leading digits when the mechanism supports logarithmic uniformity or an appropriate limiting argument, such as Benford frequencies for powers of an integer. Merely spanning many powers of ten does not establish that assumption. A discrepancy from the Benford law can prompt investigation of the model and data collection; by itself it does not establish fraud, and agreement does not establish authenticity.

Simon Newcomb's 1881 paper, Note on the Frequency of Use of the Different Digits in Natural Numbers, appeared in the American Journal of Mathematics 4, pp. 39–40. Its opening connects unequal leading-digit frequencies with the faster wear of early pages in logarithm tables. The publication metadata and original opening excerpt are available in Newcomb (1881), original publication record and ^[ref]. Frank Benford's The Law of Anomalous Numbers, Proceedings of the American Philosophical Society 78 (1938), pp. 551–572, likewise discusses worn logarithm tables on p. 551 and tabulates observations on p. 553. See Benford (1938), transcription of the original paper with page numbers and publication metadata. These observations motivated study of the digit pattern; they do not make the Benford law universal.

A decimal significand lies in $[1,10)$, obtained by removing the integer power of ten from a positive number. Multiplication by a constant rotates the fractional logarithm modulo one. Invariance under every such rotation makes the fractional logarithm uniform and hence implies Benford law. This is an invariant significand distribution, not a proper scale-invariant distribution for the entire positive number.

For $x>0$, the decimal significand is the unique $S_{10}(x)\in [1,10)$ such that $x=10^k{S}_{10}(x)$ for an integer $k$. Explicitly, $k=\lfloor {\log }_{10}x\rfloor$ and $S_{10}(x)=10^{\{{\log }_{10}x\}}$, using the floor function and the fractional part. For $0.0042$, $4.2$ and $4200$, the decimal significand is $4.2$ and the first nonzero digit is $\lfloor S_{10}(x)\rfloor =4$. In the classical terminology of logarithm tables, the logarithmic mantissa is $\{{\log }_{10}x\}$, which differs from the decimal significand $10^{\{{\log }_{10}x\}}$.

For a positive random variable $X$, write its base-ten logarithm as an integer part plus a fractional part:The floor function handles values below one as well: for $X=0.0042$, $K=-3$ and the decimal significand is $10^Z=4.2$. Since $10^Z\in [1,10)$, the first nonzero decimal digit is $D=\lfloor 10^Z\rfloor$. The monotonicity of the logarithm gives the exact event equivalenceIf $Z$ has the uniform distribution on $[0,1)$, the probability of this interval is its length. Consequently $\mathbb{P}(D=d)={\log }_{10}(d+1)-{\log }_{10}d$, proving the Benford law. This argument assumes uniformity of the fractional part of the logarithm, rather than uniformity of $X$ itself. See the logarithmic-coordinate explanation in Peter Sheridan Dodds, Benford's Law, essential story.

An exact constructed example is the log-uniform distribution on $[1,10)$, with probability density function $f_X(x)=1/(x\ln 10)$ there and zero elsewhere. Its total mass is ${\int }_1^{10}dx/(x\ln 10)=1$. The change of variables formula with $x=10^z$ gives $f_Z(z)=f_X(10^z)(\ln 10)10^z=1$ for $0\le z<1$. Equivalently, integrating directly givesFor example, the probability of first digit four is ${\log }_{10}(5/4)\approx 0.096910013$. By contrast, an ordinary uniform distribution for $X$ on $[1,10)$ has probability density function $1/9$ there, so $\mathbb{P}(D=d)={\int }_d^{d+1}dx/9=1/9$ for every digit. This is a concrete counterexample to any claim that the Benford law holds for every positive random variable.

More generally, a log-uniform distribution on $[A,B)$ with $0<A<B$ has uniform $Y={\log }_{10}X$ on $[{\log }_{10}A,{\log }_{10}B)$. If its logarithmic span ${\log }_{10}(B/A)=m$ is a positive integer, reduction to the fractional part wraps an interval of length $m$ around the unit interval exactly $m$ times, making $Z$ uniform even when $A$ is not a power of ten. Arbitrary partial-decade truncations generally do not have this property: for a log-uniform distribution on $[1,2)$, the first digit is always one.

Under the uniform fractional-logarithm assumption, multiplication by any constant $c>0$ replaces $Z$ by $Z^{\prime }=\{Z+{\log }_{10}c\}$. This is a rotation modulo one, which preserves the uniform distribution and therefore preserves the Benford law; see scale invariance of decimal significands. For the constructed $[1,10)$ example, multiplying by $0.001$ gives a log-uniform distribution on $[0.001,0.01)$ with the same digit probabilities. The claim concerns the decimal significand law: there is no proper probability density function proportional to $1/x$ over all of $(0,\infty )$, since its integral diverges. The existing scale-invariant prior describes that unnormalizable measure, while a finite log-uniform distribution is normalizable.

If $a\ge 2$ is an integer with irrational ${\log }_{10}a$, then the leading digit $d$ of $a^n$ has limiting frequency ${\log }_{10}(1+1/d)$. Indeed the logarithmic fractional parts are the orbit of zero under an irrational rotation of the circle, so everywhere interval frequency under an irrational rotation applies. Thus for $a=2$, digit seven has frequency $(\log 8-\log 7)/\log 10$.

A discrete uniform distribution gives every element of a nonempty finite set $S$ the same probability. Write $n=|S|$ for its cardinality. A random variable $X$ with this law has support of a probability distribution $S$ and probability mass functionThe masses sum to $n(1/n)=1$. Conversely, if all $n$ masses equal $p$, their sum is $np=1$, so necessarily $p=1/n$. Thus equal chances determine the whole law.^[ref]

Counting now computes an event's probability: for any set $A$ of possible values,In particular, when $A\subseteq S$, the answer is $|A|/|S|$. The intersection matters: values outside the support of a probability distribution contribute zero. This turns a probability question into a combinatorics question, provided that equal chances are justified by the model.

For an ideal fair six-sided die, $S=\{1,2,3,4,5,6\}$ and each face has probability $1/6$. The event of an even integer is $\{2,4,6\}$, so its probability is $3/6=1/2$; the event $X\ge 5$ has probability $2/6=1/3$. Direct summation gives the expected value $\mathbb{E}X=21/6=7/2$ and the variance $\mathrm{Var}(X)=91/6-(7/2{)}^2=35/12$. The mean $7/2$ is a balance point between possible outcomes. These are exact consequences of stipulated fairness, rather than measured frequencies from physical dice.

Uniformity describes probabilities, not distances between values. For a second constructed model, stipulate equal-chance selection from $S=\{1,2,4,8\}$. Every value has probability $1/4$, despite the unequal gaps $1,2,4$. Here $\mathbb{P}(X\ge 4)=2/4=1/2$, while the expected value and variance areNeither the midpoint of the extreme values, $9/2$, nor a formula using only the cardinality gives these moments. For a general numerical support of a probability distribution, use its actual values:

Choosing an item from a finite list with equal chances is a basic building block of simple random sampling. A bijection that relabels the items preserves equal probabilities, although changing numerical labels can change the expected value and variance. A function that merges labels can destroy uniformity: for the fair-die model, $Y=\min (X,3)$ has masses $1/6,1/6,4/6$ at $1,2,3$, since four faces map to three. Always count the original equally likely outcomes.

An indicator random variable for membership in a set $A\subseteq S$ has a Bernoulli distribution with parameter $|A|/n$; counting that event over $r$ independent repetitions gives a binomial distribution with parameters $r$ and $|A|/n$. Equal chances among individual values need not produce equal chances among aggregated counts.^[ref]

Suppose the support of a probability distribution consists of all consecutive integers from $a$ to $b$, including both endpoints, with $a\le b$. Its cardinality is $n=b-a+1$, and a discrete uniform distribution on it satisfiesFor a short derivation, set $K=X-a$, whose possible values are $0,\dots ,n-1$. The finite sums giveand henceAdding $a$ shifts the expected value by $a$ and leaves the variance unchanged. For completeness, the first sum follows by pairing $k$ with $n-1-k$. For the second, sum $(k+1{)}^3-k^3=3k^2+3k+1$ from $k=0$ to $n-1$: the left side is $n^3$, so inserting the first sum gives the stated result.

The edge case $a=b$ has $n=1$: $X=a$ with probability one, expected value $a$, and variance zero. On an arithmetic progression $\{a,a+h,\dots ,a+(n-1)h\}$ with $h>0$, the same argument instead gives expected value $a+h(n-1)/2$ and variance $h^2(n^2-1)/12$. Equal spacing is the extra hypothesis behind these formulas; the discrete uniform distribution on $\{1,2,4,8\}$ requires the general sums above.

Let the numerical support of a probability distribution be $x_1<\cdots <x_n$. Its cumulative distribution function counts how many values have been passed:It is zero below $x_1$, equals $j/n$ on $x_j\le t<x_{j+1}$ for $1\le j<n$, and is one at and above $x_n$. Every jump is $1/n$, even when the horizontal gaps differ.

For inverse transform sampling, take an ideal continuous uniform distribution for $U$ on $[0,1)$. Partition that interval into $n$ intervals of width $1/n$ and outputEach interval has probability $1/n$, proving the desired discrete uniform distribution. Using the floor function, the index is $j=1+\lfloor nU\rfloor$; for consecutive integer values the output is $X=a+\lfloor nU\rfloor$. With the usual quantile function convention $Q(u)=\inf \{t:F_X(t)\ge u\}$, one instead writes $Q(u)=x_{\lceil nu\rceil }$ for $0<u\le 1$, using the ceiling function. The endpoint conventions differ only at a finite set of points with probability zero under the ideal continuous uniform distribution.

For $S=\{1,2,4,8\}$, the four intervals $[0,1/4)$, $[1/4,1/2)$, $[1/2,3/4)$, and $[3/4,1)$ select $1,2,4,8$, respectively. Thus $U=3/10$ selects $2$, while $U=9/10$ selects $8$. The upper half of the interval selects values at least four, recovering probability $1/2$. Equal widths refer to the sampling probability coordinate, not to distances between output values. This is an exact mathematical construction assuming an ideal continuous uniform distribution; a finite computer random-number source needs its own justification of equal output chances.

An ordered sample from $n$ equally likely values is nondecreasing exactly when it is the unique sorted representative of its multiplicities. Stars and bars counts the nonnegative multiplicities summing to $r$; repeated values are included automatically.

A Bernoulli random variable records one success as $1$ and one failure as $0$. For $0\le p\le 1$, its probability mass function iswith zero mass elsewhere. The terms success and failure merely name outcomes; success need not be desirable. Any event $A$ produces such a variable through its indicator random variable $B=1_A$, with $p=\mathbb{P}(A)$. A single Bernoulli distribution requires no independence assumption; independence becomes relevant when several trials are combined.

Because $B^2=B$, the expected value and variance follow immediately:For a constructed trial with $p=0.3$, these are $0.3$ and $0.21$. The variance is greatest at $p=1/2$, where it equals $1/4$, since $p(1-p)=1/4-(p-1/2{)}^2$. At $p=0$ or $p=1$, the outcome is certain and the variance vanishes.

The beauty of an indicator random variable is that counting becomes addition: summing such indicators counts successes, and the linearity of expectation gives the expected count even when the indicators are dependent. With independence and a shared $p$, the full count law is the binomial distribution. These models are summarized in Penn State STAT 504, discrete distributions.

A historical anchor is Bernoulli's posthumous Ars conjectandi: its original title page identifies the author and records publication at Basel in 1713. This documents the book's publication, rather than establishing priority for the modern name Bernoulli distribution. See Ars conjectandi, original title page, ETH Library.

On a cyclic sequence of $n$ independent Bernoulli random variables with success probability $p$, count all runs of $k$ consecutive successes, allowing overlaps and taking $1\le k\le n/2$. The count has expected value $n{p}^k$. Its variance is the displayed expression: each starting indicator has variance $p^k(1-p^k)$; two starts at cyclic distance $j<k$ have joint probability $p^{k+j}$; nonoverlapping starts are independent. There are $2n$ ordered overlapping pairs at each such distance, because the two ranges do not meet when $k\le n/2$.

For $p\le 1/2$, summing a geometric series gives $\mathrm{Var}X\le n{p}^k(1+2p/(1-p))\le 3n{p}^k$. Markov's inequality therefore proves absence with high probability when $n{p}^k\to 0$, and Chebyshev's inequality proves existence and relative concentration when $n{p}^k\to \infty$. This remains valid for varying probabilities eventually at most one half.

A Bernoulli string is a finite sequence of independent binary digits, each taking value one with a specified probability. Unless stated otherwise, all positions use the same probability.

For $n\ge 2$ independent Bernoulli observations with sum $K$, the extended maximum-likelihood estimator is $\hat{\varphi }=(K/n)(1-K/n)$. Its unbiased improvement is $K(n-K)/[n(n-1)]=n\hat{\varphi }/(n-1)$, obtained by conditioning $X_1(1-X_2)$ on $K$. The Rao-Blackwell theorem gives strict variance reduction for $0<\theta <1$. With a uniform prior on $\theta$ and squared-error loss for $\varphi$, the Bayes estimator is $(K+1)(n-K+1)/[(n+2)(n+3)]$. For parameter space strictly $(0,1)$, samples with $K=0$ or $n$ have only a boundary likelihood supremum, not an attained maximum.

A random experiment with two outcomes, success and failure, whose success indicator has a Bernoulli distribution. Repeated trials sharing success probability $\theta$ give a binomial distribution for their success count if they are independent conditional on $\theta$; integrating over an uncertain common $\theta$ generally makes the trials dependent marginally.

If an event occurs with probability $p$ and is independently retained with conditional probability $q$, its retained indicator is Bernoulli with probability $pq$. Applying this independently to a binomial count turns $\mathrm{Binomial}(n,p)$ into $\mathrm{Binomial}(n,pq)$.

Consider successive independent Bernoulli trials with the same success probability $0<p\le 1$. A geometric distribution models waiting for their first success. Two conventions coexist, so always say what is counted. Let $T$ count all trials up to and including the successful trial, and let $F=T-1$ count preceding failures. Their probability mass functions areThe factors describe failures followed by one success; independence permits multiplication. Summing the geometric series verifies that each law has total mass one. Their expected values differ by one, while shifting by a constant leaves the variance unchanged:The positive convention and these moments are also given by Penn State STAT 414.^[ref]

For a constructed retry mechanism with independent attempts and $p=0.3$, success on attempt four has probability $\mathbb{P}(T=4)=0.7^3(0.3)=0.1029$. More than four attempts are needed precisely when the first four fail: $\mathbb{P}(T>4)=0.7^4=0.2401$. The expected values are $\mathbb{E}T=10/3$ and $\mathbb{E}F=7/3$, and the common variance is $70/9\approx 7.7778$. The large spread explains why the average waiting count is not a deadline.

The two probability mass functions have identical heights with different labels: $T=4$ and $F=3$ describe the same event. For $0<p<1$, consecutive masses have ratio $1-p$, explaining the name geometric distribution. The support of a probability distribution is the positive integers for $T$ and the nonnegative integers for $F$. At $p=1$, it collapses to $T=1$ and $F=0$, both with variance zero; interpret an empty product, including $(1-p{)}^0$, as one. These counts concern attempts; converting them into elapsed time requires specifying the time spent per attempt.

The survival function makes the counting convention especially visible. Put $q=1-p$. For nonnegative integers $n$, and for $k\ge 1$,The event $T>n$ requires $n$ failures, whereas $T\ge n$ requires only $n-1$ when $n\ge 1$. For the constructed $p=0.3$ mechanism, $\mathbb{P}(T\ge 4)=0.343$ differs from $\mathbb{P}(T>4)=0.2401$. The geometric success deadline uses the latter tail to control the chance of still waiting.

The striking memorylessness of the geometric distribution says that, for nonnegative integers $m,r$ with $\mathbb{P}(T>m)>0$,After five failures, the conditional probability of requiring more than two additional attempts is still $0.7^2=0.49$. The analogous zero-based identity uses $\mathbb{P}(F\ge m+r\mid F\ge m)=\mathbb{P}(F\ge r)$; keeping the inequalities straight avoids an off-by-one error. This property follows from fresh independent trials with unchanged $p$; learning or changing conditions can destroy it. At $p=0$, success never occurs, so there is no proper finite waiting-count law.

For independent positive-support geometric random variables with success probabilities $p_i$, all must exceed $k$ for their minimum to exceed $k$. The resulting survival function is ${\prod }_i(1-p_i{)}^k$. This is the positive-support geometric distribution with the displayed success probability. Independence is needed for multiplying the survival probabilities.

The same argument works for any integer base $b\ge 2$. Suppose $N$ has geometric distribution $\mathbb{P}(N=n)=(1-q)q^n$, $n\ge 0$, with $0<q<1$. Its Euclidean division $N=bY+X$ gives $0\le X<b$ and $Y\ge 0$. Their joint probability mass function isThe factors are normalized probability mass functions, so the final digit $X$ and quotient $Y$ are independent. The quotient again has geometric distribution, with success probability $1-q^b$. If $N$ is the integer part of an exponential random variable of rate $\lambda$, take $q=e^{-\lambda }$.

Suppose a contest uses $N_0$ trials initially and ends there with probability $1-\alpha$. Conditional on an initial tie, independent further rounds each use $\ell$ trials and resolve the contest with a fixed probability $0<r\le 1$. The number $J$ of further rounds, conditional on that tie, has a geometric distribution: $\mathrm{Pr}(J=j\mid \text{tie})=(1-r{)}^{j-1}r$ for $j\ge 1$. Thus the total number $N$ of trials has an atom $1-\alpha$ at $N_0$ and the displayed probabilities thereafter. The geometric series sums to $\alpha$, so termination has probability one, and the expected value is $\mathbb{E}[N]=N_0+\ell \alpha /r$. The displayed distribution requires independence of the future rounds from the initial tie.

For the positive-integer geometric distribution with success probability $0<p\le 1$, the displayed identity holds for nonnegative integers $m,r$ whenever the conditioning event has positive probability. The first $m$ attempts have failed; future independent attempts use the same success probability. Equivalently, divide the tail $(1-p{)}^{m+r}$ by $(1-p{)}^m$. For a zero-based failures count $F=T-1$, use $\mathbb{P}(F\ge m+r\mid F\ge m)=\mathbb{P}(F\ge r)$. Constant success probability and independence are essential: accumulated wear or learning would require a different model.

The full remaining-count law is unchanged, not only one tail probability. With $0<p<1$, after $m$ failures set $R=T-m$ on the event $T>m$. For $r=1,2,\dots$, its probability mass function under this conditional probability isHere independence makes the future trials unaffected by the observed failures, and the unchanged success probability makes their law identical to the original one. Consequently $\mathbb{E}[T-m\mid T>m]=1/p$, while $\mathbb{E}[T\mid T>m]=m+1/p$. For the constructed $p=0.3$ mechanism, five failures leave a mean of $10/3$ more attempts, making the conditional mean total $25/3$; the five already spent are still counted.

The same mechanism has constant discrete hazard:Thus each reached attempt has the same chance of success. This differs from the decreasing unconditional probability $\mathbb{P}(T=k)$: later success requires surviving earlier attempts. At $p=1$, only conditioning on an event of positive probability is allowed: $T>m$ permits only $m=0$, and $T\ge k$ only $k=1$.

Among proper laws on the positive integers, memorylessness of the geometric distribution also characterizes the geometric distribution. Write $S(n)=\mathbb{P}(T>n)$. The identity gives $S(m+r)=S(m)S(r)$; if $S(m)=0$, both sides vanish anyway. Since $S(0)=1$, induction yields $S(n)=S(1{)}^n$. Properness excludes $S(1)=1$, so setting $p=1-S(1)>0$ recovers the geometric distribution, including $p=1$.^[ref]

The retry example stipulates independent Bernoulli trials with a known constant $p$; it is not evidence that a real retry system behaves this way. Shared changing conditions or adapting attempts can alter the next success probability. Even constant individual success probabilities alone do not imply independence.

For an original contrasting model, uniformly shuffle one success card and three failure cards, then draw by sampling without replacement. Its success position $U$ has the discrete uniform distribution on $\{1,2,3,4\}$. Initially the success probability is $1/4$; after one failure it is $1/3$. In particular,This shows concretely why sampling without replacement need not be independent and why the remaining wait can change. Every draw still has unconditional success probability $1/4$ when all four positions are considered; the relevant discrete hazard changes after failures.

How many attempts give at least a chosen success probability $0<\alpha <1$? For a positive-integer geometric distribution with $0<p<1$, completion by attempt $N$ means $T\le N$, soThe logarithm $\log q$ is negative, which reverses the inequality when dividing. The least integer meeting the target is therefore obtained with the ceiling function:For our constructed independent retry mechanism with $p=0.3$ and $\alpha =0.95$,To verify minimality directly, eight attempts give $\mathbb{P}(T\le 8)=1-0.7^8=0.94235199<0.95$, whereas nine give $\mathbb{P}(T\le 9)=1-0.7^9=0.959646393\ge 0.95$. Under the zero-based convention, the same completion event is $F\le 8$, with failure to complete given by $F\ge 9$; saying $F\le 9$ would allow ten attempts. A 95% deadline controls a tail probability, while the expected value $10/3$ describes an average.

At $p=1$ success occurs on the first attempt, so $N_{\alpha }=1$; the logarithm formula is inapplicable. At $p=0$ no finite deadline achieves a positive target. For $0<p<1$, no finite deadline guarantees success with probability one because $q^N>0$. A retry cap at $N$ produces the capped geometric waiting time $\min (T,N)$ as the number of attempts actually spent; reaching the cap can mean either success on the last allowed attempt or failure of all $N$ attempts.

Start a Markov chain at a nonabsorbing state $i$. If each departure from $i$ has probability $p>0$ of absorption before the next return, the Strong Markov property makes the number of visits to $i$, including the initial one, a positive-integer geometric random variable of parameter $p$. For a continuous-time Markov chain whose holding times at $i$ are independent rate-${\lambda }_i$ exponentials, independently of the embedded jump chain, the total occupation time at $i$ is a sum of $K$ such holding times and has expected value $1/(p{\lambda }_i)$.

Independently retain each event of a zero-based geometric distribution count with probability $\alpha$. Conditional on the original count, the retained count is binomial, so its probability generating function is $p/[1-(1-p)(1-\alpha +\alpha z)]$. This is again a zero-based geometric distribution, with success parameter $p_{\alpha }$ and mean $\alpha (1-p)/p$. In excess of loss reinsurance, $\alpha$ is the probability that a claim exceeds the retention.

Let $\mathbb{P}(X=n)=p(1-p{)}^n$ for $n\ge 0$ and $Y\mid X=n\sim \mathrm{Binomial}(n,q)$, with $0<p,q<1$. Write $D=p+q-pq$. Summing the joint probability mass function with the differentiated geometric series identity ${\sum }_{n=k}^{\infty }\left(\genfrac{}{}{0ex}{}{n}{k}\right)t^{n-k}=(1-t{)}^{-k-1}$ gives $\mathbb{P}(Y=k)=(p/D)((1-p)q/D{)}^k$. By Bayes' theorem,Thus $X-k$, given $Y=k$, has the failure-count negative binomial distribution for $k+1$ successes and success parameter $D$. Its conditional expectation is $k+(k+1)(1-D)/D$ for $X$ itself. The shift by $k$, the number of retained successes, must be retained when identifying the posterior distribution.

For a positive-integer geometric distribution $P(N=j)=p{q}^{j-1}$ with $q=1-p$, the capped time has masses $p{q}^{j-1}$ for $1\le j<k$ and $q^{k-1}$ at $k$. The last mass includes all later arrivals, not only $N=k$. Its probability generating function and expected value areThe expectation follows either by differentiating the PGF or summing the tail probabilities up to $k$.

When independent uniform draws are made from $n$ types, the time $T_n$ until every type has appeared decomposes as a sum of independent geometric waiting times with parametersConsequentlyand Chebyshev's inequality gives $T_n/(n\log n)\to 1$ in probability.

For independent coupon labels arriving at rate $\lambda$, Poisson thinning makes the type-specific first arrival times independent exponentials of rates $\lambda p_j$. Completion time is their maximum. Its distribution is $\mathbb{P}(T<t)={\prod }_j(1-e^{-\lambda p_{j}t})$. The completion count $L$ depends only on the labels and is independent of the exponential interarrival sequence. Therefore $T={\sum }_{k\ge 1}{E}_k{1}_{\{L\ge k\}}$ and nonnegative integration gives the displayed identity. Completion count and its expectation do not depend on arrival rate.

In independent trials with two outcomes of probabilities $p$ and $q=1-p$, let $N$ include the first trial and the trial that first completes the pair. Conditional on the first outcome, $N-1$ has a geometric distribution of parameter $q$ or $p$, with mixture weights $p,q$. The law of total expectation and law of total variance giveThe final term in the unsimplified variance is the variance of the two conditional means; omitting it is incorrect unless $p=q$. Both outcomes must have positive probability for these finite formulas.

For uniform independent draws of $n$ coupon types, the waiting times with $r$ unseen types remaining are independent positive-support geometric distributions of parameter $r/n$. Summing their means gives $n{\sum }_{r=1}^{n}1/r$, and summing their variances gives the displayed formula. Independence follows from fresh draws after each discovery and the fact that the next stage's conditional distribution depends only on the count of remaining types.

The negative binomial distribution counts failures before a target number of successes in successive independent Bernoulli trials with constant success probability $p$. In this stopping model, $r$ is a positive integer and $0<p\le 1$. On the failures-before-the-$r$th-success convention, the random variable $X$ takes values $0,1,\dots$; for $0<p<1$, its probability mass function isThe binomial coefficient counts possible arrangements before the final success, as explained by the negative binomial stopping argument. At $p=1$, every trial succeeds: $X=0$ with probability one, so its expected value and variance are both zero. This handles the endpoint without needing to interpret $0^0$. At $p=0$, the target is never reached and there is no proper finite waiting-count law.

For a worked example, toss a fair coin until the second head, calling heads $S$ and tails $F$. Thus $r=2$ and $p=1/2$. Exactly two failures means that the second success is on trial four. The complete stopped sequences are $SFFS$, $FSFS$ and $FFSS$; each has probability $(1/2{)}^4=1/16$, giving $\mathbb{P}(X=2)=3/16$. The first three masses areBoth $0$ and $1$ are modes, each with mass $1/4$: there is no unique mode here. Later masses decrease, since $\mathbb{P}(X=x+1)/\mathbb{P}(X=x)=(x+2)/(2x+2)<1$ for $x\ge 1$.

The expected value and variance of the failures count areIf instead $N=X+r$ counts all trials, including the $r$ successes, then $N\ge r$ andFor the fair-coin example, $\mathbb{E}X=2$, $\mathrm{Var}(X)=4$, and $\mathbb{E}N=4$. Shifting the count changes its expected value but preserves its variance. When $r=1$, $X$ has the failures-count geometric distribution, while $N=X+1$ has the all-trials geometric distribution. The two conventions and the moments are treated in Kyle Siegrist, The Negative Binomial Distribution, Random Services.

The negative binomial distribution is useful when a procedure runs until it collects a target number of successes: for example, obtaining $r$ usable samples from independent attempts with a stable acceptance probability. A binomial distribution instead counts successes in a fixed number of trials. The attractive connection is that these two experimental questions can be answered from the same trial sequence, using the negative binomial stopping argument. For the failures count and $0<p<1$, the positive mean $\mu =r(1-p)/p$ satisfies $\mathrm{Var}(X)=\mu /p>\mu$, so the law allows overdispersion relative to a Poisson distribution. At $p=1$, both quantities vanish and the inequality is not strict. The separate Poisson-gamma mixture explains another way this count law arises; its noninteger shape parameters do not represent a literal target number of successes.

When each observation counts untagged captures before the $r$th tagged capture with immediate replacement, its negative binomial distribution has success probability $p=k/N$. For $n$ independent runs, the log-likelihood is $nr\log p+({\sum }_i{x}_i)\log (1-p)$ plus a constant. Differentiation gives the displayed estimator and expected Fisher information. For an interior true parameter, its asymptotic variance is $p^2(1-p)/(nr)$. A confidence interval $(L,U)$ for $p$ transforms to $(k/U,k/L)$ for the population size, with endpoint order reversed.