How to show that a set of random strings has unit probability I am encountering a problem where I want to show that the generation of a random string terminates in finite time with probability one, where the termination is condition is reaching an element of a given set (see more in "Background" below). I am trying to formalize my problem here. I can imagine this kind of problem has been studied in the literature, but I can't find what I'm looking for.
Consider a finite set $S = \{s_1, \ldots, s_k\}$ of symbols. Let's define a string over $S$ to be a finite sequence in $S$, and denote the set of all strings over $S$ by $F(S)$. With every symbol $s_i \in S$, let there be associated a probability $p_{s_i} \in [0,1]$ of $s_i$, such that $\sum_{i=1}^k p_{s_i} = 1$. For every string $x = (x_i)_{i=1}^n \in F(S)$, we call $p_x = \prod_{i=1}^n p_{x_i}$ the probability of the string $x$. 
Consider a subset $T \subseteq F(S)$ with the following properties:


*

*No string in $T$ has a proper continuation in $T$. More precisely, for every pair of 
strings 
$x=(x_i)_{i=1}^n$, $y=(y_i)_{i=1}^m \in F(S)$ with $n < m$ and $x_i = y_i$ for $i = 1, 
    \ldots, n$, it holds that $x \in F(S) \implies y \notin F(S)$.

*Every string in $F(S)$ is continued by a string in $T$ or continues a string in $T$. 
More precisely, for every string $x=(x_i)_{i=1}^n \in F(S)$, there is a string 
$y=(y_i)_{i=1}^m$ with $n \leq m$ and $x_i = y_i$ for $i = 1, \ldots, n$ or there is a 
string $z=(z_i)_{i=1}^l$ with $l \leq n$ and $x_i = z_i$ for $i=1, \ldots, l$.


Question: How can I show that $T$ has unit probability, i.e. that it holds that $\sum_{x \in T} p_x = 1$?
Remark: Note that the length of the strings in $T$ can be unbounded (that's true for the cases I'm actually interested in). For example, for $S = \{a,b\}$, one might define $T$ to be the set of all strings where $a$ occurs five times and where $a$ is the last entry.
Background: The idea is that a string is randomly generated by repeatedly picking a symbol from $S$ with the prescribed probabilities until a termination condition is met, namely until the string is one of the strings in $T$. In the example made in the remark, the termination condition is that $a$ has been picked five times. I tried to work out conditions for when the definition of a termination condition is sound, meaning that (a) every string in $T$ can be reached and that (b) the generation stops after finitely many steps with probability one. Condition 1 is supposed to guarantee (a), and I hope that (b) is implied by condition 2. I don't want to directly put (b) as an assumption, because in the cases I'm interested in, it can be hard to directly calculate the probability of $T$. Thus, I would like to have an easy-to-see criterion that guarantees that $T$ has unit probability. 
Note that in the example made in the remark, if $p_a = p_b = 1/2$, then always generating $b$ would never result in meeting the termination condition, but the sequence $(b,b,b,\ldots)$ has probability zero.
 A: You are studying a class of (possibly infinite) prefix codes; you should also investigate Huffman codes (most references talk about binary codes but everything extends to your case with $|S|$ symbols).  The term "prefix" comes from your condition (1), which says that no element of $T$ is a prefix of another.  Associated to $T$ is a binary tree, in which edges are labeled with elements of $S$, and edges coming out of a node have distinct labels.  The codewords in $T$ correspond to paths from the root to a leaf in $T$.  Your condition (2) says that the tree is full (every node is either a leaf or has all $|S|$ descendants).
It's easy to show by induction that the total mass is $1$ for finite trees. The probability of reaching a given node (whether or not it's a leaf) is the product of the edge probabilities on the path from the root.  You show, by working backwards from the leaves, that the total probability from any given node forward is $1$; hence this holds for the root node as well.
For your infinite tree, approximate it by the subtrees of depth $n$ as $n\to\infty$.  The (measures on $T$ defined by the) finite trees converge to your tree in measure, so the total measure of your infinite $T$ is $1$ as well.
