Finite discrete sources and product blocks

A finite discrete source is an integer $m\ge 1$ and a probability vector $p=(p_1,\dots ,p_m)$ on the alphabet $\mathcal{X}=[m]=\{1,\dots ,m\}$ such that $p_i>0$ for every $i$. Here a probability vector has nonnegative entries summing to one, as in Finite distributions, entropy, divergence, and stochastic matrices; the strict positivity convention means that $\mathcal{X}$ is the source support. In particular, the one-symbol source has $m=1$ and $p_1=1$.

For $n\ge 1$, a block of length $n$ is a word $x^n=(x_1,\dots ,x_n)\in {\mathcal{X}}^n$. Its product probability is $p^n(x^n):={\prod }_{t=1}^n{p}_{x_t}\mathrm{.}$ Finite distributivity gives ${\sum }_{x^n\in {\mathcal{X}}^n}{p}^n(x^n)=({\sum }_{i=1}^m{p}_i{)}^n=1$, so $p^n$ is again a probability vector and has full support. When coding blocks, use lexicographic order on ${\mathcal{X}}^n$; listing its $m^n$ words in that order identifies the block alphabet with $[m^n]$ for the code conventions below. Blocks are the only memoryless-source objects used on this page.