Geometric Sampling

Why Geometric Sampling Has Two Conventions

A geometric random variable counts how long it takes to obtain the first success in a sequence of independent trials. The count may include the successful trial, or it may count only the failures before that success. Both conventions describe the same waiting process, but their supports begin at different integers. In simulation, that difference changes the output by one, so the convention must be stated before applying an inverse-transform formula.

Assume each trial is a success with probability \(p\), where \(0<p<1\), and a failure with probability \(q=1-p\). The trials are independent and have the same success probability. Let \(K\) count failures before the first success, and let \(T\) count trials through and including the first success. Thus \(K\) takes values \(0,1,2,\ldots\), while \(T\) takes values \(1,2,3,\ldots\), and \(T=K+1\).

Definition: Under the failures-before-success convention, \(K\) has geometric probabilities \(P(K=k)=q^k p\) for \(k=0,1,2,\ldots\). Under the trials-until-success convention, \(T\) has probabilities \(P(T=t)=q^{t-1}p\) for \(t=1,2,3,\ldots\). In both definitions, \(p\) is the probability of success on each trial.

Deriving the Inverse-Transform Algorithms

Let \(U\) be uniform on the open interval \((0,1)\). For a discrete random variable, inverse-transform sampling assigns \(U\) to the value whose cumulative probability interval contains it. The geometric cumulative distribution functions follow by adding the probabilities of obtaining a success within the stated number of trials.

P(K\leq k)=1-q^{k+1}\quad(k\geq 0), \qquad P(T\leq t)=1-q^t\quad(t\geq 1).

For example, \(K\leq k\) means that the first success occurs within the first \(k+1\) trials. The complementary event is that all \(k+1\) trials fail, with probability \(q^{k+1}\). Similarly, \(T\leq t\) means that a success occurs within the first \(t\) trials, whose complement has probability \(q^t\).

To invert either cumulative distribution, find the smallest supported integer whose cumulative probability is at least \(U\). For \(K\), this requires \(U\leq 1-q^{k+1}\), or \(1-U\geq q^{k+1}\). Taking logarithms and remembering that \(\log q<0\) reverses the inequality when dividing gives \(k+1\geq \log(1-U)/\log q\). The smallest integer \(k+1\) satisfying this is the ceiling of that ratio.

r=\frac{\log(1-U)}{\log q}, \qquad K=\lceil r\rceil-1, \qquad T=\lceil r\rceil.

The two formulas differ by exactly one because \(T=K+1\). The ceiling is important: it selects the smallest integer at or above \(r\). If \(r\) is exactly an integer, the formulas assign \(U\) to the cumulative probability boundary consistently with the definition “smallest integer whose cumulative probability is at least \(U\).” Such exact boundaries have probability zero for a continuous uniform variable, but a clear convention avoids ambiguity.

Specify the count.
Decide whether the required output is failures before success, \(K\), or trials through success, \(T\).

Set the probabilities.
Use the per-trial success probability \(p\) and failure probability \(q=1-p\).

Transform the uniform input.
For \(U\in(0,1)\), calculate \(r=\log(1-U)/\log q\).

Apply the support convention.
Return \(K=\lceil r\rceil-1\) or \(T=\lceil r\rceil\), then check that the result is in the appropriate support.

Worked Example: Sampling Both Geometric Counts From One Uniform

A hypothetical claim-monitoring process records independent daily indicators, each with success probability \(p=0.20\). Given \(U=0.35\), generate both the number \(K\) of failures before the first success and the number \(T\) of days through the first success. Check each result using cumulative probabilities.

Method. This is inverse-transform sampling. The failure probability is \(q=1-0.20=0.80\). First calculate \(r=\log(1-U)/\log q=\log(0.65)/\log(0.80)\approx1.931\), to three decimal places.

For the failures-before-success convention, \(K=\lceil1.931\rceil-1=2-1=1\). For the trials-until-success convention, \(T=\lceil1.931\rceil=2\). These agree with \(T=K+1\).

Probability check for \(K\). The cumulative probabilities are \(P(K\leq0)=1-0.80=0.20\) and \(P(K\leq1)=1-0.80^2=0.36\). Since \(0.20<0.35\leq0.36\), the uniform input belongs to the interval for \(K=1\).

Probability check for \(T\). We have \(P(T\leq1)=0.20\) and \(P(T\leq2)=1-0.80^2=0.36\). Thus \(0.20<0.35\leq0.36\), so the generated trial count is \(T=2\).

Common mistake avoided. Returning \(2\) for \(K\) would count the successful day as a failure. The stated \(K\) convention counts only the one failed day; the successful day is included only in \(T\).

Checking Outcomes and Expected Counts

A sampled value should be consistent with the probability intervals, not merely with the algebraic formula. For either convention, the probability of a particular count is the length of its corresponding interval of uniform values. For instance, under the \(T\) convention, \(T=t\) when the first \(t-1\) trials fail and the \(t\)th succeeds, so its probability is \(q^{t-1}p\).

The expected counts also provide a useful check on the parameterization. For any nonnegative integer-valued variable \(K\), its expectation can be written as the sum of its tail probabilities. Here \(P(K\geq j)=q^j\) for \(j\geq1\), because at least \(j\) failures means the first \(j\) trials all fail. Therefore,

E[K]=\sum_{j=1}^{\infty}P(K\geq j) =\sum_{j=1}^{\infty}q^j =\frac{q}{1-q} =\frac{q}{p}.

The last equality uses the sum of a convergent geometric series and \(1-q=p\). Since \(T=K+1\), linearity of expectation gives \(E[T]=E[K]+1=q/p+1=1/p\). These formulas are checks on the interpretation: when success is less likely, both waiting counts increase; and the trials count is always one larger than the failures count.

Worked Example: Checking Probabilities and Means for a Geometric Model

A hypothetical inspection procedure finds a specified defect on each independently inspected component with probability \(p=0.25\). Let \(K\) be the number of defect-free components inspected before finding the first defective one, and let \(T\) be the total number inspected through the first defective one. Find \(P(K=2)\), \(P(T\leq3)\), and both expected counts.

Method. Use the failures-before-success probability formula for \(P(K=2)\), the cumulative formula for \(T\), and the tail-sum results for the means. Here \(q=1-p=0.75\).

For exactly two failures followed by a success, \(P(K=2)=q^2p=(0.75)^2(0.25)=0.5625(0.25)=0.140625\).

The event \(T\leq3\) means that at least one success occurs in the first three inspections. Its complement is three consecutive failures, so \(P(T\leq3)=1-q^3=1-(0.75)^3=1-0.421875=0.578125\).

The expected number of failures before success is \(E[K]=q/p=0.75/0.25=3\). The expected total number of inspections is \(E[T]=1/p=1/0.25=4\), also equal to \(E[K]+1=3+1=4\).

Check. The point probability is between zero and one, the cumulative probability \(0.578125\) is between zero and one, and the two expected counts differ by one. The values are consistent with a success probability of only one quarter.

Worked Example: Applying the Formula to Several Uniform Inputs

A hypothetical screening system has independent daily success indicators with probability \(p=0.40\). For uniform inputs \(U=0.08\), \(0.52\), and \(0.94\), generate the trials-until-success counts \(T\). Verify each result by locating the input between cumulative probabilities.

Method. Here \(q=0.60\), so use \(r=\log(1-U)/\log(0.60)\) and \(T=\lceil r\rceil\).

For \(U=0.08\), \(r=\log(0.92)/\log(0.60)\approx0.163\), so \(T=1\). The first cumulative probability is \(P(T\leq1)=0.40\), and \(0.08\leq0.40\), confirming the result.

For \(U=0.52\), \(r=\log(0.48)/\log(0.60)\approx1.437\), so \(T=2\). The cumulative probabilities are \(P(T\leq1)=0.40\) and \(P(T\leq2)=1-(0.60)^2=0.64\). Since \(0.40<0.52\leq0.64\), the result is \(T=2\).

For \(U=0.94\), \(r=\log(0.06)/\log(0.60)\approx5.507\), so \(T=6\). The cumulative probabilities around the result are \(P(T\leq5)=1-(0.60)^5=0.92224\) and \(P(T\leq6)=1-(0.60)^6=0.953344\). Since \(0.92224<0.94\leq0.953344\), the result is \(T=6\).

Check. The generated counts are \(1,2,6\), all in the positive-integer support for \(T\). The large input maps to a larger waiting time, as expected from the cumulative-probability intervals.

Common Traps and Practical Checks

Shifting the support incorrectly. \(K=0\) is possible because the first trial may succeed. \(T=0\) is impossible because at least one trial is needed. Use \(K=\lceil r\rceil-1\) and \(T=\lceil r\rceil\).
Using the failure probability as the success probability. The parameter \(p\) in these definitions is the per-trial success probability; \(q=1-p\) is used in the powers and logarithm denominator.
Ignoring the negative logarithm denominator. Since \(0<q<1\), \(\log q<0\). Dividing an inequality by it reverses the inequality. The ceiling formulas follow from that reversal.
Using the wrong logarithm ratio. With the stated inverse-CDF construction, the numerator is \(\log(1-U)\). The ratio is nonnegative because both logarithms are negative.
Failing to verify support and probabilities. Check \(K\geq0\) or \(T\geq1\), then confirm that \(U\) lies between the cumulative probabilities immediately below and at the proposed count.

The derivation assumes \(0<p<1\) and \(U\in(0,1)\). If \(p=1\), success occurs on the first trial with certainty, so \(K=0\) and \(T=1\); the logarithmic formula is not used because \(q=0\). If \(p=0\), success never occurs, so there is no finite first-success count. In practical implementations, uniform-number generators may permit endpoint values; the simulation procedure should map or avoid those endpoints so the logarithm is defined and the result is finite.

Key takeaway: Set \(q=1-p\), compute \(r=\log(1-U)/\log q\), and then apply the stated support convention: \(K=\lceil r\rceil-1\) for failures before success, or \(T=\lceil r\rceil\) for trials through success. The checks \(E[K]=q/p\) and \(E[T]=1/p\) help catch a one-unit shift.

Check Your Understanding

For each problem, identify the support convention before applying the sampling or probability formula.

A hypothetical process has independent trials with success probability \(p=0.30\). For \(U=0.50\), find the failures-before-success count \(K\) using inverse transformation. (Answer: \(K=1\))
For the same success probability \(p=0.30\), find \(P(T=3)\), where \(T\) counts trials through the first success. (Answer: \(0.1470\))
A hypothetical device test succeeds independently with probability \(p=0.10\) on each test. Find \(P(T\leq4)\). (Answer: \(0.3439\))
For a geometric model with \(p=0.40\), find the expected failures before success and the expected total number of trials. (Answer: \(E[K]=1.5\), \(E[T]=2.5\))
For \(p=0.25\) and \(U=0.90\), generate \(T\), then verify it using the two adjacent cumulative probabilities. (Answer: \(T=9\); \(P(T\leq8)=0.8999\) and \(P(T\leq9)=0.9249\), to four decimals)

What You'll Learn