How to prove this combinatorial statement with a probabilistic argument?

Question

Let $[0,d) = \{0, 1, \ldots, d-1\}$ be considered an alphabet of $d$ symbols. The set of all finite sequences over $[0,d)$ of length $n$ is denoted $[0,d)^n$, and the set of all finite sequences over $[0,d)$ of any length is denoted $[0,d)^* = \bigcup_n [0,d)^n$.

For each $i \in [0,d)$ and $x \in [0,d)^*$, let $c_i(x)$ count the number of appearances of the symbol $i$ in the sequence $x$. I understand that, when $n$ is large, most $x \in [0,d)^n$ will satisfy $c_i(x)/n \approx 1/d$ for each $i$. More formally: for each $\delta > 0$, the proportion of $x \in [0,d)^n$ which satisfy

$$\Big|\frac{c_i(x)}{n} - \frac{1}{d} \Big|< \delta \quad \forall i \in [0,d)$$

approaches $1$ as $n$ approaches infinity (say $x$ is "$\delta$-close to the average" if the above condition holds). This can be proven by reinterpreting this situation through a probabilistic lense and using the (weak) law of large numbers.

I understand it can also be proven by explicitly bounding the involved sums of multi-nomial coefficients, but I am hoping to more thoroughly understand the probabilistic approach, because I want to prove something more general.

Let $|x|$ denote the length of $x$ in symbols. Define a partial order $\leq$ on $[0,d)^*$ as $y \leq x$ iff $|y| \leq |x|$ and $y$ and $x$ agree as sequences in the first $|y|$ places. The sequence $y$ is said to be an initial segment of $x$ in this case.

Claim: for each $\delta > 0$, the proportion of $x \in [0,d)^n$ which satisfy "every $y \leq x$ with $|y| > \log |x|$ is $\delta$-close to the average" approaches $1$ as $n$ approaches infinity.

I believe this is true, because if the initial segment is made long enough then it will be close to the average with high probability, and then the remaining symbols are (often) close to the average as well. There is a strong deviation from the average only in exceptional cases. But I do not know how to robustly prove this, or the earlier statement, using a probabilistic argument.

Can anyone present such an argument, or point me to references where I can learn more in this direction? I especially want to learn how to prove statements like this, involving averages of symbol counts in sequences, on my own.

Answer 1

The first statement you made,

"for each $\delta > 0$, the proportion of $x \in [0,d)^n$ which satisfy $$\Big|\frac{c_i(x)}{n} - \frac{1}{d} \Big|< \delta \quad \forall i \in [0,d)$$ approaches $1$ as $n$ approaches infinity"

is a special case of the weak law of large numbers https://en.wikipedia.org/wiki/Law_of_large_numbers#Weak_law

Let $\psi(n)$ be any integer sequence tending to infinity. The claim

for each $\delta > 0$, the proportion of $x \in [0,d)^n$ which satisfy "every $y \leq x$ with $|y| > \psi(|x|)$ is $\delta$-close to the average" approaches $1$ as $n$ approaches infinity

is an immediate consequence of the strong law of large numbers, once you interpret what "almost sure convergence" means. The case described in the original question is $\psi(n)=\lfloor \log n \rfloor$.

Some details: Consider the probability space of infinite sequences from $\{0, 1, \ldots, d-1\}$, endowed with the product $\sigma$-algebra and product measure, that makes the coordinates uniform and independent. Let $A_k$ be the event that the prefix $(x_1,\ldots, x_k)$ is $\delta$-close to the average, as you defined this notion. The weak law asserts that $P(A_k) \to 1$ as $k \to \infty$. The strong law implies that $$B_\ell= \cap_{k \ge \ell} A_k$$ satisfy $P[\cup_{\ell \ge 1} B_\ell]=1$. Since the sets $B_\ell$ are increasing in $\ell$, it follows that $P[B_{\psi(n)}] \to 1$ as $n \to \infty$.