Probability on Free Semigroups

Let $I$ be a countable alphabet of letters, and let $S$ denote the set of all finite length words using letters from $I$ . The empty word, with no letters, is denoted $e$ . Let $\cdot$ denote the concatenation operation on elements of $S$ . That is, suppose that $m, n \in N$ and that $x_{i}, y_{j} \in I$ for $i \in {1, 2, \dots, m}$ and $j \in {1, 2, \dots, n}$ . Then $x = x_{1} \dots x_{m} \in S$ and $y = y_{1} \dots y_{n} \in S$ , and $x y = x_{1} \dots x_{m} y_{1} \dots y_{n}$ The space $(S, \cdot)$ is a discrete, positive semigroup, known as the free semigroup generated by $I$ .

The set of words

S

is sometimes denoted

I^{*}

, and the elements of

I

are the irreducible elements of

(S, \cdot)

. The adjective free is used because there are no algebra rules imposed on

(S, \cdot)

. Here are two examples that we will use in exercises:

The binary semigroup is the free semigroup on the alphabet ${0, 1}$ , and so the simplest non-trivial free semigroup. The nonempty words are simply bit strings of finite length.

The genetic semigroup is the free semigroup on the alphabet ${A, C, G, T}$ . In genetics, the letters refer to the nucleotides that are the base building blocks of DNA: adenine, cytosine, guanine, and thymine, respectively. Nonempty words may represent genes.

For $x \in S$ and $i \in I$ , let $d_{i} (x)$ denote the number of times that letter $i$ occurs in $x$ , and let $d (x) = \sum_{i \in I} d_{i} (x)$ denote the length of $x$ .

Suppose again that $(S, \cdot)$ is the free semigroup corresponding to the countable alphabet $I$ .

Let $(S, ⪯)$ denote the partial order graph associated with $(S, \cdot)$ . Then $x ⪯ y$ if and only if $y = x t$ for some $t \in S$ , so that $x$ is a prefix of $y$ and then $x^{- 1} y$ is the corresponding suffix.
Let $(S, ↑)$ denote the cover graph of $(S, ⪯)$ . Then $x ↑ y$ if and only if $y = x i$ for some $i \in I$ . Hence $(S, ↑)$ is a regular tree rooted at $e$ of degree $# (I)$ .
For $n \in N$ , let $↑^{n}$ denote the composition power of $↑$ of order $n$ . Then $x ↑^{n} y$ if and only if $y = x t$ for some $t \in S$ with $d (t) = n$ .

Since

(S, ↑)

is a rooted tree, all of the results in Section 1 apply. In particular, if

# (I) = k \in N_{+}

, then

(S, ↑)

is a regular rooted tree of degree

k

. Specializing further, when

k = 2

and

I = {0, 1}

, so that we have the binary semigroup described in [2], then the corresponding cover graph

(S, ↑)

is the binary tree. Note also that

d (x)

is the distance from

e

x

in the cover graph

(S, ↑)

for

x \in S

, so our notation is consistent. More generally, if

x ⪯ y

then

d (x, y) = d (y) - d (x)

is the distance from

x

y

(S, ↑)

. Like all rooted trees,

(S, ⪯)

is a lower semi-lattice and for

x, y \in S

x \land y

is the largest common prefix of

x

and

y

. But

(S, ⪯)

is not an upper semi-lattice unless

I

consists of a single letter.

Let $N_{I} = {(n_{i} : i \in I) : n_{i} \in N for i \in I and n_{i} = 0 for all but finitely many i \in I}$ . We define the multinomial coefficients on $N_{I}$ by $C (n) = # {x \in S : d_{i} (x) = n_{i} for i \in I} = \frac{(\sum_{i \in I} n_{i})!}{\prod_{i \in I} n_{i}!}, n = (n_{i} : i \in I) \in N_{I}$

The free semigroup has the property that

[e, x]

is finite and totally ordered for each

x \in S

. Moreover, it is the only discrete positive semigroup with this property.

Suppose that $(S, \cdot)$ is a discrete positive semigroup with associated partial order $⪯$ and with the property that $[e, x]$ is finite and totally ordered for each $x \in S$ . Then $(S, \cdot)$ is isomorphic to a free semigroup on an alphabet.

Details:

Let $I$ denote the set of irreducible elements of $(S, \cdot)$ . If $x \in S - {e}$ then $i_{1} ⪯ x$ for some $i_{1} \in I$ and hence $x = i_{1} y$ for some $y \in S$ . If $y ≻ e$ then we can repeat the argument to write $y = i_{2} z$ for some $i_{2} \in I$ and $z \in S$ . Note that $x = i_{1} i_{2} z$ and hence $i_{1} i_{2} ⪯ x$ . Moreover, $i_{1}$ and $i_{1} i_{2}$ are distinct. Since $[e, x]$ is finite, the process must terminate. Thus, we can write $x$ in the form $x = i_{1} i_{2} \dots i_{n}$ for some $n \in N_{+}$ and some $i_{1}, i_{2}, \dots, i_{n} \in I$ . Finally, we show that the factorization is unique. Suppose that $x = i_{1} i_{2} \dots i_{n} = j_{1} j_{2} \dots j_{m}$ where $i_{1}, \dots, i_{n} \in I$ and $j_{1}, \dots, j_{m} \in I$ . Then $i_{1} ⪯ x$ and $j_{1} ⪯ x$ . Since the elements of $[e, x]$ are totally ordered, we must have $i_{1} = j_{1}$ . Using left cancellation we have $i_{2} \dots i_{n} = j_{2} \dots j_{m}$ . Continuing in this fashion it follows that $m = n$ and $i_{1} = j_{1}$ , $i_{2} = j_{2}, \dots, i_{n} = j_{n}$ .

Suppose that $(S, \cdot)$ is a discrete positive semigroup with the property that every $x \in S$ has a unique finite factoring over the set of irreducible elements $I$ . Then $(S, \cdot)$ is isomporphic to the free semigroup on $I$ .

Details:

Every $x \in S$ has a finite factoring over $I$ , so that $x = i_{1} i_{2} \dots i_{n}$ . If this factoring is unique, then clearly $(i_{1}, i_{2}, \dots i_{n}) \mapsto i_{1} i_{2} \dots i_{n}$ is an isomorphism from the free semigroup $(I^{*}, \cdot)$ onto $(S, \cdot)$ .

The left walk functions and the left generating functions for the graphs

(S, ⪯)

(S, ↑)

and

(S, ⇑)

are given in Section 1, as is the Möbius kernel for

(S, ⪯)

. Since we have a discrete positive semigroup, we can give the more basic Möbius function:

The Möbius function $μ$ of $(S, \cdot)$ is given by $μ (e) = 1$ , $μ (i) = - 1$ for $i \in I$ , and $μ (x) = 0$ for all other $x \in S$ .

$\dim (S, \cdot) = # (I)$ .

Details:

Note first that a homomorphism $ϕ$ from $(S, \cdot)$ into $(R, +)$ can uniquely be specified by defining $ϕ (i)$ for all $i \in I$ and then defining $ϕ (i_{1} i_{2} \dots i_{n}) = ϕ (i_{1}) + ϕ (i_{2}) + \dots ϕ (i_{n})$ Thus, if $ϕ$ is a such a homomorphism and $ϕ (i) = 0$ for all $i \in I$ , then $ϕ (x) = 0$ for all $x \in S$ . Now suppose that $B \subseteq S$ and $# (B) < # (I)$ . We will show that there exists a nonzero homomorphism from $(S, \cdot)$ into $(R, +)$ with $ϕ (x) = 0$ for all $x \in B$ . Let $I_{B}$ denote the set of letters contained in the words in $B$ . Suppose first that $I_{B}$ if a proper subset of $I$ (and note that this must be the case if $I$ is infinite). Define a homomorphism $ϕ$ by $ϕ (i) = 0$ for $i \in I_{B}$ and $ϕ (i) = 1$ for $i \in I - I_{B}$ . Then $ϕ (x) = 0$ for $x \in B$ , but $ϕ$ is not the zero homomorphism. Suppose next that $I_{B} = I$ . Thus $I$ is finite, so let $k = # (B)$ and $n = # (I)$ , with $k < n$ . Denote the words in $B$ by $i_{j 1} i_{j 2} \dots i_{j m_{j}}, j = 1, 2, \dots, k$ The set of linear, homogeneous equations $ϕ (i_{j 1}) + ϕ (i_{j 2}) + \dots + ϕ (i_{j m_{j}}) = 0, j = 1, 2, \dots, k$ has $n$ unkowns, namely $ϕ (i)$ for $i \in I$ , but only $k$ equations. Hence there exists a non-trivial solution. The homomorphism so constructed satisfies $ϕ (x) = 0$ for $x \in B$ .

We can use the strict positive semigroup to provide a simple example of a discrete semigroup in which multiples of counting measure

#

are not the only left invariant measures.

Suppose that $I$ has at least two elements and consider the strict positive semigroup $(S_{+}, \cdot)$ associated with the free semigroup $(S, \cdot)$ . That is, $S_{+} = S - {e}$ while $\cdot$ is still concatenation. Define the function $g : S_{+} \to (0, \infty)$ by $g (x) = c_{i}$ if the terminal letter of $x$ is $i \in I$ , where $c_{i} \in (0, \infty)$ for each $i \in I$ and $c_{i} \neq c_{j}$ for some $i, j \in I$ . Let $λ$ be the positive measure on $S_{+}$ with density $g$ (relative to $#$ ). That is, $λ (A) = \sum_{x \in A} g (x) = \sum_{i \in I} c_{i} n_{i} (A), A \subseteq S_{+}$ where $n_{i} (A)$ is the number of words in $A$ with terminal letter $i$ for each $i \in I$ . Then $λ$ is left invariant: If $x \in S$ and $A \subseteq S$ then the words in $x A$ have the same terminal letters as the corresponding words in $A$ , so $λ (x A) = λ (A)$ . But $λ$ is clearly not a multiple of counting measure.