Our starting point again is a measurable space \((S, \ms S)\) with the assumptions and notation in Section 1. In particular, \((S, \cdot)\) is a measurable semigroup tht satisfies the left cancellation property. Recall also that the graph \((S, \rta)\) associated with \((S, \cdot)\) is defined by \(x \rta y\) if and only if \(y \in x S\) for \(x, \, y \in S\) so that \(y = x t\) for some \(t \in S\). In the case of a positive semigroup, the relation \(\preceq\) is a partial order.
A \(\sigma\)-finite measure \(\lambda\) on \((S, \ms S)\) is supported by \((S, \cdot)\) if \(\lambda\) is supported by the associated graph \((S, \rta)\), so that \[\lambda(x S) \gt 0, \quad x \in S\]
We usually assume that measures, and probability distributions in particular, are supported by the semigroup, so that the measures and the semigroup (and its graph) are connected in a fundamental way. In particular, recall that \(x S\) is the set of (right) neighbors of \(x \in S\) and that the \(\sigma\)-algebra associated with the semigroup (or its graph) is \(\ms S_0 = \sigma\{x S: x \in S\}\). Left invariance of a measure on \((S, \ms S)\) with respect to the semigroup \((S, \cdot)\) is the abstract version of translation invariance for Lebesgue measure and counting measure, and is very important for our study of probability on semigroups.
Suppose that \((S, \cdot)\) is a semigroup. A \(\sigma\)-finite measure \(\lambda\) is left invariant for \((S, \cdot)\) if \(\lambda(x A) = \lambda(A)\) for every \(x \in S\) and \(A \in \ms S\).
We always assume that \(\lambda(S) \gt 0\), so trivially a measure that is left invariant for \((S, \cdot)\) is supported by the semigroup. Naturally there is a parallel definition for a right invariant measure which leads in turn to the definition for an invariant measrue that is both left and right invariant. Invariant measures (left, right, or both) are also known as Haar measures in honor of Alfred Haar, who first studied them. Left invariance is the property that is important for our study of abstract reliability.
Suppose that \(\lambda\) is left invariant for \((S, \cdot)\). Then for \(x \in S\) and \(A \in \ms S\), \[\lambda(x^{-1} A) = \lambda(A \cap x S)\]
Recall that \(x(x^{-1} A) = A \cap x S\) for \(x \in S\) and \(A \in \ms S\). Hence \[\lambda[x(x^{-1} A)] = \lambda(x^{-1} A) = \lambda(A \cap x S)\]
In partiular, \(\lambda(x^{-1} A) = \lambda(A)\) if \(x \in S\) and \(A \in \ms S\) with \(A \subseteq x S\). The left cancellation property would seem to be a necessary condition for left invariance to make sense, since \(t \mapsto x t\) is an isomorphism from the graph \((S, \rta)\) to the graph \((xS, \rta)\) for each \(x \in S\). We are particularly interested in the case where a left-invariant measure exists and is unique up to multiplication by positive constants, either on the associated \(\sigma\)-algebra \(\ms S_0\) or the reference \(\sigma\)-algebra \(\ms S\). The next example and proposition give a case where uniqueness fails in the extreme, and an important case where uniqueness holds.
Suppose that \((S, \cdot)\) is the right zero semigroup on \(S\), so that \(x y = y\) for \(x, \, y \in S\). Then \(x A = A\) for \(x \in S\) and \(A \in \ms S\), so trivially every measure \(\lambda\) on \((S, \ms S)\) is left invariant.
Suppose that \((S, \cdot)\) is a discrete positive semigroup. Then \(\#\) is the unique left-invariant measure, up to multiplication by positive constants.
Recall that the term discrete means that \(S\) is countable and \(\ms S\) is the power set of \(S\). If \(x \in S\) and \(A \subseteq S\) then \(A\) and \(x A\) have the same cardinality so \(\#(x A) = \#(A)\). Hence \(\#\) is left invariant. On the other hand, \((S, \cdot)\) has an identity element \(e\), so if \(\lambda\) is a left-invariant measure then \(\lambda(\{x\}) = \lambda(x \{e\}) = \lambda(\{e\})\) for \(x \in S\). Hence \(\lambda = \lambda(\{e\}) \#\).
Here is the classical existence and uniqueness theorem in the special case of a topological group:
Suppose that \((S, \ms U)\) is a locally compact topological space. If \((S, \cdot)\) is a topological group then there exists a regular left-invariant Borel measure \(\lambda\) that is unique up to multiplication by positive constants.
Recall that \(S\) is given the Borel \(\sigma\)-algebra \(\ms S = \sigma(\ms U)\). The term topological group means that the function \((x, y) \mapsto x^{-1} y\) from \(S^2\) (with the product topology) into \(S\) is continuous. The term Borel measure means that \(\lambda(A) \gt 0\) if \(A \subseteq S\) is open, and the term regular means that for \(A \in \ms S\) \begin{align*} \lambda(A) &= \sup\{\lambda(C): C \subseteq A, \, C \text{ compact}\} \\ \lambda(A) &= \inf\{\lambda(U): A \subseteq U, \, U \text{ open}\} \end{align*} The proof of the theorem can be found in the book by Halmos.
However, a full group is usually not the proper object of study in the abstract reliability setting. Rather, we are usually interested in a sub-semigroup of positive elements
.
Suppose again that \((S, \ms U)\) is a locally compact topological space and that \((S, \cdot)\) is a topological group. If \((T, \cdot)\) is a (measurable) positive sub-semigroup of \((S, \cdot)\) and \(T\) has nonempty interior, then the regular left-invariant measure \(\lambda\) for \((S, \cdot)\) is also left invariant for \((T, \cdot)\).
The assumptions mean that the identity \(e \in T\) and that if \(x, \, y \in T_+\) then \(x y \in T_+\), where as usual, \(T_+ = T - \{e\}\). The fact that \(T\) has nonempty interior ensures that \(\lambda(T) \gt 0\). The left-invariance property trivially holds for \(x \in T\) and \(A \in \ms S\) with \(A \subseteq T\) since it holds more generally for \(x \in S\) and \(A \in \ms S\).
Fix \(x \in S\) and let \(\varphi_x(y) = x y\) for \(y \in S\). Recall that \(\varphi_x\) maps \(S\) one-to-one onto \(x S\) and has inverse function given by \(\varphi_x^{-1}(y) = x^{-1} y\) for \(y \in x S\). Both are measurable. By definition, if the measure \(\lambda\) is left invariant for \((S, \cdot)\) then the functions \(\varphi_x\) and \(\varphi_x^{-1}\) preserve measure: \begin{align*} \lambda[\varphi_x(A)] &= \lambda(x A) = \lambda(A), \quad A \in \ms S \\ \lambda[\varphi_x^{-1}(A)] &= \lambda(x^{-1}A) = \lambda(A), \quad A \in \ms S, \, A \subseteq x S \end{align*} The standard change of variables theorem then gives integral versions of left invariance.
Suppose that \(\lambda\) is left invariant for \((S, \cdot)\) and that \(f: S \to \R\) is measurable. Then for \(x \in S\) (and assuming that the integrals exist), \begin{align*} \int_S f(x y) \, d\lambda(y) &= \int_{x S} f(u) \, d\lambda(u) \\ \int_{x S} f(x^{-1} y) \, d\lambda(y) &= \int_S f(u) \, d\lambda(u) \end{align*}
The fundamental mapping in Section 1 gives a two-dimensional version. As before, let \(\varphi(x, y) = (x, x y)\) for \((x, y) \in S^2\), so that \(\varphi\) maps \(S^2\) one-to-one onto \[\{(x, y) \in S^2: x \rta y\} = \{(x, y): x \in S, y \in x S\}\] and has inverse function \(\varphi^{-1}\) given by \(\varphi^{-1}(x, y) = x^{-1} y\) for \(x \rta y\). Both are measurable, and it is worth noting again that the co-domain is the realtion \(\rta\) as a set of ordered pairs. If \(\lambda\) is left invariant then \(\varphi\) preserves measure:
Suppose that \(\lambda\) is left invariant for \((S, \cdot)\). Then \[\lambda^2[\varphi(C)] = \lambda^2(C), \quad C \in \ms S^2\]
For \(C \in \ms S^2\), let \(C_x = \{y \in S: (x, y) \in C\}\) denote the cross section of \(C\) at \(x \in S\). Then \([\varphi(C)]_x = x (C_x)\). Hence by Fubini's theorem and left invariance \[\lambda^2[\varphi(C)] = \int_S \lambda\left([\varphi(C)]_x\right) \, d\lambda(x) = \int_S \lambda[x (C_x)] \, d\lambda(x) = \int_S \lambda(C_x) \, d\lambda(x) = \lambda^2(C)\]
As before, the standard change of variables theorem for integrals gives us the following:
Suppose that \(\lambda\) is left invariant for \((S, \cdot)\) and that \(f: S^2 \to \R\) is measurable. Then (assuming that the integrals exist), \[\int_{S^2} f(x, xy) \, d\lambda^2(x, y) = \int_{u \to v} f(u, v) \ d\lambda^2(u, v)\]
The concept of convolution of functions makes sense in a semigroup with a left invariant reference measure. So for the remainder of this section, suppose that the \(\sigma\)-finite measure \(\lambda\) is left invariant for the semigroup \((S, \cdot)\), and let \(\rta\) denote the relation associated with \((S, \cdot)\). We are only going to need convolution for nonnegative functions.
For measurble \(f, \, g: S \to [0, \infty)\), the convolution of \(f\) with \(g\) is the function \(f * g\) defined by \[(f * g)(y) = \int_{x \rta y} f(x) g(x^{-1} y) \, d\lambda(x), \quad y \in S\]
Note that the definition makes sense. Recall that \(x \rta y\) if and only if \(y \in x S\), so \(x^{-1} y\) is defined. Moreover, the function \(x \mapsto g(x^{-1} y)\) from \(\{x \in S: y \in x S\}\) to \([0, \infty)\) is measurable. Like the semigroup itself, convolution is associative, but not commutative in general.
For measurable \(f, \, g, \, h: S \to [0, \infty) \), \[[(f * g) * h](z) = [f * (g * h)](z) = \int_{x \rta y \rta z} f(x) g(x^{-1} y) h(y^{-1} z) \, d\lambda^2(x, y), \quad z \in S\]
First, \begin{align*} [(f * g) * h](z) &= \int_{y \rta z} (f * g)(y) h(y^{-1} z) d \lambda(y) = \int_{y \rta z} \left[\int_{x \rta y} f(x) g(x^{-1} y) \, d\lambda(x)\right] h(y^{-1} z) \, d\lambda(y) \\ &= \int_{y \rta z} \int_{x \rta y} f(x) g(x^{-1} y) h(y^{-1} z) \, d\lambda(x) \, d\lambda(y), \quad z \in S \end{align*} On the other hand, for \(z \in S\), \[[f * (g * h)](z) = \int_{x \rta z} f(x) (g * h)(x^{-1} z) \, d\lambda(x) = \int_{x \rta z} f(x) \int_{y \rta x^{-1} z} g(y) h[y^{-1}(x^{-1} z)] \, d\lambda(y) \, d\lambda(x)\] But if \(x \rta z\) and \(y \rta x^{-1} z\) then \(y^{-1} (x^{-1} z) = (x y)^{-1} z\). Our basic measure preserving mapping \(u = x\), \(v = xy\) transforms the domain \(\{(x, y) \in S^2: x \rta z, y \rta x^{-1} z\}\) one-to-one onto the domain \(\{(u, v) \in S^2: u \rta v, v \rta z\}\). Hence from , \[[f * (g * h)](z) = \int_{v \rta z} \int_{u \rta v} f(u) g(u^{-1} v) h(v^{-1} z) \, d\lambda(u) \, d\lambda(v)\]
Convolution can also be defined for finite measures without reference to an underlying left-invariant measure. Probability measures, of course, are the most important special case.
Suppose that \(\mu\) and \(\nu\) are finite measures on \((S, \ms{S})\). The convolution of \(\mu\) with \(\nu\) is the finite measure defined by \[(\mu * \nu)(A) = \int_{S^2} \bs 1_A(x y) \, d(\mu \times \nu)(x, y) \]
There are several variations.
Suppose again that \(\mu\) and \(\nu\) are finite measures on \((S, \ms{S})\). Then \[ (\mu * \nu)(A) = \int_S \int_S \bs 1_A(x y) \, d\mu(x) \, d\nu(y) = \int_S \int_S \bs 1_A(x y) \, d\nu(y) \, d\mu(x) = \int_S \nu(x^{-1} A) \, d\mu(x), \quad A \in \ms{S} \]
The first and second representations follows from the definition by Fubini's theorem. The third representation follows from the second since \(x y \in A\) if and only if \(y \in x^{-1} A\).
Once again, convolution is associative.
Suppose that \(\mu\), \(\nu\), and \(\rho\) are finite measures on \((S, \ms{S})\). Then \( (\mu * \nu) * \rho = \mu * (\nu * \rho) \) so we can write \(\mu * \nu * \rho\) without ambiguity.
The common value is \[ \int_{S^3} \bs{1}_A (x y z) \, d(\mu \times \nu \times \rho)(x, y, z) = \int_S \int_S \int_S \bs{1}_A(x y z) \, d\mu(x) \, d\nu(y) \, d\rho(z), \quad A \in \ms S \]
Given definition , the following result is not surprising.
Suppose that \(\mu\) and \(\nu\) are finite measures and that \(f: S \to [0, \infty)\) is measurable. Then \[\int_S f(z) \, d(\mu * \nu)(z) = \int_{S^2} f(x y)\, d(\mu \times \nu)(x, y) = \int_S \int_S f(x y) \, d\mu(x) \, d\nu(y) \]
This result holds more generally for measurable \(f: S \to \R\), assuming that the integrals exist.
For our last result, suppose that \((S, \cdot)\) is a positive semigroup with identity \(e\), so that the associated relation is a partial order \(\preceq\). We assume again that we have a fixed, left-invariant measure \(\lambda\), and as usual, we let \(L\) denote the adjacency kernel and \(\gamma_n\) the path function of order \(n \in \N\) (with respect to \(\lambda\) of course).
For \(n \in \N_+\), \[L^n(x, y) = L^n(e, x^{-1} y) = \gamma_{n - 1}(x^{-1}y), \quad x \preceq y\]
Suppose that \(x \preceq y\) and \(n \in \N_+\). The simple combinatorial argument
is that
\[x \preceq x_1 \preceq x_2 \preceq \cdots \preceq x_{n-1} \preceq y\]
is a path of length \(n\) from \(x\) to \(y\) if and only if
\[e \preceq x^{-1} x_1 \preceq x^{-1} x_2 \preceq \cdots \preceq x^{-1} x_{n-1} \preceq x^{-1} y\]
is a path of length \(n\) from \(e\) to \(x^{-1} y\), if and only if
\[x^{-1} x_1 \preceq x^{-1} x_2 \preceq \cdots \preceq x^{-1} x_{n-1} \preceq x^{-1} y\]
is a path of length \(n - 1\) terminating in \(x^{-1} y\). As will be shown in Section 7, the product measure \(\lambda^{n-1}\) is left invariant for the product semigroup \((S^{n - 1}, \cdot)\). Hence the three sets of walks have the same measure.
Consider the standard continuous semigroup \(([0, \infty), +)\). For \(n \in \N_+\), \[L^n(x, y) = L^n(0, y - x) = \gamma_{n-1}(y - x) = \frac{(y - x)^{n-1}}{(n - 1)!}, \quad x \le y\]
Consider the standard discrete semigroup \((\N, +)\). For \(n \in \N\), \[L^n(x, y) = L^n(0, y - x) = \gamma_{n-1}(y - x) = \binom{y - x + n - 1}{n - 1}, \quad x \le y\]