1. Reliability
  2. 4. Standard Discrete Spaces
  3. 1
  4. 2
  5. 3
  6. 4
  7. 5

3. Sub-Semigroups

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 defined in [4]

Basics

Throughout this section we assume that (S,+) is a sub-semigroup of (N,+) with the properties that

  1. 0S
  2. xS for some xN+.
Details:

Of course, the meaning of sub-semigroup is closure under the semigroup operation, so if x,yS then x+yS.

The first condition means that (S,+) is a positive sub-semigroup of (N,+), and the second condition rules out the trivial case S={0}. Of course, the partial order associated with (S,+) is given by xy if and only if x+z=y for some zS. So xy implies xy for x,yS but not conversely, in general. That is, (S,+) is not necessarily algebriacally complete. The partial order graph (S,) is left finite and hence the associated σ-algebra is P(S), the collection of all subsets of S. A standard way to construct a subsemigroup is by means of a generating set.

If AN, then the sub-semigroup generated by A is the interesection of all subsemigroups of (N,+) that contain A (and the identity element 0). Equivalently, the base set A of the sub-semigroup generated by A is A={x1+x2+xn:nN, and x1,x2,,xnA} 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.

If (S,+) is a sub-semigroup of (N,+) then the set I of irreducible elements of (S,+) is the unique minimal generating set of (S,+).

Details:

The semigroup (S,+) is left finite, so by a result in Section 2.2, if xS then x=i1+i2++in for some nN and i1,i2,,inI. That is, I=S. Clearly I is also miniimal. Suppose that J is a proper subset of I and that iIJ. But then iJ since i is irreducible in (S,+). Conversely, if A is a generating set for (S,+) then clearly IA.

A numerical semigroup is a sub-semigroup of (N,+) that contains all but finitely many elements of N.

(S,+) is a numerical semigroup if NS is finite.

  1. NS is the set of gaps.
  2. #(NS) is the genus of the semigroup.
  3. max(NS) is the Frobenius number of the semigroup.
Details:

In part (c), the maximum is with respect to the ordinary order , of course.

So if mN is the Frobenius number of (S,+) then {m+1,m+2,}S. Sets that generate numerical semigroups have some special properties.

A semigroup (S,+) generated by a set AN is a numerical semigroup if and only if gcd(A)=1.

Suppose that n=gcd(A){2,3,}. The a is a multiple of n for every aA and hence x is a multiple of n for every xS=A. So the set of gaps NS is infinite.

Let I denote the set of irreducible elements of the numerical semiegoupr (S,+) (so that I is the minimal generaing set). Then

  1. I is finite
  2. #(I) is the embedding dimension of the semigroup.
  3. min(I) is the multiplicity of the semigroup.
Details:

In part (c), the minimum is with respect to the ordinary order .

Suppose again that (S,+) is a sub-semigroup of (N,+) and that I is the set of irreducible elements. As usual, we let (S,) denote the covering graph corresponding to the partial order graph (S,). Then for x,yS, xy if and only if y=x+i for some iI.

Probabillity

Once again, suppose that (S,+) is a sub-semigroup of (N,+), as defined in [1]. Since the corresponding partial order graph (S,) is a lattice, the graph is stochastic. That is, the reliability function F of a probability measure P on 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,) and for its covering graph (S,).

F:S(0,1] is the reliability function of an exponential distribution on (S,+) if and only if there exists q(0,1) such that F(x)=qx for xS. The rate constant is α=1/xSqx.

Details:

Suppose that q(0,1) and that F(x)=qx for xS. Then trivially F is multiplicative: F(x+y)=F(x)F(y) for x,yS. Also, xSF(x)n=0qn=11q< so F is the reliability function of an exponential distribution on (S,+) by a result in Section 2.3. The rate constant α is given by 1/α=xSqx. Conversely, suppose that F is the reliability function for an exponential distribution on (S,+).Let i=min(S+). If xS then ix=xiS 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 following result is essentially a restatment of [7].

Suppose that X has a geometric distribution on N. Then the conditional distribution of X given XS has an exponential distribution on (S,+). Moreover, every exponential distribution on (S,+) has this form.

Details:

Suppose that X has the geometric distribution on N with success parameter p(0,1). Then of course, X has an exponential distribution on the standard discrete semigroup (N,+), with reliability function F defined by F(x)=(1p)x for xN. By a standard result in Section 2.4, the conditional distribution of X given XS is exponential for the sub-semigroup (S,+) and the reliability function of this conditional distribution is simply F restricted to S. Conversely, an exponential distribution on (S,+) has a reliability function F of the form F(x)=qx for xS where q(0,1). The corresponding density function f is f(x)=αqx for xS where the rate constant α is simply the normalizing constant. Equivalently, if X has the geometric distribution on N with success parameter 1q then P(X=xXS)=P(X=x)/P(XS)=f(x) for xS.

Of course, the exponential distribution described in [7] has constant rate for the associated partial order graph (S,). The distribution also has constant rate for the covering graph (S,).

Suppose that random variable X in S has density function f given by f(x)=cqx for xS, with parameter q(0,1), and where c=1/xSqx is the normalizing constant. Then X has constant rate 1/iIqi for the covering graph (S,). Moreover, every constant rate distribution for (S,) has this form.

Details:

As before, let I denote the set of irreducible elements of (S,+), or equivalently, the minimial generating set. Suppose that X has density f given in the theorem. Then the reliability function G for (S,) is given by G(x)=iIf(x+i)=cqxiIqi=f(x)iIqi,xS Conversely, suppose that f is the density function of a distribution on S with constant rate α for (S,). Let G denote the reliability function. Then G(x)=iIf(x+i)=αiIG(x+i),xS The characterstic equation for this linear recurrence relation is αiIrx+irx=0,xS or equivalently φ(r)=0 where φ(r)=αiIri1 for r(0,1). Note that φ(0)=1, φ(1)=α#(I)1, and φ(r)=αiIiri1 for r(0,1). So if α>1/#(I), then there exists a unique distribution with constant rate α, with reliability function of the form G(x)=rx for xS. Of course, r(0,1) depends on α.

Examples

Fix aN+ and let S={0,a,a+1,a+2,}. The numerical semigroup (S,+) has (minimal) generating set A={a,a+1,2a1}. The genus and Frobenius number are a1, and the embedding dimension and multiplier are a. The exponential distribution on (S,+) with parameter q(0,1) as defined in [7] has probability density function f given by f(x)=1q1q+qaqx,xS so the rate constant is (1q)/(1q+qa). This distribution also has constant rate for the covering graph (S,), with rate constant. (1q)/(qaq2a).

Fix an odd integer b3 and let S={2,b}={0,2,4,,b3,b1,b,b+1,b+2,}. The numerical semigroup (S,+) has embedding number 2, multiplier 2, Frobenius number b2 and genus (b1)/2. The exponential distribution on (S,+) with parameter q(0,1) as defined in [7] has probability density function f given by f(x)=1q21+qbqx,xS so the rate constant is (1q2)/(1+qb). This distribution also has constant rate for the covering graph (S,), with rate constant. 1/(q2+qb).