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

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.

-
Any reason you chose square brackets instead of ()? –  Cam.Davidson.Pilon Dec 16 '12 at 22:58
@Cam.Davidson.Pilon: My DSP background snuck in. We tend to use square brackets for discrete time functions. I guess this must be jarring so I'll change it. –  jbarlow Dec 16 '12 at 23:01
The process you are assuming does not appear clearly defined here. You say "Every step $n$, the game rolls a random number $X$. If $X < p(n)$, then the event is triggered." But, you give no specification for how $X$ is drawn. I think it would be helpful if the process could be described a little more precisely. –  cardinal Dec 16 '12 at 23:50
@jbarlow: Sorry if my previous remark was unclear. If $p(n) = k n$ for some $0 < k < 1$, then there is no way your process could have more than $\lceil k^{-1} \rceil$ steps since a uniform random number between zero and one would definitely be smaller than $p(n)$ for any $n > 1/k$. The quantity $p(n)$ as a function of $n$ is very closely related to what is called the hazard function in the subfield of statistics known as survival analysis. –  cardinal Dec 17 '12 at 3:42
For small $k$, using the differential analog of this difference equation shows that $F$ (not $f$!) is close to Gaussian. (From this we immediately deduce, for instance, that the mean must be near $\sqrt{1/k}=\sqrt{333}\approx 18$.) Please note, too, that there are some (strong) restrictions on $k$, for otherwise once $p(n)$ exceeds $1$ (which it eventually does), there is no guarantee that $F$ remains less than or equal to $1$. –  whuber Dec 17 '12 at 16:00

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$.

-
+1 Very illuminating. But, concerning the postscript, it seems to me that the "appropriate truncation" occurs as a matter of course for special values of $k$. For instance, with $k=1/2$ we obtain $f=(0,1/2,1/2,0,\ldots)$, and more generally, with $k=1/m$ we get $f(m+1)=f(m+2)=\cdots=0$. –  whuber Dec 17 '12 at 17:01
@whuber: I should have specified more clearly what I meant by "appropriate truncation". I was thinking of truncating (shrinking) the value of $f_n$ at the specified point (so that $F_n$ becomes unity). I think that notion is still valid in the case you mention, just that the truncation would not result in a change of value of $f_n$. I'll try to clarify this in an edit shortly. Thank you! –  cardinal Dec 17 '12 at 17:51
Great answer. This is very insightful. I was really interested to see this problem connected to other areas and concepts. –  jbarlow Dec 17 '12 at 20:14
@jbarlow: Thank you. I'm glad you found it useful! I enjoyed thinking a bit about it, as it's a nice question. –  cardinal Dec 17 '12 at 20:40

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) }$$
-
Cam, that's not the hazard function., but rather the survival function. :-) –  cardinal Dec 17 '12 at 4:17
ty, *edited to survival –  Cam.Davidson.Pilon Dec 17 '12 at 4:18