Entrance and escape dynamics for the typical set

According to the asymptotic equipartition property, sufficiently long sequences of random variables converge to a set that is typical. While the size and probability of this set are central to information theory and statistical mechanics, they can often only be estimated accurately in the asymptotic limit due to the exponential growth in possible sequences. Here we derive a time-inhomogeneous dynamics that constructs the properties of the typical set for all finite length sequences of independent and identically distributed random variables. These dynamics link the finite properties of the typical set to asymptotic results and allow the typical set to be applied to small and transient systems. The main result is a geometric mapping—the triangle map—relating sequences of random variables of length $n$ to those of length $n+1$. We show that the number of points in this map needed to quantify the properties of the typical set grows linearly with sequence length, despite the exponential growth in the number of typical sequences. We illustrate the framework for the Bernoulli process and the Schlögl model for autocatalytic chemical reactions and demonstrate both the convergence to asymptotic limits and the ability to reproduce exact calculations.

Figure 1

Comparison of the exact fraction of sequences in the typical set, $|A_{\epsilon }^n|/M^n$, as a function of the sequence length, $n$, from enumeration (solid line) to the asymptotic upper bound, $|A_{\epsilon }^n|/M^n\sim e^{n(h_{\mu }+\epsilon -lnM)}$ (dashed line) for a biased coin with $p=[0.7,0.3]$ and $\epsilon =0.02$.

Figure 2

With increasing $n$, the joint probability tends towards a uniform distribution and the sample entropy, $-n^{-1}ln\mu \left({\widehat{\omega }}_n\right)$, distribution concentrates. The changes in distribution occur as individual sequences move between typical (blue) and atypical (red) macrosequences. The dynamics of these macrosequences are an alternative route to quantify the size and probability in the typical set.

Figure 3

Plotting ${\mathcal{C}}_p\left[\overline{\mu }\left({\widehat{\omega }}_n\right)\right]$ against $\overline{\mu }\left({\widehat{\omega }}_n\right)$ in (a) for a random distribution with $M=10$ states. Every point represents the probability of one of the $M^{n+1}$ children. Blue points denote children in $A_{\epsilon }^n$ and red denotes $C_l^n$ and $C_u^n$. The vertical dashed lines mark the scaled bounds on $A_{\epsilon }^n,e^{-n{I}_l}$, and $e^{-n{I}_u}$. Horizontal dashed lines are the scaled bounds for $A_{\epsilon }^{n+1},e^{-(n+1)I_l}$, and $e^{-(n+1)I_u}$. These bounds divide ${\mathcal{C}}_p{\left[\overline{\mu }\left({\widehat{\omega }}_n\right)\right]}_n$ into nine cells which determine the transition probabilities for both $R\left(n\right)$ and $Q\left(n\right)$. The left lower and upper two points highlighted with black circles are $\overline{\mu }\left({\widehat{\omega }}_2\right){\overline{p}}_1$ and $\overline{\mu }\left({\widehat{\omega }}_2\right){\overline{p}}_M$, respectively. The right-hand circles highlight $\overline{\mu }({\widehat{\omega }}_2+1){\overline{p}}_1$ and $\overline{\mu }({\widehat{\omega }}_2+1){\overline{p}}_M$, which become stretched vertically because $\overline{\mu }\left({\widehat{\omega }}_2\right)<\overline{\mu }\left({\widehat{\omega }}_2\right)$, thereby creating the triangle structure. (b) The hypotenuses of one of the $M$ triangles intersects the probability of $M^n$ children (highlighted with black circles).

Figure 4

The dashed black line is the upper bound $e^{n(H+\epsilon -lnM)}$ and crosses are the $\epsilon =0$ bound $e^{n(H-lnM)}$ that is guaranteed only for $n\to \infty$. The fractional size of $|A_{\epsilon }^n|/M^n$ from enumeration (solid black line) and the calculation from our framework (blue line). The parameter $\epsilon$ is 0.02 in all cases. The method here matches the brute force calculation of sequences exactly up to where enumeration is tractable, $n\approx 25$, and agrees with the asymptotic limit near $n\approx 50$.

Figure 5

Holding $k_1$ through $k_4$ fixed and varying $a$ and $b$, Eq. (21) generates one, two, or three real fixed points. There are two solutions at each point on the black line that divides the regions with one and three steady-state solutions.

Figure 6

The (a) size of and (b) the amount of probability in $S_{\alpha }^n$ for a stable fixed point of the Schlögl model (black lines) when $\epsilon =0.1:C_l^n$ (open circles), $C_u^n$ (stars), and $A_{\epsilon }^n$ (black dashed line). Colored symbols are the results from the method here. The (c) size and (d) the probability of $S_{\alpha }^n$ for the unstable fixed point at the same parameter values. There is a second stable fixed point that exhibits qualitatively the same high redundancy behavior as the stable fixed point (data not shown).

Figure 7

The cumulative density ${\rho }_{n+1}\left(y\right)$ is proportional to all the sequences which lie below a particular $y$. Since each sequence lies on the function $l_j$, the point on $l_j\left(y\right)$ can be mapped to ${\rho }_n\left(x\right)$. If $y>{\overline{p}}_j$, as is shown with the rightmost gray line covering $l_1$, then the contribution from ${\rho }_n$ at this point is one.