Bernoulli Renewals on a Discrete Time Grid

Independent Events on an Integer Grid

A renewal process can be built from repeated independent opportunities for an event. On an integer time grid, suppose an event occurs independently at each time with the same probability $p$. The waiting time from one event to the next is then geometric, and the number of events by time $n$ has a particularly simple distribution. The independence assumption matters: equal event probabilities by themselves are not enough.

Work on a probability space $(\Omega,\mathcal{F},\mathbb{P})$. Let $Y_m$, for integer times $m\ge1$, be independent Bernoulli random variables with $\mathbb{P}(Y_m=1)=p$ and $\mathbb{P}(Y_m=0)=1-p$, where $0<p\le1$. Here $Y_m=1$ means a renewal occurs at time $m$. The discrete-time filtration is $\mathcal{F}_n=\sigma(Y_1,\ldots,Y_n)$, with $\mathcal{F}_0=\{\varnothing,\Omega\}$. The renewal count $N(n)=\sum_{m=1}^nY_m$ takes values in the countable state space $S=\{0,1,2,\ldots\}$. Set $N(0)=0$.

Definition: The renewal epochs are $S_0=0$ and $S_k=\inf\{m\ge1:N(m)=k\}$ for $k\ge1$, with $\inf\varnothing=\infty$. When $p>0$, all these epochs are finite almost surely. The interarrival time $X_k=S_k-S_{k-1}$ is the number of grid steps from renewal $k-1$ to renewal $k$. The count by integer time $n$ is equivalently $N(n)=\max\{k\ge0:S_k\le n\}$.

The two descriptions of $N(n)$ use the same endpoint convention: an event at time $n$ is included. Because $p>0$, the probability of no event in the first $r$ grid times is $(1-p)^r$, which tends to $0$ as $r\to\infty$. Thus the first renewal occurs in finite time almost surely; applying the same argument after each finite renewal epoch gives finite successive epochs almost surely. If $p=1$, every time is a renewal and each interarrival time is exactly $1$.

Geometric Interarrivals and the Count Law

Theorem: For independent Bernoulli events with common probability $p$, $0<p\le1$, the interarrival times $X_1,X_2,\ldots$ are independent and have the geometric distribution on $\{1,2,\ldots\}$: $$ \mathbb{P}(X_k=r)=(1-p)^{r-1}p,\qquad r\ge1. $$ For every integer $n\ge0$, the renewal count has the binomial distribution $$ \mathbb{P}(N(n)=k)=\binom{n}{k}p^k(1-p)^{n-k},\qquad 0\le k\le n. $$ In particular, $\mathbb{E}[N(n)]=np$ and $\operatorname{Var}(N(n))=np(1-p)$.

Proof. Write $q=1-p$. Fix any positive integers $r_1,\ldots,r_\ell$. The event $X_1=r_1,\ldots,X_\ell=r_\ell$ specifies a consecutive sequence of grid outcomes: there are $r_1-1$ failures and then one success, followed by $r_2-1$ failures and then a success, continuing in this way through the $\ell$th success. Independence of the $Y_m$ therefore gives $$ \mathbb{P}(X_1=r_1,\ldots,X_\ell=r_\ell) =\prod_{a=1}^{\ell}q^{r_a-1}p. $$ Also, for each $r\ge1$, $\sum_{r\ge1}q^{r-1}p=1$, since $0\le q<1$. The displayed joint probability is a product of probability mass functions, so the $X_k$ are independent geometric random variables with the stated law. This argument includes $p=1$, when the mass is $1$ at $r=1$ and $0$ at every $r>1$.

For the count, the definition gives $N(n)=\sum_{m=1}^nY_m$. To have exactly $k$ renewals, choose which $k$ of the $n$ independent trials are successes. Each such choice has probability $p^kq^{n-k}$, and there are $\binom{n}{k}$ choices. This proves the count formula, including $n=0$, when the only possible value is $k=0$.

For the moments, $\mathbb{E}[Y_m]=p$ and $\operatorname{Var}(Y_m)=p(1-p)$, since $Y_m^2=Y_m$. By linearity of expectation, $\mathbb{E}[N(n)]=\sum_{m=1}^n\mathbb{E}[Y_m]=np$. Independence gives $\operatorname{Cov}(Y_a,Y_b)=0$ for $a\ne b$, so $$ \operatorname{Var}(N(n)) =\sum_{m=1}^n\operatorname{Var}(Y_m) +2\sum_{1\le a<b\le n}\operatorname{Cov}(Y_a,Y_b) =np(1-p). $$ When $n=0$, both sums are empty and the count is the constant zero, so the same formulas hold. $\square$

The geometric interarrival description and the binomial count description answer different questions about the same process. A single gap has a geometric law, while the number of successes in a fixed number of trials has a binomial law. In particular, one should not treat the interarrival times as the count itself: the count by time $n$ is determined by how many successive gaps fit within $n$, and the direct trial representation gives its distribution most efficiently.

Worked Example: The Full Count Distribution for Four Grid Steps

Suppose the event probability at each time is $p=\tfrac13$, independently across times. Find the distribution, expectation, and variance of $N(4)$.

Each of the four trial outcomes has probability $p=\tfrac13$ of success and $q=1-p=\tfrac23$ of failure. The count formula gives, for $k=0,1,2,3,4$, $$ \begin{aligned} \mathbb{P}(N(4)=0)&=\binom40\left(\tfrac13\right)^0\left(\tfrac23\right)^4=\tfrac{16}{81},\\ \mathbb{P}(N(4)=1)&=\binom41\left(\tfrac13\right)^1\left(\tfrac23\right)^3=\tfrac{32}{81},\\ \mathbb{P}(N(4)=2)&=\binom42\left(\tfrac13\right)^2\left(\tfrac23\right)^2=\tfrac{24}{81},\\ \mathbb{P}(N(4)=3)&=\binom43\left(\tfrac13\right)^3\left(\tfrac23\right)^1=\tfrac{8}{81},\\ \mathbb{P}(N(4)=4)&=\binom44\left(\tfrac13\right)^4\left(\tfrac23\right)^0=\tfrac{1}{81}. \end{aligned} $$ These probabilities sum to $(16+32+24+8+1)/81=81/81=1$. The mean is $4(\tfrac13)=\tfrac43$, and the variance is $4(\tfrac13)(\tfrac23)=\tfrac89$.

Check: The mean from the distribution is $$ \frac{0\cdot16+1\cdot32+2\cdot24+3\cdot8+4\cdot1}{81} =\frac{108}{81}=\frac43. $$ The second moment is $(0^2\cdot16+1^2\cdot32+2^2\cdot24+3^2\cdot8+4^2\cdot1)/81=216/81=8/3$. Hence the variance is $8/3-(4/3)^2=8/3-16/9=8/9$, as claimed.

Worked Example: Counting Renewals by Time Three

Let $p=\tfrac12$ and $n=3$. Compute the count distribution and moments, then verify the probability of at least two renewals using the interarrival description.

Here $q=1-p=\tfrac12$, so $$ \mathbb{P}(N(3)=k)=\binom3k\left(\tfrac12\right)^k\left(\tfrac12\right)^{3-k} =\frac{\binom3k}{8}. $$ Thus the probabilities for $k=0,1,2,3$ are respectively $\tfrac18,\tfrac38,\tfrac38,\tfrac18$, which sum to $1$. The formulas give $\mathbb{E}[N(3)]=3(\tfrac12)=\tfrac32$ and $\operatorname{Var}(N(3))=3(\tfrac12)(\tfrac12)=\tfrac34$.

At least two renewals by time $3$ means $X_1+X_2\le3$. The only possible positive-integer pairs are $(1,1),(1,2),(2,1)$. From the geometric law, $\mathbb{P}(X=1)=\tfrac12$ and $\mathbb{P}(X=2)=\tfrac14$. Independence of the interarrivals therefore gives $$ \mathbb{P}(X_1+X_2\le3) =\left(\tfrac12\right)\left(\tfrac12\right) +\left(\tfrac12\right)\left(\tfrac14\right) +\left(\tfrac14\right)\left(\tfrac12\right) =\tfrac14+\tfrac18+\tfrac18=\tfrac12. $$ The count distribution gives $\mathbb{P}(N(3)\ge2)=\tfrac38+\tfrac18=\tfrac12$, in agreement. The weak inequality is appropriate because a renewal at time $3$ is included.

Worked Example: Five Steps with Success Probability Two-Fifths

Suppose $p=\tfrac25$ and $n=5$. Compute every probability in the count distribution and verify the moments directly from it.

Now $q=1-p=\tfrac35$. Substituting in the binomial formula gives $$ \begin{aligned} \mathbb{P}(N(5)=0)&=\left(\tfrac35\right)^5=\tfrac{243}{3125},\\ \mathbb{P}(N(5)=1)&=5\left(\tfrac25\right)\left(\tfrac35\right)^4=\tfrac{810}{3125},\\ \mathbb{P}(N(5)=2)&=10\left(\tfrac25\right)^2\left(\tfrac35\right)^3=\tfrac{1080}{3125},\\ \mathbb{P}(N(5)=3)&=10\left(\tfrac25\right)^3\left(\tfrac35\right)^2=\tfrac{720}{3125},\\ \mathbb{P}(N(5)=4)&=5\left(\tfrac25\right)^4\left(\tfrac35\right)=\tfrac{240}{3125},\\ \mathbb{P}(N(5)=5)&=\left(\tfrac25\right)^5=\tfrac{32}{3125}. \end{aligned} $$ The numerators sum to $243+810+1080+720+240+32=3125$. The mean from the formula is $5(\tfrac25)=2$, and the variance is $5(\tfrac25)(\tfrac35)=\tfrac65$.

Check: The distribution gives mean $$ \frac{810+2(1080)+3(720)+4(240)+5(32)}{3125} =\frac{6250}{3125}=2. $$ Its second moment is $(810+4(1080)+9(720)+16(240)+25(32))/3125=16250/3125=26/5$. Subtracting the squared mean gives $26/5-2^2=26/5-20/5=6/5$.

Why Independence Cannot Be Dropped

The identical Bernoulli probabilities at each grid time do not, on their own, imply geometric interarrivals or a binomial renewal count. For a concrete counterexample, let $Z$ be a single Bernoulli random variable with $\mathbb{P}(Z=1)=\tfrac12$, and set $Y_m=Z$ for every $m\ge1$. Each time still has event probability $\tfrac12$, but the outcomes are perfectly dependent: either every time is a renewal or no time is.

At $n=2$, this construction gives $\mathbb{P}(N(2)=0)=\tfrac12$, $\mathbb{P}(N(2)=2)=\tfrac12$, and $\mathbb{P}(N(2)=1)=0$. Incorrectly applying the binomial formula would give probabilities $\tfrac14,\tfrac12,\tfrac14$ for counts $0,1,2$, respectively. The error is assuming independence from the marginal probabilities. In this counterexample, after the first success, the next interarrival is $1$ with probability $1$; before any success, the wait is either $1$ or infinite. Neither behavior has the geometric law with parameter $\tfrac12$.

For $p=0$, there are no renewals and $N(n)=0$ for every $n$, so the count formulas extend to this boundary case with mean and variance zero. However, there are no finite interarrival times, so the ordinary geometric renewal model assumes $p>0$. At the other boundary $p=1$, every grid time is a renewal, $N(n)=n$, and the formulas correctly give mean $n$ and variance zero.

Common pitfall. Do not infer a geometric waiting time merely from the statement that the event probability is $p$ at each time. The geometric formula requires independent trials with the same success probability: $\mathbb{P}(X_k=r)=(1-p)^{r-1}p$. Under that assumption, the count formula follows because $N(n)$ is the sum of $n$ independent Bernoulli indicators. Checking both the time-grid convention and the independence assumption prevents the two most common modeling errors.

Check Your Understanding

Use the independent Bernoulli-grid model unless a question explicitly asks you to assess that assumption.

For $p=\tfrac14$, what is the probability that the first interarrival time is exactly $3$?
For $p=\tfrac12$, find $\mathbb{P}(N(4)=2)$, $\mathbb{E}[N(4)]$, and $\operatorname{Var}(N(4))$.
Explain why $N(0)=0$, and why an event at time $n$ is included in $N(n)$.
For independent trials with $p=1$, state the interarrival time, count at time $n$, and count variance.
In the shared-variable construction $Y_m=Z$, why does the binomial count formula fail even though every time has the same event probability?

Bernoulli Renewals on a Discrete Time Grid

What You'll Learn