Variations

\(\newcommand{\P}{\mathbb{P}}\) \(\newcommand{\E}{\mathbb{E}}\) \(\newcommand{\var}{\text{var}}\) \(\newcommand{\R}{\mathbb{R}}\) \(\newcommand{\N}{\mathbb{N}}\) \(\newcommand{\ms}{\mathscr}\) \(\newcommand{\rta}{\rightarrow}\) \(\newcommand{\lfa}{\leftarrow}\) \(\newcommand{\upa}{\uparrow}\) \(\newcommand{\lfrta}{\leftrightarrow}\) \(\newcommand{\nea}{\nearrow}\) \(\newcommand{\sea}{\searrow}\) \(\newcommand{\nwa}{\nwarrow}\) \(\newcommand{\swa}{\swarrow}\) \(\newcommand{\Rta}{\Rightarrow}\) \(\newcommand{\bs}{\boldsymbol}\)

In this section we study some graphs that are closely related to the standard discrete graph \((\N, \le)\) studied in Section 1: the strict order graph \((\N, \lt)\), the covering graph \((\N, \upa)\) of \((\N, \le)\), and the reflexive closure \((\N, \rta)\) of \((\N, \upa)\). Since the spaces are discrete, the reference measure space is \((\N, \ms P(\N), \#)\), where as usual \(\ms P(\N)\) is the power set of \(\N\) and \(\#\) is counting measure. We also assume that we have a probability space \((\Omega, \ms F, \P)\) in the background so that all random variables in \(\N\) are defined on this space.

The Strict Order Graph

First we consider the strict order graph \((\N, \lt)\). Note that \((\N, \lt)\) is the irreflexive reduction of \((\N, \le)\) as discussed in Section 1.6, and is isomorphic to the graph \((\N_+, \lt)\), with isomorphism \(x \mapsto x + 1\). In turn, \((\N_+, \lt)\) is the graph associated with the strict positive semigroup \((\N_+, +)\).

Graph Basics

For the graph \((\N, \lt)\),

The left walk function \(u_n\) of order \(n \in \N\) is given by \[u_n(x) = \binom{x}{n}, \quad x \in \N\]
The left generating function \(U\) is given by \(U(x, t) = (1 + t)^x\) for \(x \in \N\) and \(t \in \R\).

Details:

Note that the expression is correct when \(n = 0\). Assume that the expression is correct for a given \(n \in \N\). Then using a binomial identity, \[u_{n + 1}(x) = \sum_{z = 0}^{x - 1} u_n(z) = \sum_{z = 0}^{x - 1} \binom{z}{n} = \binom{x}{n + 1}\] For the combinatorial proof, to construct a walk of length \(n\) in \((\N, \lt)\) ending in \(x\) we need to select a subset of size \(n\) from \(\{0, \ldots, x - 1\}\). The number of ways to do this is \(\binom{x}{n}\).
This follows from part (a) and the binomial theorem.

The (right) \(\sigma\)-algebra associated with \((\N, \lt)\) is the reference \(\sigma\)-algebra \(\ms P(\N)\).

Details:

The right neighbor set of \(x \in \N\) for the graph is \(A_x = \{y \in \N: y \gt x\} = \{x + 1, x + 2, \ldots\}\), and the \(\sigma\)-algebra associated with \((\N, \lt)\) is \(\ms A = \sigma(\{A_x: x \in \N\}\).

Reliability Functions

Suppose now that \(X\) is a random variable in \(\N\) with density function \(f\).

For the graph \((\N, \lt)\),

The reliability function of \(X\) is \[F(x) = \P(X \gt x) = \sum_{y = x + 1}^\infty f(y), \quad x \in \N \]
The rate function of \(X\) is \[r(x) = \frac{f(x)}{F(x)} = \frac{f(x)}{\sum_{y = x + 1}^\infty f(y)}, \quad x \in \N\]

Details:

The results follow directly from the defintions. Again, the right neighbor set of \(x \in \N\) is \(\{x + 1, x + 2, \ldots\}\).

The graph \((\N, \lt)\) is stochastic: the reliability function of \(X\) uniquely determines the distribution of \(X\).

Details:

The density function \(f\) can be recovered from the reliability function \(F\) by \(f(0) = 1 - F(0)\) and \(f(x) = F(x - 1) - F(x)\) for \(x \in \N_+\).

Moments

For the graph \((\N, \lt)\),

The moment of \(X\) of order \(n \in \N\) is \[\mu_n = \E\left[\binom{X}{n}\right]\]
The generating function \(M\) of \(X\) is \[M(t) = \E[(1 + t)^X]\]

Details:

The results follow from . In part (a), some of the moments may be infinite, of course. In part (b), the generating function is defined for all \(t \in \R\) for which the expected value exists. In particular, \(M(t)\) is finite for \(t \in (-2, 0)\).

Note that the generating function of \(X\) is the ordinary probability denerating function evaluated at \(1 + t\).

The recursive moment formula of \(X\) for the graph \((\N, \lt)\) is \[\sum_{x = 1}^\infty \binom{x}{n} \P(X \gt x) = \E\left[\binom{X}{n + 1}\right], \quad n \in \N\]

Details:

This follows from and and the basic result in Section 1.3.

Constant Rate Distributions

Random variable \(X\) has constant rate for \((\N, \lt)\) if and only if \(X + 1\) is exponential for \((\N_+, +)\) if and only if \(X + 1\) is memoryless for \((\N_+, +)\). The distribution with constant rate \(\alpha \in (0, \infty)\) for \((\N, \lt)\) has density function \(f\) given by \[f(x) = \frac{\alpha}{1 + \alpha} \left(\frac{1}{1 + \alpha}\right)^x, \quad x \in \N\]

Details:

Let \(F\) denote the reliability function of \(X\) for \((\N, \lt)\) and recall that \(f(0) = 1 - F(0)\) and \(f(x) = F(x - 1) - F(x)\) for \(x \in \N\). For \(\alpha \in (0, \infty)\), the constant rate property \(f = \alpha F\) has the unique solution \begin{align*} F(x) &= \left(\frac{1}{1 + \alpha}\right)^{x + 1}, \quad x \in \N \\ f(x) &= \frac{\alpha}{1 + \alpha} \left(\frac{1}{1 + \alpha}\right)^x, \quad x \in \N \end{align*} Let \(Y = X + 1\), so that \(Y\) has values in \(\N_+\). Then \(Y\) has density function \(g\) given by \(g(y) = f(y - 1)\) for \(y \in \N_+\), and the reliability function \(G\) of \(Y\) for \((\N_+, \lt)\) is given by \(G(y) = F(y - 1)\) for \(y \in \N_+\). If \(X\) has the distribution with constant rate \(\alpha \in (0, \infty)\) for \((\N, \lt)\) above, then \(Y\) is memoryless for \((\N_+, +)\) and has constant rate \(\alpha\) for the associated graph \((\N_+, \lt)\). Hence \(Y\) is exponential for \((\N_+, +)\). Conversely, if \(Y\) is memoryless for \((\N_+, +)\) then \(G(y) = (1 - \beta)^y\) for \(y \in \N_+\) and hence \(g(y) = \beta (1 - \beta)^{y - 1}\) for \(y \in \N_+\) where \(\beta = G(1) \in (0, 1)\). Hence \(Y\) has constant rate \(\alpha = \beta / (1 - \beta) \in (0, \infty)\) for \((\N_+, \lt)\) and therefore \(Y\) is exponential for \((\N_+, +)\). Then also \(X = Y - 1\) has constant rate \(\alpha\) for \((\N, \lt)\).

Of course, the constant rate distribution in is the geometric distribution on \(\N\) with success parameter \(\alpha / (1 + \alpha)\). From the general theory, if \(X\) has constant rate \(\alpha \in (0, \infty)\) then the graph moment of \(X\) of order \(n \in \N\) in is \(\alpha^n\). The followiing result gives the mean, variance, and entropy as a function of the rate parameter.

Suppose that \(X\) has constant rate \(\alpha \in (0, \infty)\) for \((\N, \lt)\). Then

\(\E(X) = 1 / \alpha\)
\(\var(X) = (1 + \alpha) / \alpha^2\)
\(H(X) = -\ln \alpha + (1 + 1 / \alpha) \ln(1 + \alpha)\)

Details:

These are standard results since \(X\) has the geometric distribution on \(\N\) with success parameter \(\alpha / (1 + \alpha)\).

Random Walk

A random walk \(\bs{Y} = (Y_1, Y_2, \ldots)\) on the graph \((\N, \lt)\) has the property that \(Y_n \lt Y_{n + 1}\) for \(n \in \N\). If \(\bs Y\) is associated with a random variable \(X\) in \(\N\) with density \(f\), then the transition density \(P\) of \(\bs Y\) is given by \[P(x, y) = \frac{f(y)}{\sum_{x \lt z}^\infty f(z)}; \quad x \lt y \] Here are the standard results when \(X\) has a constant rate distribution:

Suppose that \(X\) has constant rate \(\alpha \in (0, \infty)\) for the graph \((\N, \lt)\) and that \(\bs{Y} = (Y_1, Y_2, \ldots)\) is the random walk associated with \(X\).

The transition density \(P\) of \(\bs Y\) is given by \[P(x, y) = \alpha \left(\frac{1}{1 + \alpha}\right)^{y - x}, \quad x \lt y\]
The density function \(g_n\) of \(Y_1, Y_2, \ldots, Y_n)\) for \(n \in \N_+\) is given by \[g_n(x_1, x_2, \ldots, x_n) = \alpha^n \left(\frac{1}{1 + \alpha}\right)^{x_n + 1}, \quad x_1 \lt x_2 \lt \cdots \lt x_n\]
The density function \(f_n\) of \(Y_n\) for \(n \in \N_+\) is given by \[f_n(x) = \alpha^n \binom{x}{n - 1} \left(\frac{1}{1 + \alpha}\right)^{x + 1}, \quad x \in \{n - 1, n , n + 1, \ldots\}\]
Given \(Y_{n + 1} = x \in \{n, n + 1, \ldots\}\), \((Y_1, Y_2, \ldots, Y_n)\) is uniformly distributed on the \(\binom{x}{n}\) points in the set \[\{(x_1, x_2, \ldots, x_n) \in \N^n: x_1 \lt x_2 \lt \cdots \lt x_n \lt x\}\]

Recall also that the point process associated with the random walk \(\bs Y\) is \(\bs N = \{N_A: A \subseteq \N\}\) where \(N_A = \#\{n \in \N_+: Y_n \in A\}\).

Details:

From the general theory in Section 1.5, \(\E(N_A) = \E[U(X, \alpha); X \in A]\) for \(A \subseteq \N\) where \(U\) is the generating function. So from , \[\E(N_A) = \E[(1 + \alpha)^X; X \in A] = \sum_{x \in A} (1 + \alpha)^x \frac{\alpha}{1 + \alpha} \left(\frac{1}{1 + \alpha}\right)^x = \frac{\alpha}{1 + \alpha} \#(A)\]

Finally, recall the process of thinning the random walk \(\bs Y\). Specifically, suppose that \(N\) is independent of \(\bs Y\) and has the geometric distribution on \(\N_+\) with success probability \(p \in (0, 1)\), so that \(\P(N = n) = p (1 - p)^{n - 1}\) for \(n \in \N_+\). We accept or reject each point in \(\bs Y\), independently, with probabilities \(p\) and \(1 - p\), respectively. So \(Y_N\) is the first accepted point.

Suppose again that \(X\) has constant rate \(\alpha \in (0, \infty)\) for the graph \((\N, \lt)\) and that \(\bs{Y} = (Y_1, Y_2, \ldots)\) is the random walk associated with \(X\). For the thinned process with parameter \(p \in (0, 1)\), the density function \(h\) of \(Y_N\) is given by \[h(x) = \frac{\alpha p}{1 + \alpha} \left(1 - \frac{\alpha p}{1 + \alpha}\right)^x, \quad x \in \N\]

Details:

Recall that \(h\) is given by \(h(x) = p \alpha U[x, (1 - p) \alpha] F(x)\) for \(x \in \N\) where again \(U\) is the generating function and where \(F\) is the reliability function of \(X\). Hence \[h(x) = p \alpha [1 + (1 - p) \alpha]^x \frac{1}{(1 + \alpha)^{x + 1}} = \frac{\alpha p}{1 + \alpha} \left(1 - \frac{\alpha p}{1 + \alpha}\right)^x, \quad x \in \N\]

So \(Y_N\) has the geometric distribution on \(\N\) with success parameter \(\alpha p / (1 + \alpha)\).

The Covering Graph

Next we consider the covering graph \((\N, \upa)\) of the standard graph \((\N, \le)\), so that \(x \upa x + 1\) for \(x \in \N\).

Graph Basics

For the graph \((\N, \upa)\),

The left walk function \(u_n\) of order \(n \in \N\) is given by \(u_n(x) = \bs 1(x \ge n)\) for \(x \in \N\).
The left generating function \(U\) is given by \begin{align*} U(x, 1) & = x + 1, \quad x \in \N \\ U(x, t) &= \frac{t^{x + 1} - 1}{t - 1}, \quad x \in \N, \; t \ne 1 \end{align*}

Details:

A walk is a sequence of consecutive nonnegative integers. So if \(x \lt n\) there are no walks of length \(n\) ending in \(x\). If \(x \ge n\) there is one such walk, namely \((x - n, x - n + 1, \ldots, x - 1, x)\).
This follows from part (a) of and geometric series: For \(x \in \N\), \[U(x, t) = \sum_{n = 0}^\infty u_n(x) t^n = \sum_{n = 0}^x t^n = \frac{t^{x + 1} - 1}{t - 1}, \quad t \ne 1\] Of course, \(U(x, 1) = x + 1\).

The (right) \(\sigma\)-algebra associated with \((\N, \upa)\) is the reference \(\sigma\)-algebra \(\ms P(\N)\).

Details:

From the general theory in Section 1.2, the right \(\sigma\)-algebra associated with \((\N, \upa)\) is the same as that for \((\N, \lt)\), so the result follows from . A direct proof is also trivial since the right neighbor set of \(x \in \N\) for \((\N, \upa)\) is \(\{x + 1\}\)

Reliability Functions

Suppose again that \(X\) is a random variable in \(\N\) with density function \(f\).

For the graph \((\N, \upa)\),

The reliability function \(F\) of \(X\) is given by \(F(x) = f(x + 1)\) for \(x \in \N\).
The rate function \(f\) of \(X\) is given by \(r(x) = f(x) / f(x + 1)\) for \(x \in \N\).

Details:

The results follow form the defintions.

The graph \((\N, \upa)\) is stochastic: the reliability function of \(X\) uniquely determines the distribution of \(X\).

Details:

The density function \(f\) can be recovered from the reliability function \(F\) by \(f(x) = F(x - 1)\) for \(x \in \N_+\) and \(f(0) = 1 - \sum_{x = 0}^\infty F(x)\).

Moments

For the graph \((\N, \upa)\),

The moment of \(X\) of order \(n \in \N\) is \(\mu_n = \P(X \ge n)\).
The generating function of \(M\) of \(X\) is given by \begin{align*} M(1) & = \E(X) + 1 \\ M(t) & = \E\left(\frac{t^{X + 1} - 1}{t - 1}\right) = \frac{t \, \E\left(t^X\right) - 1}{t - 1}, \quad t \ne 1 \end{align*}

Details:

The results follow from . In the second displayed equation in part (b), the generating function is defined for all \(t \in \R\) for which the expected value exists. In particular, \(M(t)\) is finite for \(t \in (-1, 1)\).

Once agin, the graph generating function of \(X\) is closely related to the ordinary probability generating function.

The recursive moment formula of \(X\) for the graph \((\N, \upa)\) is \[\sum_{x = 0}^\infty \bs 1(x \ge n) \P(X = x + 1) = \E[\bs 1(X \ge n + 1)], \quad n \in \N\]

Details:

This follows from and and the basic result in Section 1.3.

Of course, the formula is is trivial, since it's equivalent to \(\sum_{x = n}^\infty \P(X = x + 1) = \P(X \ge n + 1)\).

Constant Rate Distributions

Random variable \(X\) has constant rate \(\alpha \in (1, \infty)\) for \((\N, \upa)\) if and only if \(X\) has denstiy function \(f\) given by \[f(x) = \left(1 - \frac{1}{\alpha}\right) \left(\frac{1}{\alpha}\right)^x, \quad x \in \N\]

Details:

Let \(f\) denote the density function of \(X\) and let \(F\) denote the reliability function of \(X\) for \((\N, \upa)\). Then \(F(x) = f(x + 1)\) for \(x \in \N\), so the constant rate property is \(f(x) = \alpha f(x + 1)\) for \(x \in \N\). Hence \(f(x) = (1 / \alpha)^x f(0)\) for \(x \in \N\). In order for \(f\) to be a proper density function, we must have \(\alpha \gt 1\), in which case \(f(x) = (1 - 1 / \alpha) (1 / \alpha)^x\) for \(x \in \N\).

Of course, the distribution in is the geometric distribution on \(\N\) with success parameter \(1 - 1 / \alpha\). A bit more generally, the total order graph \((\N, \le)\) is uniform, so from results in Section 1.5, \(X\) has constant rate \(\alpha^n\) for \((\N, \upa^n)\) for each \(n \in \N\), where \(\upa^n\) is the composition power of \(\upa\) of order \(n\).

Suppose again that \(X\) is a random variable in \(\N\). For the graph \((\N, \upa)\),

The cumulative rate function \(R_n\) of order \(n \in \N_+\) is given by \(R_n(x) = f(x - n) / f(x)\) for \(x \in \{n, n + 1, \ldots\}\) and \(R_n(x) = 0\) for \(x \in \{0, 1, \ldots, n - 1\}\).
If \(X\) has constant average rate (order 1) then \(X\) has constant rate.
If \(n \ge 2\) then there are distributions with constant average rate of order \(n\) that do not have constant rate.

Details:

Suppose that \(X\) has density function \(f\).

This follows from the definition.
The condition for \(X\) to have constant average rate \(\alpha \in (1, \infty)\) reduces to \(f(x) = f(x - 1) / \alpha\) for \(x \in \N_+\). Hence \(f(x) = (1 / \alpha)^x f(0)\) for \(x \in \N_+\). The condition \(\sum_{x = 0}^\infty f(x) = 1\) then gives \[f(x) = \left(1 - \frac{1}{\alpha}\right) \left(\frac{1}{\alpha}\right)^x, \quad x \in \N\] which is the distribution with constant rate \(\alpha\).
Let \(n \in \{2, 3, \ldots\}\) and \(\alpha \in (1, \infty)\). The condition for \(X\) to have constant average rate \(\alpha^n\) of order \(n\) reduces to \(f(x) = f(x - n) / \alpha^n\) for \(x \in \{n, n + 1, \ldots\}\). Hence \[f(m n + k) = \frac{f(k)}{\alpha^{m n}}, \quad m \in \N, \, k \in \{0, 1, \ldots, n - 1\}\] No conditions are imposed on \(f(k)\) for \(k \in \{0, 1, \ldots, n - 1\}\) except of course that \(\sum_{x=0}^\infty f(x) = 1\). If we take \(f(k) = (1 - 1 / \alpha) (1 / \alpha)^k\) for \(k \in \{0, 1, \ldots, n - 1\}\) then we get \(f(x) = (1 - 1 / \alpha) (1 / \alpha)^x\) for \(x \in \N\) and hence \(X\) has constant rate \(\alpha\). But of course there are infitely many other choices for \(f(k)\), \(k \in \{0, 1, \ldots, n - 1\}\) that do not lead to constant rate distributions.

Once again, the graph moment of \(X\) of order \(n \in \N\) is \(\alpha^n\). Below are the mean, variance and entropy in terms of the rate parameter.

Suppose that \(X\) has constant rate \(\alpha \in (1, \infty)\) for \((\N, \upa)\). Then

\(\E(X) = 1 / (\alpha - 1)\)
\(\var(X) = \alpha / (\alpha - 1)^2\)
\(H(X) = \ln \alpha / (\alpha - 1) - \ln(1 - 1 / \alpha)\)

Details:

These are standard results since \(X\) has the geometric distribution on \(\N\) with success parameter \(1 - 1 / \alpha\).

Random Walk

The random walk on \((\N, \upa)\) associated with a random variable \(X \in \N\) is trivial: \((X, X + 1, X + 2, \ldots)\). The next result gives a summary when \(X\) has a constant rate distribution.

Suppose that \(X\) has constant rate \(\alpha \in (1, \infty)\) for the graph \((\N, \upa)\) and that \(\bs Y = (Y_1, Y_2, \ldots)\) is the random walk associated with \(X\).

The transition density \(P\) of \(\bs Y\) is given by \(P(x, x + 1) = 1\) for \(x \in \N\),
The density function \(g_n\) of \((Y_1, Y_2, \ldots, Y_n)\) for \(n \in \N_+\) is given by \[g_n(x, x + 1, \ldots, x + (n - 1)) = \left(1 - \frac 1 \alpha\right) \left(\frac{1}{\alpha}\right)^{x}, \quad x_1 \in \N\]
The density function \(f_n\) of \(Y_n\) for \(n \in \N_+\) is given by \[f_n(x) = \left(1 - \frac 1 \alpha\right) \left(\frac{1}{\alpha}\right)^{x - n + 1}, \quad x \in \{n - 1, n, n + 1, \ldots\}\]
Given \(Y_{n + 1} = x \in \{n, n + 1, \ldots\}\), \((Y_1, Y_2, \ldots, Y_n) = (x - n, x - n - 1, \ldots, x - 1)\) with probability 1.

Recall again that the point process associated with the random walk \(\bs Y\) is \(\bs N = \{N_A: A \subseteq \N\}\) where \(N_A = \#\{n \in \N_+: Y_n \in A\}\).

Details:

From the general theory in Section 1.5, \(\E(N_A) = \E[U(X, \alpha); X \in A]\) for \(A \subseteq \N\) where \(U\) is the generating function. So from and , \[\E(N_A) = \E\left[\frac{\alpha^{X + 1} - 1}{\alpha - 1}; X \in A\right] = \sum_{x \in A} \left(1 - \frac 1 \alpha\right)\left(\frac 1 \alpha\right)^x \frac{\alpha^{x + 1} - 1}{\alpha - 1} = \#(A) - \sum_{x \in A} \left(\frac 1 \alpha\right)^{x + 1}, \quad A \subseteq \N\] Note that the series on the right is always finite, so we don't have to worry about the dreaded indeterminate form \(\infty - \infty\).

Recall again the process of thinning the random walk \(\bs Y\) with parameter \(p \in (0, 1)\). So \(N\) is independent of \(\bs Y\) and has the geometric distribution on \(\N_+\) with success probability \(p\), and hence \(Y_N\) is the first accepted point.

Suppose again that \(X\) has constant rate \(\alpha \in (1, \infty)\) for the graph \((\N, \upa)\) and that \(\bs{Y} = (Y_1, Y_2, \ldots)\) is the random walk associated with \(X\), thinned with parameter \(p \in (0, 1)\). Then \(Y_N\) has the distribution of the sum of two independent geometrically distrtibuted variables in \(\N\), with success parameters \(1 - 1 / \alpha\) and \(p\). The density function \(h\) of \(Y_N\) is given as follows:

If \((1 - p) \alpha = 1\) then \[h(x) = (x + 1) \left(1 - \frac{1}{\alpha}\right)^2 \left(\frac 1 \alpha\right)^x, \quad x \in \N\]
If \((1 - p) \alpha \ne 1\) then

Details:

There is a simple direct proof of this result: Since the random walk is \(\bs{Y} = (X, X + 1, X + 2, \ldots)\), the first accepted point is \(Y_N = X_1 + (N - 1)\). But \(X\) has the geometric distribution on \(\N\) with success parameter \(1 - 1 / \alpha\) and \(N - 1\) has the geometric distribution on \(\N\) with parameter \(p\), and \(X_1\) and \(N\) are independent.

In part (a), the success parameters are the same, so \(Y_N\) has the negative binomial distribution on \(\N\) with stopping parameter \(2\) and success parameter \(1 - 1 / \alpha\).

The Reflexive Closure

Finally, we study the reflexive closure \((\N, \rta)\) of the covering graph \((\N, \upa)\), so that \(x \rta x\) and \(x \rta x + 1\) for \(x \in \N\).

Graph Basics

For the graph \((\N, \rta)\),

The left walk function \(u_n\) of order \(n \in \N\) is given by \[u_n(x) = \sum_{k = 0}^x \binom{n}{k}, \quad x \in \N\]
The left generating function \(U\) is given by \begin{align*} U(x, 1 / 2) & = 2 (x + 1), \quad x \in \N \\ U(x, t) & = \frac{1}{1 - 2 t} \left[1 - \left(\frac{t}{1 - t}\right)^{x + 1}\right], \quad x \in \N, \, t \in (-1, 1), t \ne 1 / 2 \end{align*}

Details:

The results follow from from and general results on reflexive closure in Section 1.6. Let \(v_k\) denote the walk function of order \(k \in \N\) for \((\N, \upa)\), and \(V\) the generating function for \((\N, \upa)\). Then

\[u_n(x) = \sum_{k = 0}^n \binom{n}{k} v_k(x), \quad x \in \N\]
\[U(x, t) = \frac{1}{1 - t} V\left(x, \frac{t}{1 - t}\right), \quad x \in \N\]

In part (a), we have the usual convention that \(\binom{n}{k} = 0\) if \(k \gt n\), and hence \(u_n(x) = 2^n\) if \(x \ge n\).

The (right) \(\sigma\)-algebra associated with \((\N, \rta)\) is the reference \(\sigma\)-algebra \(\ms P(\N)\).

Details:

This follows from the general theory in Section 1.6 since \(\upa\) is asymmetric. A direct proof is also trivial: The right neighbor set of \(x \in \N\) for \((\N, \rta)\) is \(\{x, x + 1\}\). Hence \(A_x \setminus A_{x + 1} = \{x\}\) for \(x \in \N\).

Reliability Functions

Suppose again that \(X\) is a random variable in \(\N\) with density function \(f\).

For the graph \((\N, \rta)\),

The reliability function \(F\) of \(X\) is given by \(F(x) = f(x) + f(x + 1)\) for \(x \in \N\).
The rate function \(f\) of \(X\) is given by \(r(x) = f(x) / [f(x) + f(x + 1)]\) for \(x \in \N\).

Details:

The results follow form the defintions.

The graph \((\N, \rta)\) is stochastic: the reliability function of \(X\) uniquely determines the distribution of \(X\).

Details:

For \(x, \, n \in \N\), note that \[\sum_{i = 0}^n (-1)^i F(x + i) = f(x) + (-1)^n f(x + n + 1)\] since the sum on the left collapses. But \(f(x + n + 1) \to 0\) as \(n \to \infty\) so \[f(x) = \sum_{i = 0}^\infty (-1)^i F(x + i), \quad x \in \N\]

Moments

For the graph \((\N, \rta)\),

The moment of \(X\) of order \(n \in \N\) is \[\mu_n = \sum_{k = 0}^n \binom{n}{k} \P(X \ge k) \]
The generating function \(M\) of \(X\) is \[M(t) = \frac{1}{1 - 2 t} \left(1 - \frac{t}{1 - t} \E\left[\left(\frac{t}{1 - t}\right)^X\right]\right)\]

Details:

The results follow from . In part (b), the generating function is defined at least for \(t\) in the interval \((-1, 1)\).

The graph generating function of \(X\) is closely related to the ordinary probability generating function of \(X\), evaluated at \(t / (1 - t)\).

The recursive moment formula of \(X\) for the graph \((\N, \rta)\) is \[\sum_{x = 0}^\infty \sum_{k = 0}^x \binom{n}{k}[\P(X = x) + \P(X = x + 1)] = \sum_{k = 0}^{n + 1} \binom{n + 1}{k} \P(X \ge k), \quad n \in \N\]

Details:

This follows from and and the basic result in Section 1.3. Once again, this result is \[\sum_{x = 0}^\infty u_n(x) F(x) = \E[u_{n + 1}(X)], \quad n \in \N\] A direct proof involves a sum interchange and the basic binomial identity on the left.

When \(n = 0\), the formula in reduces to the obvious result \(\sum_{x = 0}^\infty [\P(X = x) + \P(X = x + 1)] = 1 + \P(X \ge 1)\).

Constant Rate Distributions

Random variable \(X\) has contant rate \(\alpha \in (1 / 2, 1)\) for \((\N, \rta)\) if and only if \(X\) has density function \(f\) given by \[f(x) =\left(2 - \frac 1 \alpha\right) \left(\frac 1 \alpha - 1\right)^x, \quad x \in \N\]

Details:

The proof follows from Section 1.6 on reflexive closure: \(X\) has constant rate \(\alpha\) for \((\N, \upa)\) if and only if \(X\) has constant rate \(\alpha / (1 - \alpha)\) for \((\N, \rta)\).

Of course, the distribution in is the geometric distribution on \(\N\) with success parameter \(2 - 1 / \alpha\). Once again, the graph moment of \(X\) of order \(n\) is \(\alpha^n\). The following result gives the mean, variance and entropy in terms of the rate parameter.

Suppose that \(X\) has constant rate \(\alpha \in (1 / 2, 1)\) for \((\N, \rta)\). Then

\(\E(X) = (1 - \alpha) / (2 \alpha - 1)\)
\(\var(X) = \alpha (1 - \alpha) / (2 \alpha - 1)^2\)
\(H(X) = -\ln (2 - 1 / \alpha) - \ln (1 / \alpha - 1) [(1 - \alpha) / (2 \alpha - 1)]\).

Details:

These are standard results since \(X\) has the geometric distribution on \(\N\) with success parameter \(2 - 1 / \alpha\).

Random Walks

A random walk \(\bs Y = (Y_1, Y_2, \ldots)\) on the graph \((\N, \rta)\) has the property that \(Y_{n + 1} \in \{Y_n, Y_n + 1\}\) for \(n \in \N\). If the walk is associated with a random variable \(X\) in \(\N\) with density \(f\), then the transition density \(P\) of \(\bs Y\) is given by \[P(x, x) = \frac{f(x)}{f(x) + f(x + 1)}, \; P(x, x + 1) = \frac{f(x + 1)}{f(x) + f(x + 1)}, \quad x \in \N\] Here are the standard results when \(X\) has a constant rate distribution.

Suppose that \(X\) has constant rate \(\alpha \in (1 / 2, 1)\) for the graph \((\N, \rta)\) and that \(\bs Y = (Y_1, Y_2, \ldots)\) is the random walk associated with \(X\).

The transition density \(P\) of \(\bs Y\) is given by \(P(x, x) = \alpha,\) and \(P(x, x, + 1) = 1 - \alpha\) for \(x \in \N\).
The density function \(g_n\) of \((Y_1, Y_2, \ldots, Y_n)\) for \(n \in \N_+\) is given by \[g_n(x_1, x_2, \ldots, x_n) = \alpha^{n - 1} \left(2 - \frac 1 \alpha\right) \left(\frac 1 \alpha - 1\right)^{x_n}, \quad x_1 \in \N, \, x_{k + 1} \in \{x_k, x_k + 1\} \text{ for } k \in \{1, 2, \ldots, n - 1\}\]
The density function \(f_n\) of \(Y_n\) for \(n \in \N_+\) is given by \[f_n(x) = \alpha^{n - 1} \left(2 - \frac 1 \alpha\right) \left(\frac 1 \alpha - 1\right)^x \sum_{k = 0}^x \binom{n - 1}{k}, \quad x \in \N \]
Given \(Y_{n + 1} = x \in \N\), \((Y_1, Y_2, \ldots, Y_n)\) is uniformly distributed on the \(\sum_{k = 0}^x \binom{n}{k}\) points in the set \[\{(x_1, x_2, \ldots, x_n) \in \N^n: x_{k + 1} \in \{x_k, x_k + 1\} \text{ for } k \in \{1, 2, \ldots, n - 2\} \text{ and } x_n \in \{x - 1, x\}\}\]

Recall again that the point process associated with the random walk \(\bs Y\) is \(\bs N = \{N_A: A \subseteq \N\}\) where \(N_A = \#\{n \in \N_+: Y_n \in A\}\).

Suppose again that \(X\) has constant rate \(\alpha \in (1 / 2, 1)\) for the graph \((\N, \rta)\) and that \(\bs{Y} = (Y_1, Y_2, \ldots)\) is the random walk associated with \(X\). Then \[\E(N_A) = \frac{1}{1 - 2 \alpha} + \frac{1}{1 - \alpha} \#(A), \quad A \subseteq \N\]

Details:

From the general theory in Section 1.5, \(\E(N_A) = \E[U(X, \alpha); X \in A]\) for \(A \subseteq \N\) where \(U\) is the generating function. So the result follows from and .

Suppose again that \(X\) has constant rate \(\alpha \in (1 / 2, 1)\) for the graph \((\N, \rta)\) and that \(\bs{Y} = (Y_1, Y_2, \ldots)\) is the random walk associated with \(X\), thinned with parameter \(p \in (0, 1)\). Then \(Y_N\) has the distribution of the sum of two independent, geometrically distributed random variables in \(\N\), with success parameters \(2 - 1 / \alpha\) and \(p / [1 - (1 - p)\alpha]\). The density function \(h\) of \(Y_N\) is given as follows:

If \((1 - p) \alpha = 1 / 2\) then \[h(x) = (x + 1) \left(2 - \frac 1 \alpha\right)^2 \left(\frac 1 \alpha - 1\right)^x, \quad x \in \N\]
If \((1 - p) \alpha \ne 1 / 2\) then \[h(x) = \frac{p (2 \alpha - 1)}{(1 - \alpha) [1 - 2 \alpha (1 - p)]} \left[\left(\frac 1 \alpha - 1\right)^{x + 1} - \left[\frac{(1 - \alpha)(1 - p)}{1 - \alpha(1 - p)}\right]^{x + 1}\right], \quad x \in \N \]

Details:

As with the covering graph, there is a direct probabilistic proof, although one that is a bit more complicated. Recall that we have a sequence of Bernoulli trials that indicate whether each point in the random walk is accepted or rejected. The success probability is \(p\) and \(N\) is the index number of the first accepted point. We now define another sequence of Bernoulli trials: Let \(J_n = 1\) if \(Y_{n + 1} = Y_n + 1\) and and let \(J_n = 0\) if \(Y_{n + 1} = Y_n\). Then \(\bs{J} = (J_1, J_2, \ldots)\) is an independent sequence and \(\P(J_n = 1) = P(x, x + 1) = 1 - \alpha\) (independent of \(x \in \N\)). Note that \(Y_N = X + M\) where \(M = \sum_{n = 1}^{N - 1} J_n\). But \(N - 1\) has the geometric distribution on \(\N\) with success parameter \(p\) and is independent of \(\bs{J}\). By a basic result in probability theory, \(M\) has the geometric distribution on \(\N\) with success parameter \[\frac{p}{(1 - \alpha) + p - p(1 - \alpha)} = \frac{p}{1 - (1 - p) \alpha}\] and is independent of \(X\). Of course \(X\) has the geometric distribution on \(\N\) with success parameter \(2 - 1 / \alpha\).

In part (a), the success parameters are the same, so \(Y_N\) has the negative binomial distribution on \(\N\) with stopping parameter 2 and success parameter \(2 - 1 / \alpha\).

Geometric Distributions

Graph Summary

As noted above, the constant rate distributions for the graphs \((\N, \lt)\), \((\N, \upa)\), and \((\N, \rta)\) in propositions , , and , as well as the constant rate distribution for \((\N, \le)\) studied in Section 1 are all geometric distributions. In a sequence of Bernoulli trials, the geoemtric distribution on \(\N\) governs the number of failures before the first success. To summarize, the distribution with constant rate \(\alpha \in (0, 1)\) for \((\N, \le)\) is geometric with success parameter \(\alpha\). The distribution with constant rate \(\alpha \in (0, \infty)\) for \((\N, \lt)\) is geometric with success parameter \(\alpha / (1 + \alpha)\). The distribution with constant rate \(\alpha \in (1, \infty)\) for \((\N, \upa)\) is geometric with success parameter \((\alpha - 1) / \alpha\). The distribution with constant rate \(\alpha \in (1 / 2, 1)\) for \((\N, \rta)\) is geometric with success parameter \((2 \alpha - 1) / \alpha\). Here is another way of looking at the results.

Suppose that \(X\) has the geometric distribution on \(\N\) with success parameter \(p \in (0, 1)\), so that \(X\) has density function \(f\) given by \(f(x) = p (1 - p)^x\) for \(x \in \N\). Then

\(X\) has constant rate \(p\) for \((\N, \le)\).
\(X\) has constant rate \(p / (1 - p)\) for \((\N, \lt)\).
\(X\) has constant rate \(1 / (1 - p)\) for \((\N, \upa)\).
\(X\) has constant rate \(1 / (2 - p)\) for \((\N, \rta)\).

Details:

The results follow by solving for \(\alpha\) in terms of \(p\). In terms of part (c), note that the standard graph (\(\N, \le)\) is completely uniform in the terminology of Section 1.2, since there is one path in the covering graph from \(x\) to \(y\) for each \(x, \, y \in \N\) with \(x \lt y\). So by a result in Section 1.5, the fact that \(X\) has constant rate \(1 / (1 - p)\) for \((\N, \upa)\) implies that \(X\) has constant rate \(1 / (1 - p)^n\) for \((\N, \upa^n)\) for each \(n \in \N\), and constant rate \(p\) for \((\N, \le)\).

The app below is a simulation of the geometric distribution with success parameter \(p\). The parameter \(p\) can be varied with the scrollbar and in addition, the app shows the rate constants \(\alpha_1\) for \((\N, \le)\), \(\alpha_2\) for \((\N, \lt)\), \(\alpha_3\) for \((\N, \upa)\), and \(\alpha_4\) for \((\N, \rta)\)

The geometric distribution also plays a prominent role for the random variable \(Y_N\) in the thinned process for each of the graphs: \(Y_N\) has a geometric distribution for \((\N, \lt)\) and is the sum of two independent geometric variables for the graphs \((\N, \upa)\) and \((\N, \rta)\). Finally, we already know from Section 1 that if \(X\) has the geometric distribution on \(\N\) with success parameter \(p \in (0, 1)\), then \(X\) has entropy \[H(X) = -\ln p - \frac{1 - p}{p} \ln (1 - p)\] and that \(X\) maximizes entropy over all random variables \(Y \in \N\) with \(\E(Y) = \E(X) = 1 / p\). The entropy is expressed in terms of the rate constants for the various graphs in , , and .

Modified Geometric Distribution

A useful variation of the geometric distribution arises in a sequence of independent trials, where the probability of success on the first trial may be different than the common probability of success on the remaining (Bernoulli) trials. This family of distributions will be important in Chapter 8 on subset spaces.

Consider a sequence of independent trails where trial 1 has probability of success \(p_0 \in (0, 1)\) and the remaining trials have probability of success \(p \in (0, 1)\). Let \(N\) denote the number of failures before the first success. Then \(N\) has the modified geometric distribution on \(\N\) with success parameters \(p_0, \, p\). The probability density function \(f\) of \(N\) is given by \[f(0) = p_0; \quad f(x) = (1 - p_0) p (1 - p)^{x - 1}, \; x \in \N_+\]

Details:

Let \((I_1, I_2, \ldots)\) denote the sequence of independent trials as described. Then \(\P(N = 0) = \P(I_1 = 1) = p_0\). For \(x \in \N_+\), \[\P(N = x) = \P(I_1 = 0, I_2 = 0, \cdots, I_x = 0, I_{x + 1} = 1) = (1 - p_0)(1 - p)^{x -1} p\]

Of course, if \(p_0 = p\), the modified geometric distribution reduces to the ordinary geometric distribution on \(\N\) with success parameter \(p\). In the following propositions, \(N\) has the modified geometric distribution on \(\N\) with success parameters \(p_0, \, p \in (0, 1)\).

The conditional distribution of \(N\) given \(N \gt 0\) is the geometric distribution on \(\N_+\) with success parameter \(p\).

Details:

\[\P(N = x \mid N \gt 0) = \frac{f(x)}{1 - f(0)} = (1 - p)^{x - 1} p, \quad x \in \N_+\]

The mean and variance of \(N\) are

\(\E(N) = (1 - p_0) / p\)
\(\var(N) = (1 - p_0) (1 + p_0 - p) / p^2\)

Details:

Direct computations are simple, but we can also use and elementary facts about the geometric distribution on \(\N_+\).

Conditioning on \(N \gt 0\) gives \(\E(N) = \P(N \gt 0) \E(N \mid N \gt 0) = (1 - p_0) (1 / p)\)
Similarly, \(\E(N^2) = \P(N \gt 0) \E(N^2 \mid N \gt 0) = (1 - p_0) [(1 - p) / p^2 + 1 / p^2]\). And then \(\var(N) = \E(N^2) - [\E(N)]^2\).

The probability generating function \(P\) of \(N\) is given by \[P(t) = \frac{p_0 + (p - p_0) t}{1 - (1 - p) t}, \quad t \in [0, \infty)\]

Details:

Once again we use and the probability generating function of the geometric distribution on \(\N_+\): \[P(t) = \E(t^N) = \P(N = 0) \E(t^N \mid N = 0) + \P(N \gt 0) \E(t^N \mid N \gt 0) = p_0 + (1 - p_0) \frac{p t}{1 - (1 - p) t}\] Simplifying gives the result.

The reliability function \(F\) and the rate function \(r\) of \(N\) for the graph \((\N, \le)\) are as follows:

\(F(0) = 1\) and \(F(x) = (1 - p_0) (1 - p)^{x - 1}\) for \(x \in \N_+\).
\(r(0) = p_0\) and \(r(x) = p\) for \(x \in \N_+\).

Details:

Of course, \(\P(N \ge 0) = 1\). In terms of the independent trials, the event \(\{N \ge x\}\) for \(x \in \N_+\) means that the first \(x\) trials were failures, so \(F(x) = (1 - p_0) (1 - p)^{x - 1}\).
This follows from (a) and the density function in .

So \(N\) has constant rate \(p\) on \(\N_+\). On the other hand, if \(p_0 \ne p\), the memoryless property \(F(x + y) = F(x) F(y)\) for the semmigroup \((\N, +)\) never holds for \(x, \, y \in \N_+\).