The standard discrete semigroup is \((\N, +)\) amd its associated graph is the standard discrete graph \((\N, \le)\). These spaces form the usual models for discrete time. Counting measure \(\#\) is the reference measure and is the unique invariant measure for \((\N, +)\) up to multiplcation by posiitve constants. As usual, we start with the path functions and the path generating function.
The path function \(\gamma_n\) of order \(n \in \N\) for \((\N, \le)\) is given by \[\gamma_n(x) = \binom{x + n}{n}, \quad x \in \N\]
For a proof by induction, note that the expression is correct when \(n = 0\). Assume that the expression is correct for a given \(n \in \N\). Then \[\gamma_{n + 1}(x) = \sum_{z = 0}^x \gamma_n(z) = \sum_{z = 0}^x \binom{n + z}{x} = \binom{n +1 + x}{x}, \quad x \in \N\] by a binomial identity. For a combinatorial proof, to construct a path of length \(n\) in \((\N, \le)\) ending in \(x\) we need to select a multiset of size \(n\) from \(\{0, 1, \ldots, x\}\). The number of ways to do this is \(\binom{x + n}{n}\).
The generating function \(\Gamma\) for \((\N, \le)\) is given by \[\Gamma(x, t) = \frac{1}{(1 - t)^{x+1}}, \quad x \in \N, \, t \in (-1, 1)\]
From the path function and a binomial identity, \[\Gamma(x, t) = \sum_{n=0}^\infty \binom{n+x}{x} t^n = \frac{1}{(1 - t)^{x+1}}, \quad x \in \N, \, t \in (-1, 1)\]
The Möbius function \(\mu\) of \((\N, +)\) is given by: \[\mu(x) = \begin{cases} 1, & x = 0 \\ -1, & x = 1 \\ 0, & \text{otherwise} \end{cases}\]
This is well known, but a proof is also easy from the definition: \(\mu(0) = 1\) and \[\mu(x) = -\sum_{t = 0}^{x - 1} \mu(t), \quad x \in \N\]
So it follows that the Möbius kernel \(M\) of \((\N, \le)\) is given by \[M(x, y) = \mu(y - x) = \begin{cases} 1, & y = x \\ -1, & y = x + 1 \\ 0, & \text{otherwise} \end{cases}\]
Suppose that \(X\) is a random variable in \(\N\) with probability density function \(f\). As usual, when a particular graph is under discussion, we assume that the graph supports the distribution of \(X\).
For the graph \((\N, \le)\), the reliability function \(F\) and the rate function \(r\) of \(X\) are given by \begin{align*} F(x) &= \P(x \le X) = \sum_{y=x}^\infty f(y), \quad x \in \N \\ r(x) &= \frac{f(x)}{F(x)} = \frac{f(x)}{\sum_{y=x}^\infty f(y)}, \quad x \in \N \end{align*} Both functions uniquely determine the distribution.
The formulas for the reliability function and the rate function follow from the definitions. Clearly the density function \(f\) can be recovered from \(F\) by \[f(x) = F(x) - F(x + 1), \quad x \in \N\] but of course this is also the Möbius inversion formula. The density function can be recovered from \(r\) recursively by \(f(0) = r(0)\) and \[f(x) = r(x) \left[1 - \sum_{n=0}^{x - 1} f(n)\right], \quad x \in \N_+\]
The graph \((\N, \le)\) is stochastic: the (right) neighbor set at \(x \in \N\) is \(\{x, x + 1, x + 2, \ldots\}\) and the \(\sigma\)-algebra generated by these sets is \(\ms P(\N)\), the power set of \(\N\). Finally, the reliability function determines the distribution on \(\ms P(\N)\) as noted in . The standard moment result for the graph \((\N, \le)\) is given next.
Suppose again that \(X\) is a random variable in \(\N\). Then \[\sum_{x=0}^\infty \binom{n+x}{n} \P(X \ge x) = \E\left[\binom{n + 1 + X}{n + 1}\right], \quad n \in \N\]
When \(n = 0\), this is equivalent to the well-known result from elementary probability \[\E(X) = \sum_{x=0}^\infty \P(X \gt x) = \sum_{x=1}^\infty \P(X \ge x)\]
Of course, we are most interested in random variables with the exponential, memoryless, and constant rate properties.
Suppose that \(X\) is a random variable in \(\N\). The following are equivalent:
The exponential distribution on \((\N, +)\) with constant rate \(\alpha \in (0, 1)\) has density function \(f\) given by \[f(x) = \alpha (1 - \alpha)^x, \quad x \in \N\]
Let \(F\) denote the reliability function and \(r\) the rate functioon of \(X\) for \((\N, \le)\). Let \(R_n\) denote the cumulative rate function of \(X\) of order \(n \in \N\).
The equivalent conditions in are well known, of course, except for (b). As we will see in Chapter 5, the proofs for parts (a) and (b) work more generally for rooted trees. Of course, the exponential distribution for \((\N, +)\) with rate \(\alpha \in (0, 1)\) is the standard geometric distribution on \(\N\) with success parameter \(\alpha\). This distribution governs the number of failures before the first success in a sequence of Bernoulli trials with success parameter \(\alpha\).
Open the simulation of the geometric distribution with rate \(\alpha\). Vary \(\alpha\) with the scrollbar and note the shape of the probability density function. Run the simulation and compare the empirical denisty function to the probability density function.
Suppose again that \(X\) is a random variable in \(\N\). For the graph \((\N, \le)\), if \(X\) has increasing rate then \(X\) has increasing average rate.
Let \(r\) denote the rate function and \(R\) the cumulative rate function of \(X\) for \((\N, \le)\). We need to show that if \(x, \, y \in \N\) and \(x \le y\) then \((y + 1) R(x) \le (x + 1) R(y)\). Note that \begin{align*} (x + 1) R(y) &= (x + 1) \sum_{t = 0}^ y r(t) = (x + 1) \left[\sum_{t = 0}^x r(t) + \sum_{t = x + 1}^y r(t)\right] \\ &= (x + 1) R(x) + (x + 1) \sum_{t = x + 1}^y r(t) \end{align*} But since \(r\) is increasing, \begin{align*} (x + 1) \sum_{t = x + 1}^y r(t) & \ge (x + 1) (y - x) r(x + 1) \ge (x + 1) (y - x) r(x) \\ & \ge (y - x) \sum_{t = 0}^x r(t) = (y - x) R(x) \end{align*}
Suppose that \(X\) has the exponential distribution on \((\N, +)\) with constant rate \(\alpha \in (0, 1)\). Then \(X\) has a compound Poisson distribution. Specifically, \(X\) can be decomposed as \[X = U_1 + U_2 + \cdots + U_N\] where \(\bs{U} = (U_1, U_2, \ldots)\) is a sequence of independent copies of \(U\), and \(U\) has the logarithmic distribution on \(\N\): \[\P(U = n) = -\frac{(1 - \alpha)^n}{n \ln \alpha}, \quad n \in \N_+\] and where \(N\) is independent of \(\bs U\) and has the Poisson distribution with parameter \(-\ln \alpha\).
The exponential distribution on \((\N, +)\) with rate \(\alpha \in (0, 1)\) is of course the geometric distribution with success parameter \(\alpha\). It's well known that the geometric distribution has the decomposition stated in the theorem. Here is a direct proof: The probability generating function \(P\) of \(U\) is given by \[P(t) = \frac{\ln[1 - (1 - \alpha) t]}{\ln \alpha}, \quad |t| \lt \frac{1}{1 - \alpha}\] The probability generating function \(Q\) of the \(N\) is given by \[Q(t) = \exp[-\ln(\alpha) (t - 1)], \quad t \in \R\] Hence the probability generating function of \(U_1 + U_2 + \cdots + U_N\) is \(Q \circ P\), given by \[Q[P(t)] = \frac{1}{1 - (1 - \alpha)t}, \quad |t| \lt \frac{1}{1 - \alpha}\] which we recognize as the probability generating function of the geometric distribution with success parameter \(\alpha\).
Proposition shows how an exponential variable for \((\N, +)\) can be written as a Poisson random sum of independent, identically distributed variables. The following result shows how the exponential variable can be written in terms of an infinte sum of independent Poisson variables.
Suppose that \(\bs V = (V_1, V_2, \ldots)\) is a sequence of independent variables and that \(V_n\) has the Poisson distribution on \(\N\) with parameter \(\lambda_n = (1 - \alpha)^n / n\) for \(n \in \N_+\) where \(\alpha \in (0, 1)\). Then \(X = \sum_{n=1}^\infty n V_n\) has the exponential distribution on \((\N, +)\) with rate \(\alpha\).
For \(n \in \N_+\), the probability generating function of \(V_n\) is \[\E\left(t^{V_n}\right) = \exp[\lambda_n (t - 1)] = \exp\left[\frac{(1 - \alpha)^n}{n}(t - 1)\right]\] Hence the probability generating function of \(X\) is \begin{align*} \E\left(t^X\right) &= \prod_{n = 1}^\infty \E\left(t^{n V_n}\right) = \prod_{n = 1}^{\infty} \exp\left[\frac{(1 - \alpha)^n}{n}(t^n - 1)\right] \\ &= \exp\left[\sum_{n = 1}^\infty \frac{(1 - \alpha)^n}{n}(t^n - 1)\right] = \exp[-\ln(1 - (1 - \alpha)t) + \ln \alpha] \\ &= \frac{\alpha}{1 - (1 - \alpha)t}, \quad |t| \lt \frac{1}{1 - \alpha} \end{align*} But this is the probability generating function of the geometric distribution with rate parameter \(\alpha\).
If \(X\) has constant rate \(\alpha \in (0, 1)\) for the graph \((\N, \le)\) then \(X\) maximizes entropy over all random variables \(Y\) on \(\N\) with \(\E(Y) = (1 - \alpha) / \alpha\).
From general results in Section 1.5, the distribution of a random variable \(X\) with constant rate \(\alpha\) for a graph \((S, \rta)\) maximizes entropy over all random variables \(Y\) in \(S\) and \(\E(\ln[F(Y)]) = \E(\ln[F(X)])\). For the graph considered here, this condition reduces to \(\E(Y) = \E(X) = (1 - \alpha) / \alpha\).
Recall that the random walk \(\bs Y = (Y_1, Y_2, \ldots)\) on the semigroup \((\N, +)\) associated with a random variable \(X\) can be constructed from a sequence \(\bs X = (X_1, X_2, \ldots)\) of independent copies of \(X\) by means of partial sums, so that \(Y_n = \sum_{i=1}^n X_i\). So in this cases, the term random walk has its elementary meaning. The random walk \(\bs Y\) on the graph \((\N, \le)\) associated with \(X\) can be constructed from the sequence \(\bs X\) by means of record variables. Recall also that the random walk \(\bs Y\) corresponding to a constant rate distribution is the most random
way to put points in the graph in the sense that given \(Y_{n+1} = x\), the sequence \((Y_1, Y_2, \ldots, Y_n)\) is uniformly distributed on the set of paths of length \(n\) in the graph that terminate in \(x\). Our main interest in this section is the random walk on \((\N, +)\) (equivalently the random walk on \((\N, \le)\)) associated with an exponential distribution on \((\N, +)\) (equivalently the constant rate distribution on \((\N, \le)\)).
Suppose that \(\bs Y = (Y_1, Y_2, \ldots)\) is the random walk on \((\N, +)\) associated with the exponential distribution with rate \(\alpha \in (0, 1)\).
Of course we recognize the distribution of \(Y_n\) as the negative binomial distribution on \(\N\) with parameters \(n\) and \(\alpha\). This distribution governs the number of failures before the \(n\)th success in a sequence of Bernoulli trials with success parameter \(\alpha\).
Open the simulation of the negative binomial distribution. Vary \(n\) and \(\alpha\) with the scrollbar and note the shape of the probability density function. Run the simulation and compare the empirical denisty function to the probability density function.
Next we consider the point process associated with a random walk \(\bs Y = (Y_1, Y_2, \ldots)\) on \((\N, \le)\). Specifically, let \(N_x = \#\{n \in \N_+: Y_n \le x\}\) for \(x \in \N\). We are interested in the function that plays the role that the renewal function plays in ordinary renewal theory, that is, \(x \mapsto \E(N_x)\).
Suppose again that \(\bs Y = (Y_1, Y_2, \ldots)\) is the random walk on \((\N, +)\) corresponding to the exponential distribution with rate \(\alpha \in (0, 1)\). Then \[\E(N_x) = \frac{\alpha}{1 - \alpha}(x + 1), \quad x \in \N\]
Recall that if \(\bs Y\) is the random walk on \((\N, \le)\) corresponding to \(X\), where \(X\) has constant rate \(\alpha \in (0, 1)\) then \[\E(N_x) = \E[\Gamma(X, \alpha); X \le x]\] where \(\Gamma\) is the generating function of \((\N, \le)\). Hence \[\E(N_x) = \E\left[\frac{1}{(1 - \alpha)^{X+!}}; X \le x\right] = \sum_{t=0}^x \frac{1}{(1 - \alpha)^{t+1}} \alpha (1 - \alpha)^t = \frac{\alpha}{1 - \alpha}( x +1), \quad x \in \N\]
Our next result concerns thinning the random walk. Suppose again that \(\bs Y = (Y_1, Y_2, \ldots)\) is a random walk on \((\N, \le)\). 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_+\). As we will see in Section 2, this distribution is exponential for the semigroup \((\N_+, +)\), but with rate \(p / (1 - p)\). 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 that \(\bs Y\) is the random walk on \((\N, +)\) corresponding to the exponential distribution with rate \(\alpha \in (0, 1)\). Then \(Y_N\) has the exponential distribution on \((\N, +)\) with rate \(\alpha p / (1 - \alpha + \alpha p)\), and hence with density function \(h\) given by \[h(x) = \frac{\alpha p}{1 - \alpha + \alpha p} \left(\frac{1 - \alpha}{1 - \alpha + \alpha p}\right)^x, \quad x \in \N\]
From the general theory in Section 1.5, \[h(x) = p \alpha \Gamma[x, (1 - p) \alpha] F(x), \quad x \in S\] where \(\Gamma\) is the generating function and \(F\) is the reliability function of the distribution for the graph. For the graph \((\N, \le)\), the generating function \(\Gamma\) is given by \(\Gamma(x, t) = 1 / (1 - t)^{x + 1}\) for \(x \in \N\) and \(t \in (-1, 1)\) and the reliability function \(F\) is given by \(F(x) = (1 - \alpha)^x\) for \(x \in \N\). Substituting gives the result.
Our last results in this subsection deal with compound Poisson distributions.
Suppose again that \(\bs Y = (Y_1, Y_2, \ldots)\) is the random walk on \((\N, +)\) corresponding to the exponential distribution with constant rate \(\alpha \in (0, 1)\). For \(n \in \N_+\), \(Y_n\) has a compound Poisson distribution. Specifically, \[Y_n = W_1 + W_2 + \cdots + W_N\] where \((W_1, W_2, \ldots)\) is a sequence of independent variables, each with the logarithmic distribution on \(\N\) with parameter \(\alpha\), and where \(N\) is independent of \(\bs W\) and has the Poisson distribution with parameter \(-n \ln \alpha\).
This follows immediately from and general results in Section 2.4.
Consider again the positive semigroup \((\N, +)\). For \(t \in \N_+\), the sub-semigroup generated by \(t\) is \[\N t = \{n t: n \in \N\}\] and the corresponding quotient space, as defined in Section 2.8, is \(\{0, 1, \ldots, t - 1 \}\). The general assumptions in that section hold, so that \(x \in \N\) can be written uniquely as \[x = t n_t(x) + z_t(x)\] where \(n_t(x)= \lfloor x/t \rfloor \in \N\) and \(z_t(x) = x - n_t(x) = x \bmod t \in \{0, 1, \ldots t - 1\}\). The following proposition follows from the general results in Section 2.8.
Suppose that \(t \in \N_+\) and that \(X\) has the exponential distribution on \((\N, +)\) with rate \(\alpha \in (0, 1)\). Then
As in Section 3.1 on standard continuous spaces, we are interested in a converse that is stronger than the general converse in Section 2.8.
Suppose that \(X\) is a random variable in \(\N\), with density function \(f\) and reliability function \(F\) for \((\N, \le)\). Then the independence of \(Z_t\) and \(\{N_t = 0\}\) is equivalent to \[ f(k) = [1 - F(t)] \sum_{n=0}^\infty f(nt + k) \] for all \(t \in \N_+\) and all \(k \in \{0, \ldots, t - 1\}\).
However, as in the continuous case, it is easy to see that if \(X\) has an exponential distribution on \((\N, +)\) then the equation in holds for all \(t \in \N_+\) and \(k \in \N\), not just \(k \in \{0, 1, \ldots, t - 1\}\).
Suppose that the equation in holds for \(k = 0\) and for \(k = t\), for all \(t \in \N_+\). Then \(X\) has an exponential distribution on \((\N, +)\).
The hypotheses are \begin{align} f(0) &= [1 - F(t)] \sum_{n=0}^\infty f(nt), \quad t \in \N_+ \\ f(t) &= [1 - F(t)] \sum_{n=0}^\infty f[(n+1)t], \quad t \in \N_+ \end{align} From these equations, it follows that \[f(t) = f(0)F(t), \quad t \in \N_+\] and hence \(X\) has constant rate \(\alpha = f(0)\) for \((\N, \le)\). Equivalently \(X\) has the exponential distribution for \((\N, +)\) with rate \(\alpha\) which of course is the geometric distribution with success parameter \(\alpha\).
However, there are non-geometrically distributed variables for which \(N_t\) and \(Z_t\) are independent. The following result is easy to verify.
Suppose that the support of \(X\) is \(\{0, 1\}\) or \(\{0, 2\}\) or \(\{c\}\) for some \(c \in \N\). Then \(N_t\) and \(Z_t\) are independent for all \(t \in \N_+\).
The following theorem gives a partial converse:
Suppose that \(X\) takes values in a proper subset of \(\N\) and that \(Z_t\) and \(\{N_t = 0\}\) are independent for all \(t \in \N_+\). Then the support of \(X\) is one of the sets in .
Let \(f\) denote the density function and let \(F\) denote the reliability function of \(X\) for \((\N, \le)\). First, we will use induction on \(a \in \N\) to show that if \(X\) takes values in \(\{0, 1, \ldots, a\}\), then the support of \(X\) is one of the sets in Proposition . If \(a = 0\) or \(a = 1\), the result is trivially true. Suppose that the statement is true for a given \(a \in \{2, 3, \ldots\}\), and suppose that \(X\) takes values in \(\{0, 1, \ldots, a + 1\}\). With \(t = a + 1\), the equation in Proposition becomes \[ f(k) = \sum_{j=0}^a f(j) \sum_{n=0}^\infty f[n(a + 1) + k], \quad k \in \{0, \ldots, a \} \] But \(\sum_{j=0}^a f(j) = 1 - f(a + 1)\). Hence the equation above gives \begin{align} f(0) &= [1 - f(a + 1)][f(0) + f(a + 1)], \quad (k = 0) \\ f(k) &= [1 - f(a + 1)]f(k), \quad k \in \{1, \ldots, a \} \end{align} Suppose that \(f(k) > 0\) for some \(k \in \{1, \ldots, a \}\). Then from the last equation \(f(a + 1) = 0\). Hence \(X\) takes values in \(\{0, \ldots, a \}\), so by the induction hypothesis, the support set of \(X\) is \(\{0, 1\}\), \(\{0, 2\}\), or \(\{c\}\) for some \(c\). Suppose that \(f(k) = 0\) for all \(k \in \{1, \ldots, a\}\). Thus, \(X\) takes values in \(\{0, a + 1\}\). But then the equation in Proposition with \(t = a\) and \(k = 0\) gives \(f(0) = f(0)f(0)\). If \(f(0) = 0\) then the support of \(X\) is \(\{a + 1\}\). If \(f(0) = 1\) then the support of \(X\) is \(\{0\}\).
To complete the proof, suppose that \(X\) takes values in a proper subset of \(\N\), so that \(f(k) = 0\) for some \(k \in \N\). Then \(1 - F(t) = \P(X \lt t) > 0\) for \(t\) sufficiently large and hence by the equation in Proposition , \(f(t + k) = 0\) for \(t\) sufficiently large. Thus \(X\) takes values in \(\{0, 1, \ldots, a\}\) for some \(a\), and hence the support of \(X\) is one of the sets in .