What's the name of this discrete distribution (recursive difference equation) I derived?

Question

I came across this distribution in a computer game and wanted to learn more about its behaviour. It comes from the decision as to whether a certain event should occur after a given number of player actions. The details beyond this aren't relevant. It seems applicable to other situations, and I found it interesting because it's easy to calculate and creates a long tail.

Every step $n$, the game generates a uniform random number $0 \leq X < 1$. If $X < p(n)$, then the event is triggered. After the event once occurs, the game resets $n = 0 $ and runs through the sequence again. I'm only interested in one occurrence of the event for this problem, because that represents the distribution that the game is using. (Also, any questions regarding multiple occurrences can be answered with a single occurrence model.)

The main "abnormality" here is that the probability parameter in this distribution increases over time, or put another way, the threshold rises over time. In the example it changes linearly but I suppose other rules could apply. After $n$ steps, or actions by the user,

$$ p(n) = kn $$

for some constant $0 < k < 1$. At a certain point $n_{\max} $, we get $p(n_{\max}) \geq 1 $. The event is simply guaranteed to occur at that step.

I was able to determine that

$$ f(n) = p(n)\left[1 - F(n - 1)\right] $$ and $$ F(n) = p(n) + F(n-1)\left[1 - p(n)\right] $$ for PMF $f(n)$ and CDF $F(n)$. In brief, the probability that the event will on the $n$th step is equal to the probability $p(n)$, less the probability that it has already happened on any preceding step.

Here's a plot from our friend Monte Carlo, for fun, with $k \approx 0.003$. The median works out to 21 and average to 22.

This is broadly equivalent to a first-order difference equation from digital signal processing, which is my background, and so I found that quite novel. I'm also intrigued by the notion that $p(n)$ could vary according to any arbitrary formula.

My questions:

1. What's the name of this distribution, if it has one?
2. Is there any way to derive an expression for $f(n)$ without reference to $F(n)$?
3. Are there other examples of discrete recursive distributions like this?

Edits Clarified process about random number generation.

Answer 1

In a sense, what you have done is characterize all nonnegative integer-valued distributions.

Let's set aside the description of the random process for a moment and focus on the recursions in the question.

If $f_n = p_n (1 - F_{n-1})$, then certainly $F_n = p_n + (1-p_n) F_{n-1}$. If we rewrite this second recursion in terms of the survival function $S_n = 1 - F_n = \mathbb P(T > n)$ (where $T$ has distribution $F$), we get something very suggestive and easy to handle. Clearly, $$ S_n = 1 - F_n = (1-p_n) S_{n-1} \>, $$ and so $$ S_n = \prod_{k=0}^n (1-p_k) \> . $$ Thus, as long as our sequence $(p_n)$ takes values in $[0,1]$ and does not converge too rapidly to zero, then we will obtain a valid survival function (i.e., monotonically decreasing to zero as $n \to \infty$).

More specifically,

Proposition: A sequence $(p_n)$ taking values in $[0,1]$ determines a distribution on the nonnegative integers if and only if $$ -\sum_{n=0}^\infty \log(1-p_n) = \infty \>, $$ and all such distributions have a corresponding sequence (though it may not be unique).

Thus, the recursion written in the question is fully general: Any nonnegative integer valued distribution has a corresponding sequence $(p_n)$ taking values is $[0,1]$.

However, the converse is not true; that is, there are sequences $(p_n)$ with values in $[0,1]$ that do not correspond to any valid distribution. (In particular, consider $0 < p_n < 1$ for all $n \leq N$ and $p_n = 0$ for $n > N$.)

But, wait, there's more!

We've hinted at a connection to survival analysis and it's worth exploring this a little more deeply. In classical survival analysis with an absolutely continuous distribution $F$ and corresponding density $f$, the hazard function is defined as $$ h(t) = \frac{f(t)}{S(t)} \>. $$

The cumulative hazard is then $\Lambda(t) = \int_0^t h(s) \,\mathrm d s$ and a simple analysis of derivatives shows that $$ S(t) = \exp(-\Lambda(t)) = \exp\Big(-\int_0^t h(s) \,\mathrm d s\Big)\>. $$ From this, we can immediately give a characterization of an admissible hazard function: It is any measurable function $h$ such that $h(t) \geq 0$ for all $t$ and $\int_0^t h(s) \,\mathrm d s \uparrow \infty$ as $t \to \infty$.

We get a similar recursion for the survival-function to the one above by noticing that for $t > t_0$ $$ S(t) = e^{-\int_{t_0}^t h(s) \,\mathrm d s} S(t_0) \>. $$

Observe in particular that we could chose $h(t)$ to be piecewise constant with each piece being of width 1 and such that the integral converges to infinity. This would yield a survival function $S(t)$ that matches any desired discrete nonnegative integer valued one at each positive integer.

Connecting back to the discrete case

To match a desired discrete $S(n)$ at each integer, we should choose a hazard function that is piecewise constant such that $$ h(t) = h_n = -\log(1-p_n)\>, $$ on $(n-1,n]$. This provides a second proof of the necessary condition for the sequence $(p_n)$ to define a valid distribution.

Note that, for small $p_n$, $-\log(1-p_n) \approx p_n = f_n / S_{n-1}$ which provides a heuristic connection between the hazard function of a continuous distribution and the discrete distribution with matching survival function on the integers.

Postscript: As a final note, the example $p_n = k n$ in the question does not satisfy the necessary conditions without an appropriate modification to $f_n$ at $n = \lceil k^{-1} \rceil$ and setting $f_n = 0$ for all $n > \lceil k^{-1} \rceil$.

Answer 2

In the case $p(n) = p < 1$, we have some known properties. We can solve the recurrence relation

$$ F(n) = p + F(n-1)(1-p); \; F(0) = p $$

has the solution

$$ F(n) = P(N \le n) = 1- (1-p)^{n+1} $$ which is the geometric distribution. It is well studied.

The more general case of $p(n)$ can probably not be computed in closed form, and thus likely does not have a known distribution.

Other cases:

1. $p(n) = \frac{p}{n}; \; p<1; \;F(0) = p$ has solution $$ F(n) = 1 - \frac{(1-p)\Gamma( n + 1 -p)}{\Gamma( 1-p)\Gamma(n+1)} $$ which is not a commonly known distribution.
2. Define $S(n) = 1-F(n)$ (known as the survival function in stats), the recurrence relation above reduces to the simpler form: $$S(n) =\left(1 - p(n) \right) S(n-1)$$
3. From your example, it appears you want a function $p(n)$ that increases in $n$. Your choice $p(n) = kn$ isn't great analytically because of the break at $p>1$. Mathematicians and statisticians prefer smooth things. So I propose $$p(n) = 1 - \frac{(1-p)}{n+1} \; p<1$$ which $p(0) = p$ and converges to 1. Solving the recurrence relation with this $p(n)$, has the nice analytical form: $$ F(n) = 1 - \frac{ (1-p)^{n+1} }{ n! } $$ Consider $S(n) = 1 - F(n) = \frac{ (1-p)^{n+1} }{ n! }$. A known stat fact is that $$\sum_{i=0}^{\infty} S(i) = E[N]$$ which, if you remember some calculus, looks a lot like the exponential's Taylor series, hence, $$E[N] = (1-p)e^{(1-p) }$$