In this section we consider sub-semigroups of the standard discrete space \((\N, +)\) that was studied in Section 1. Of particular interest are numerical semigroups given in defintion below.
First we review some basic definitions.
Suppose that \(S \subseteq \N\). Then \((S, +)\) is a positive sub-semigroup of \((\N, +)\) if \(0 \in S\) and \(x + y \in S\) for all \(x, \, y \in S\). The associated partial order graph \((S, \preceq)\) is a subgraph of \((\N, \le)\).
Of course, the meaning of sub-semigroup is closure under the semigroup operation, so if \(x, \, y \in S\) then \(x + y \in S\).
As usual, \(S_+ = S - \{0\}\). Recall that the partial order \(\preceq\) on \(\N\) associated with the set \(S\) is given by \(x \preceq y\) for \(x, \, y \in \N\) if and only if \(x + z = y\) for some \(z \in S\). Restricted to \(S\), the relation \(\preceq\) is the partial order associated with \((S, +)\). So \(x \preceq y\) implies \(x \le y\) for \(x, \, y \in \N\) but not conversely, in general. That is, \((S, +)\) is not necessarily algebraically complete. The partial order graph \((S, \preceq)\) is left finite and hence the associated \(\sigma\)-algebra is \(\ms P(S)\), the collection of all subsets of \(S\). A standard way to construct a subsemigroup is by means of a generating set.
Suppose that \(A \subseteq \N\) is nonempty with \(0 \notin A\). The positive semigroup \((S, +)\) generated by \(A\) is the interesection of all positive sub-semigroups of \((\N, +)\) that contain \(A\). That is, \[S = \{x_1 + x_2 + \cdots x_n: n \in \N, \text { and } x_1, \, x_2, \ldots, x_n \in A\}\] where as usual, an empty sum is interpreted as \(0\). The generating set \(A\) is minimal if no proper subset of \(A\) generates the same semigroup.
Often the base set \(S\) in definition is denoted \(\langle A \rangle\).
If \((S, +)\) is a positive sub-semigroup of \((\N, +)\) then the set \(I\) of irreducible elements of \((S, +)\) is the unique minimal generating set of \((S, +)\).
The semigroup \((S, +)\) is left finite, so by a result in Section 2.2, if \(x \in S\) then \(x = i_1 + i_2 + \cdots + i_n\) for some \(n \in \N\) and \(i_1, \, i_2, \ldots, i_n \in I\). That is, \(\langle I \rangle = S\). Clearly \(I\) is also miniimal. Suppose that \(J\) is a proper subset of \(I\) and that \(i \in I - J\). But then \(i \notin \langle J \rangle\) since \(i\) is irreducible in \((S, +)\). Conversely, if \(A\) is a generating set for \((S, +)\) then clearly \(I \subseteq A\).
Suppose again that \((S, +)\) is a positive sub-semigroup of \((\N, +)\) and that \(I\) is the set of irreducible elements. As usual, we let \((S, \upa)\) denote the covering graph corresponding to the partial order graph \((S, \preceq)\). Then for \(x, \, y \in S\), \(x \upa y\) if and only if \(y = x + i\) for some \(i \in I\). Our next result involves the quotient as studied in Section 2.8.
Suppose again that \((S, +)\) is a postive sub-semigroup of \((\N, +)\) and let \(m = \min (S_+)\). The quotient of \((\N, +)\) by \((S, +)\) is the set \(T = \{0, 1, \ldots m - 1\}\).
By definition, the quotient set is \(\bigcap_{t \in S_+} (t + \N)^c\). But \(t + \N = \{t, t + 1, t + 2, \ldots\}\) for \(t \in \N_+\) and hence \((t + \N)^c = \{0, 1, \ldots t - 1\}\). The intersection of these sets over \(t \in S_+\) is \(\{0, 1, \ldots m - 1\}\).
As we will see, elements in \(\N\) generally do not have a unique sum over \(S\) and \(T\), again as discussed in Section 2.8. But we do have the following result:
Suppose again that \((S, +)\) is a positive sub-semigroup of \((\N, +)\), with quotient \(T\) as described in . If \((S, +)\) is complete, then every \(x \in \N\) has a unique sum \(x = y + z\) where \(y \in S\) and \(z \in T\).
From the general theory in Section 2.8, we need to show that for \(x \in \N\), the set \(A_x = \{t \in S: t \le x\}\) has a unique maximal element with respect to \(\preceq\). Since \(A_x\) is finite, such maximal elements exist, so suppose that \(a, \, b \in A_x\) are maximal elements with respect to \(\preceq\). Since \(\le\) is a total order, either \(a \le b\) or \(b \le a\). Suppose without loss of generality that \(a \le b\), so that \(a + (b - a) = b\). Since \((S, +)\) is complete, and \(a, \, b \in S\) we have \(b - a \in S\) also, and hence \(a \preceq b\). But \(a\) is maximal and hence \(a = b\).
Of particular interest are numerical semigroups. These are positive sub-semigroups of \((\N, +)\) that contains all but finitely many elements of \(\N\).
A positive sub-semigroup \((S, +)\) of \((\N, +)\) is a numerical semigroup if \(\N - S\) is finite.
In part (c), the maximum is with respect to the ordinary order \(\le\), of course.
So if \(m \in \N\) is the Frobenius number of \((S, +)\) then \(\{m + 1, m + 2, \ldots\} \subseteq S\). Sets that generate numerical semigroups have some special properties.
A semigroup \((S, +)\) generated by a set \(A \subset \N\) is a numerical semigroup if and only if \(\gcd(A) = 1\).
Suppose that \(n = \gcd(A) \in \{2, 3, \ldots\}\). The \(a\) is a multiple of \(n\) for every \(a \in A\) and hence \(x\) is a multiple of \(n\) for every \(x \in S = \langle A \rangle\). So the set of gaps \(\N - S\) is infinite.
Let \(I\) denote the set of irreducible elements of the numerical semigroup \((S, +)\) (so that \(I\) is the minimal generaing set). Then
In part (c), the minimum is with respect to the ordinary order \(\le\).
Suppose that \((S, +)\) is a numerical semigroup with multiplicity \(m \in \N_+\). By , the quotient set is \(T = \{0, 1, \ldots m - 1\}\). However, the sum of an element \(x \in \N\) over \(S\) and \(T\) is not generally unique.
Suppose that \((S, +)\) is a nontrivial numerical semigroup with Frobenius number \(b \in \{2, 3, \ldots\}\) and quotient set \(T\). Then
Since \((S, +)\) is nontrivial, the multiplicity \(m \gt 1\) and hence \(1 \in T\) and \(1 \notin S\).
Once again, suppose that \((S, +)\) is a sub-semigroup of \((\N, +)\), as defined in . Since the corresponding partial order graph \((S, \preceq)\) is a lattice, the graph is stochastic. That is, the reliability function \(F\) of a probability measure \(P\) on \(\ms P(S)\) uniquely determines \(P\). As usual, our primary interest is in exponential distributions for \((S, +)\) and constant rate distributions for the corresponding partial order graph \((S, \preceq)\) and for its covering graph \((S, \upa)\). It will come as no surprise that geometric distributions will play a fundamental role.
Suppose that \(S \subseteq \N\) is nonempty. The geometric distribution on \(S\) with parameter \(q \in (0, 1)\) has probability density function \(f\) given by \(f(x) = q^x / c_S\) for \(x \in S\) where \(c_S = \sum_{x \in S} q^x\) is the normalizing constant.
Note that \(0 \lt c_S \lt 1 / (1 - q) \lt \infty\).
The ordinary geometric distribution on \(\N\) with success parameter \(p \in (0, 1)\) (governing the number of Bernoulli trials before the first success) has a geometric distribution in the sense of with parameter \(q = 1 - p\) and normalizing constant \(1 / p\). Similarly, the ordinary geoemtric distribution on \(\N_+\) with success parameter \(p \in (0, 1)\) (governing the trial number of the first success) has a geometric distribution in the sense of with parameter \(q = 1 - p\) and normalizing constant \((1 - p) / p\). Moreover, geometric distributions are preserved under conditioning.
Suppose that \((T \subseteq S \subseteq \N)\) (nonempty). If \(X\) has the geometric distribution on \(S\) with parameter \(q \in (0, 1)\) then the conditional distribution of \(X\) given \(X \in T\) has the geoemtric distribution on \(T\) with parameter \(q\).
This is a very simple result. The PDF \(f\) of \(X\) is \(f(x) = q^x / c_S\) for \(x \in S\). The conditional PDF \(g\) of of \(X\) given \(X \in T\) is \(g(x) = f(x) / \P(X \in T)\) for \(x \in T\). But \(\P(X \in T) = \sum_{x \in T} q^x / c_S = c_T / c_S\).
Suppose that \((S, +)\) is a positive sub-semigroup of \((\N, +)\). Then \(X\) has an exponential distribution on \((S, +)\) if and only if \(X\) has a geometric distribution on \(S\) with parameter \(q \in (0, 1)\). In this case,
Suppose that \(q \in (0, 1)\) and that \(F(x) = q^x\) for \(x \in S\). Then trivially \(F\) is multiplicative: \(F(x + y) = F(x) F(y)\) for \(x, \, y \in S\). Also, \(\sum_{x \in S} F(x) = c_S \lt \infty\). So \(F\) is the reliability function of an exponential distribution on \((S, +)\) by a result in Section 2.3. The rate constant \(\alpha\) is given by \(1 / c_S\). Conversely, suppose that \(F\) is the reliability function for an exponential distribution on \((S, +)\). Let \(i = \min(S_+)\). If \(x \in S\) then \(i x = x i \in S\) so by the memoryless property, \([F(x)]^i = [F(i)]^x\) so \(F(x) = [F(i)]^{x / i}\). That is, \(F\) has the form given in the theorem with \(q = [F(i)]^{1 / i}\).
The geometric distribution also has constant rate for the covering graph \((S, \upa)\).
Suppose that \((S, +)\) is a positive sub-semigroup of \((\N, +)\) with \(I\) as the set of irreducible elements. Then \(X\) has constant rate for \((S, \upa)\) if and only if \(X\) has a geometric distribution on \(S\) with parameter \(q \in (0, 1)\). The rate constant is \(1 / \sum_{i \in I} q^i\).
Suppose that \(X\) has has the geometric distribution with parameter \(q \in (0, 1)\). Then the reliability function \(G\) for \((S, \upa)\) is given by \[G(x) = \sum_{i \in I} f(x + i) = c_S q^x \sum_{i \in I} q^i = f(x) \sum_{i \in I} q^i, \quad x \in S\] Conversely, suppose that \(f\) is the density function of a distribution on \(S\) with constant rate \(\alpha\) for \((S, \upa)\). Let \(G\) denote the reliability function. Then \[G(x) = \sum_{i \in I} f(x + i) = \alpha \sum_{i \in I} G(x + i), \quad x \in S\] The characterstic equation for this linear recurrence relation is \[\alpha \sum_{i \in I} r^{x + i} - r^x = 0, \quad x \in S\] or equivalently \(\varphi(r) = 0\) where \(\varphi(r) = \alpha \sum_{i \in I} r^i - 1\) for \(r \in (0, 1)\). Note that \(\varphi(0) = -1\), \(\varphi(1) = \alpha \#(I) - 1\), and \(\varphi^\prime(r) = \alpha \sum_{i \in I} i r^{i - 1}\) for \(r \in (0, 1)\). So if \(\alpha \gt 1 / \#(I)\), then there exists a unique distribution with constant rate \(\alpha\), with reliability function of the form \(G(x) = r^x\) for \(x \in S\). Of course, \(r \in (0, 1)\) depends on \(\alpha\).
The sub-semigroup generated by \(t \in \N_+\) is \((\N t, +)\) where \(\N t = \{n t: n \in \N\}\).
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
Of course, all of the distributions in are geometric distributions: \(X\) and \(\N_t\) have geometric distributions on \(\N\) while \(Z_t\) has a geometric distribution on the quotient set \(\{0, 1, \ldots, t\}\). 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)\). For \(t \in \N_+\), the independence of \(Z_t\) and \(\{N_t = 0\}\) is equivalent to \[ f(k) = [1 - F(t)] \sum_{n = 0}^\infty f(n t + k), \quad k \in \{0, 1, \ldots, t - 1\} \]
Let \(t \in \N_+\) and \(k \in \{0, 1, \ldots, t - 1\}\). Then \[f(k) = \P(X = k) = \P(N_t = 0, Z_t = k)\] But \(Z_t\) and \(\{N_t = 0\}\) are independent if an only if for all \(k \in \{0, 1, \ldots, t - 1\}\), \[\P(N_t = 0, Z_t = k) = \P(N_t = 0) \P(Z_t = k) = \P(X \in \{0, 1, \ldots, t - 1\}) \P(X = n t + k, \text{ for some } n \in \N_+)\] The right hand side is \([1 - F(t)] \sum_{n = 0}^\infty f(n t + k)\).
However, as in the continuous case, if \(X\) has an exponential distribution on \((\N, +)\) then the equation in holds more generally.
Suppose that \(X\) has a geometric distribution on \(\N\). Then the equation in holds for all \(t \in \N_+\) and \(k \in \N\).
Suppose that \(X\) has the geometric distribution on \(\N\) with parameter \(q \in (0, 1)\) so that \(f(x) = (1 - q) q^x\) and \(F(x) = q^x\) for \(x \in \N\). Then for \(t \in \N_+\) and \(k \in \N\), \[[1 - F(t)] \sum_{n = 0}^\infty f(n t + k) = (1 - q^t) \sum_{n = 0}^\infty (1 - q) q^{n t + k} = (1 - q^t)(1 - q) q^k \sum_{n = 0}^\infty (q^t)^n = (1 - q) q^k = f(k)\]
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(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\).
This leads to an interesting question:
If \(X\) has support \(\N\) and if \(Z_t\) and \(\{N_t = 0\}\) are independent for each \(t \in \N_+\), (equivalently, the equation in holds for \(t \in \N_+\) and \(k \in \{0, 1, \ldots, t - 1\}\)), does \(X\) have a geometric distribution?
Fix \(a \in \N_+\) and let \(S = \{0, a, a + 1, a + 2, \ldots\}\). Then \((S, +)\) is a numerical semigroup.
The numerical semigroup in is a discrete version of the continuous shifted semigroup studied in Section 3.2. Suppose now that \(X\) is a random variable in \(S\). The reliability function \(F\) of \(X\) for \((S, \preceq)\) is given by \(F(x) = \P(X = x) + \P(X \ge x + a)\) for \(x \in S\).
Suppose that \(X\) has the geometric distribution on \(S\) with parameter \(q \in (0, 1)\) as defined in . Then \(X\) has has probability density function \(f\) given by \[f(x) = \frac{1 - q}{1 - q + q^a} q^x, \quad x \in S\]
Fix an odd integer \(b \ge 3\) and let \((S, +)\) be the numerical semigroup with minimal generating set \(\{2, b\}\). Then
In the context of , suppose that \(X\) has the geometric distribution on \(S\) with paraemter \(q \in (0, 1)\). Then \(X\) has has probability density function \(f\) given by \[f(x) = \frac{1 - q^2}{1 + q^b} q^x, \quad x \in S\]
When \(b = 3\), the semigroup in describes the possible scores in American football: 2 points for a safety and 3 points for a field goal. A touchdown (6 points) is the same as two field goals; a touchdown with an extra point (7 points) is the same as two safeties and a field goal. A touchdown with a two-point conversion (8 points) is the same as four safeties or two field goals and a safety. The base set is \(S = \{0, 2, 3, 4, 5, \ldots\}\), so only a score of 1 is impossible. Another football-related numerical semigroup is discussed next.
Let \((S, +)\) be the numerical semigroup with minimal generating set \(\{3, 7\}\). So \(S\) is the set of possible scores in American football with only field goals and touchdowns with extra points (the most common scores).
Note again that a touchdown with a missed extra point (6 points) is included, since this is equivalent to two field goals.
In the context of , suppose that \(X\) has the geometric distribution on \(S\) with paraemter \(q \in (0, 1)\). Then \(X\) has has probability density function \(f\) given by \(f(x) = q^x / c\) for \(x \in S\) where \[c = 1 + q^3 + q^6 + q^7 + q^9 + q^{10} + \frac{q^{12}}{1 - q}\]