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 \[u_{n + 1}(x) = \sum_{z = 0}^x u_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 walk 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}\).

From the walk functions and a binomial identity, \[U(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)\]

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\]

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_+\]

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\).

1. The constant rate properties reduces to \(f(0) = \alpha\) and \[F(x + 1) = (1 - \alpha) F(x), \quad x \in \N\] so \(F(x) = (1 - \alpha)^x\) for \(x \in \N\).
2. Recall that for any graph, the constant rate property implies the constant average rate property of order \(n\) for every \(n \in \N_+\). To complete the equivalence, suppose that \(X\) has constant average rate of order \(n \in \N_+\). Our assumption is \[ R_n(x) = \sum_{x_1 \le x_2 \le \cdots \le x_n \le x} r(x_1) r(x_2) \cdots r(x_n) = \alpha^n \binom{x + n}{n}, \quad x \in \N \] for some \(\alpha \in (0, 1)\). We will prove by induction on \(x \in \N\) that \(r(x) = \alpha\). When \(x = 0\), equation above gives \(r^n(0) = \alpha^n\) so \(r(0) = \alpha\). Suppose that \(x \in \N\) and that \(r(y) = \alpha\) for \(y \in \{0, 1, \ldots, x\}\). We will show that \(r(x + 1) = \alpha\). For \(k \in \{0, l, \ldots, n\}\), let \(P_k\) denote the set of walks of length \(n\) terminating in \(x + 1\) with exactly \(k\) points less that \(x + 1\) (and so the last \(n - k\) points are each \(x + 1\)). The walks in \(P_k\) can be mapped one-to-one onto the set of walks of length \(k\) terminating in \(x\), and hence there are \(\binom{x + k}{k}\) such walks. Hence by the induction hypothesis \[R_n(x) = \sum_{k = 0}^n \binom{x + k}{k} \alpha^k r^{n - k}(x + 1)\] But also by a standard binomial identity, \[\alpha^n \binom{x + 1 + n}{n} = \sum_{k = 0}^n \alpha^k \alpha^{n - k} \binom{x + k}{x}\] Hence the last equation can be written as \[\sum_{k=0}^n \binom{x + k}{k} \alpha^k \left[r^{n - k}(x + 1) - \alpha^{n - k}\right] = 0\] The only solution is \(r(x + 1) = \alpha\).
3. The memoryless property is \[F(x + y) = F(x) F(y), \quad x, \, y \in \N\] The only solution is \(F(x) = (1 - \alpha)^x\) where \(\alpha = 1 - F(1)\).
4. Recall that the exponential property implies the memoryless property.

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*}

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\).

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\).

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 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[U(X, \alpha); X \le x]\] where \(U\) is the left generating function of \((\N, \le)\). Hence \[\E(N_x) = \E\left[\frac{1}{(1 - \alpha)^{X + 1}}; 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\]

From the general theory in Section 1.5, \[h(x) = p \alpha U[x, (1 - p) \alpha] F(x), \quad x \in S\] where \(U\) is the left generating function of \((\N, \le)\) and where \(F\) is the reliability function of the distribution for the \((\N, \le)\). But \(U\) is given by \(U(x, t) = 1 / (1 - t)^{x + 1}\) for \(x \in \N\) and \(t \in (-1, 1)\), and \(F\) is given by \(F(x) = (1 - \alpha)^x\) for \(x \in \N\). Substituting gives the result.

This follows immediately from and general results in Section 2.4.

The hypotheses are \begin{align} f(0) &= [1 - F(t)] \sum_{n = 0}^\infty f(n t), \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\).

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 .