Online Condensing of Unpredictable Sources via Random Walks

Due to the streaming nature of our source $X$, one would like a condenser (or extractor) for such sources to process each symbol sequentially as it is received. The notion of online condensing achieves exactly this. As in the model from Dodis, Guo, Stephens-Davidowitz, and Xie [7, 8], in (deterministic) online condensing, the function $\mathrm{𝖢𝗈𝗇𝖽}$ is implemented by a procedure that starts in a state $S_0$, and makes a sequence of calls to an update procedure

The length of each state $S_i$ should be not much larger than the final output length $m$. The procedure may then output the final state $S_t\in {\{0,1\}}^m$ (or perhaps some function of $S_t$).

We clarify that the question of whether online condensing is possible is entirely orthogonal to the question of whether seeded condensing is possible. Indeed, a natural question to ask is whether (and how well) can general weak sources be condensed in an online manner. In the case of seeded online condensing (and in some regimes, we provably must use a seed), one may consider an update procedure that also takes as input a seed $Y\in {\{0,1\}}^{\mathrm{\ell }}$ that is independent of the stream $X$, and computes $S_{i+1}\leftarrow \mathrm{𝖴𝗉𝖽𝖺𝗍𝖾}(S_i,X_{i+1},Y)$.³³3 Since the seed length $\mathrm{\ell }$ typically depends on $t$, when the length of the stream $t$ is not known in advance, one can model the use of a uniform seed by also viewing it as a stream of uniform and independent bits. For example, the seed can be initialized to the empty string (or some constant length uniform string), and $\mathrm{𝖢𝗈𝗇𝖽}$ may call, in conjunction with each update, an additional procedure, $Y\leftarrow \mathrm{𝖤𝗑𝗍𝖾𝗇𝖽𝖲𝖾𝖾𝖽}(S_i,Y)$, that may choose to increase the length of $Y$ by one or several bits, depending on the current state $S_i$. Generally, the choice to extend $Y$ will depend on how many symbols $\mathrm{𝖢𝗈𝗇𝖽}$ has seen so far, which would be stored in the state. The guarantee of such a $\mathrm{𝖢𝗈𝗇𝖽}$ should be that at any point in the stream $i$, the state $S_i$ should contain most of the entropy seen so far in $X_1,\mathrm{\dots },X_i$ (or about $|S_i|$, if this length is smaller), and the length of $Y$ relative to $i$ should be small. The hope is that the update procedure accumulates the additional entropy from $X_i$ in each step into the state $S_i$, and thus the final state $S_t$ contains most of the entropy in $X$ (or about the length of $|S_t|$, if this length is smaller). As noted earlier, the advantages of such an online model of condensing are that it allows one to utilize the entropy that was overall contained in the entire stream $X$, even if one does not know the length of the stream $t$ ahead of time. Moreover, when one only wishes to get $m$ bits of entropy out of a very long stream of length $t\gg m$. An online construction would use space $m$ rather than $t$.

In [9], they showed that a natural way to condense a randomness stream is to use its symbols as instructions for a random walk over an expander $G$, starting from an arbitrary fixed vertex (similarly to Theorem 1). The intuition is that if a step in a random walk makes progress towards mixing, then that step accumulates the entropy from the instruction into the vertex distribution. Thus, using the current vertex in the walk as our “state” yields a (deterministic) condenser with output length $m=\log M$, where $M$ is the number of vertices of $G$.⁴⁴4One may notice that committing to a graph of size $M$ may be problematic when the length of the stream is not known ahead of time, as one would like $m$ to be comparable to $t$. This can be fixed with a trick of repeatedly increasing the size of the graph at regular intervals. We discuss this more in Section 1.5.1, and for most of the introduction, we will assume that $t$ is known ahead of time.

In this work, we are primarily focused on sequences $X_1,\mathrm{\dots },X_t$ that may not mix at every step, as is the case for unpredictable sources. We now give broad intuition on how such erroneous steps affect condensing. Suppose that a symbol $X_i$ is highly correlated with the previous instructions $x_1,\mathrm{\dots },x_{i-1}$. Also, assume that the vertex distribution at step $i-1$ is uniform on some set $S$ of size $K$. If $G$ is a $D$-regular graph, then an adversarially chosen $X_i$ may cause the walk to “consolidate” the vertices of $S$ into groups of size $D$. This would result in a vertex distribution that is uniform on a set of size $K/D$, and hence $d=\log D$ bits of entropy were lost. In general, one can show that this is the worst that can happen, and so if there are very few bad steps overall, then overwhelmingly, mixing, and thus condensing, indeed occurs. Realizing this intuition for unpredictable sources poses several challenges, that we discuss further in Section 1.5.

Towards discussing unpredictable sources, let us first review in more detail the previous work, [9], on condensers via random walks. Both here, and in [9], we study random walks on lossless expanders. A degree-$D$ $(K,\epsilon )$-lossless expander on $M$ vertices is an undirected graph $G$ such that for any set $S\subseteq V,|S|\le K$, the size of the neighborhood $\mathrm{\Gamma }(S)$ satisfies $|\mathrm{\Gamma }(S)|\ge (1-\epsilon )D|S|$.⁵⁵5More technically, we consider bipartite graphs $([M],[M],E)$, as these are what the known explicit constructions yield. However, at a high level, this distinction is not necessary. [9] proved that a random walk using $X$, starting from an arbitrary fixed vertex, on a sufficiently good lossless expander, accumulates entropy and thus yields a deterministic condenser.

That is, $\mathrm{𝖢𝗈𝗇𝖽}$ condenses $X$ to within a constant entropy gap, where we say that the entropy gap (with error $\epsilon$) of a distribution $Z\sim {\{0,1\}}^m$ is $\mathrm{\Delta }$ if $Z$ is $\epsilon$-close to an $(m-\mathrm{\Delta })$-source.

But in practice, it may be unreasonable to assert that for every $i$ and every prefix $x_1,\mathrm{\dots },x_i$, the next symbol $X_i$ is highly unpredictable. To address this, [9] does consider generalized versions of CG sources, although the guarantee about $\mathrm{𝖢𝗈𝗇𝖽}(X)$ from Theorem 4 for such sources is much weaker there. In particular, the situation (before this work) becomes quite bleak when introducing the generalization coined $\rho$-error in [9].

It turns out that in the presence of $\rho$-error (together with other error types discussed shortly), general min-entropy sources are almost CG sources in some regime of parameters (see [9, Section 8]). Thus, in general, deterministic condensing to within a constant entropy gap of such sources is impossible. Moreover, before this work, it was unknown whether or not a random walk using $\rho$-almost CG sources mix well in any sense at all. In this paper we show that it is indeed the case that random walks mix, even under the more general notion of unpredictable sources, which captures all previously considered generalizations of CG sources.

As discussed previously, the notion of CG sources is quite strong – it assumes that every prefix leads to a high entropy distribution is quite strong. An unpredictable source does not make such an assumption. Indeed, notice that in the definition of an unpredictable source, we do not directly insist on any guarantee on the (smooth) min-entropy of the distribution $X_i|X_{[1,i-1]}=x_{[1,i-1]}$, only that usually, the next symbol $x_i$ is unlikely conditioned on $x_{[1,i-1]}$. We give unpredictable sources their name as it closely resembles the intermediate objects of the same name that show up in pseudorandom constructions such as reconstructive extractors [18, 15, 17] (for the precise definition of reconstructive extractors, see, e.g., [16]).

When talking about $(\delta ,\rho )$ unpredictable sources, we informally refer to $\delta$ as the “entropy rate” of the unpredictable source, and $\rho$ as its “error rate”.⁷⁷7An $(\delta ,\rho )$ unpredictable source is indeed, roughly, $\rho$-close to an $\delta n$ sources. It is easy to see that this definition captures almost-CG sources with all previously considered error parameters.

Indeed, a $(\delta ,\gamma ,\rho ,\lambda )$ almost CG source is a $(\delta ,\gamma +\rho +\lambda )$ unpredictable source.⁸⁸8It is also true that the converse holds via several averaging arguments, although with a large loss in parameters. We prefer to study and phrase our results for unpredictable sources, as the statements are clean, and with minimal artifacts of analysis. Additionally, as was the case for almost CG sources with all error parameters, every general source with $(1-\rho )n$ min entropy is an unpredictable source, with a much more straightforward argument, with fewer constraints on $\rho$, and with less loss in converting $\rho$ into the error parameters of an almost CG source (see [10, Proposition 6.4]). In this work, we give the following result for unpredictable sources, analogous to Theorem 4:⁹⁹9Theorem 4 and 2 are analogous in the sense that they both yield a condenser with constant entropy gap for their respective class of sources. There is a key difference in that Theorem 4 is seedless, whereas 2 is seeded. This is necessary. As we have discussed before, general weak sources are unpredictable sources.

As suggested by prior discussion, the construction is again to simply use $X$ as instructions for a random walk on a lossless expander, with the random seed indicating the stopping time. In order to show that such a walk mixes, we develop a new analysis, different than that of [9], which we discuss in detail in Section 1.5.

Let us briefly discuss the error term in the theorem’s statement. First, roughly speaking, the term $\epsilon D^{1-\delta }$ is the probability that a set $S$ “does not expand” in some sense. For example, $\epsilon D^{1-\delta }$ is the probability over a uniformly chosen vertex $v\in S$ and uniform neighbor $\mathrm{\Gamma }(v)$, that $\mathrm{\Gamma }(v)$ has another neighbor in $S$. Broadly speaking, events such as this are undesirable: they represent “collisions” of paths in the random walk. Thus we expect such an error term, as it corresponds to the (inherent) error of the expander. We should also expect the error rate $\rho$ to appear for the same reason: this corresponds to the probability that “expansion does not occur” due to low quality randomness (as opposed to the expander’s error). Indeed, if one considers the $(1,\rho )$ unpredictable distribution $X$ that is $0^n$ with probability $\rho$, and uniform otherwise, one can see that at every step of a random walk using $X$, some vertex will have probability mass at least $\rho$.

Finally, we comment on the relationship between these parameters. In general, as $\rho$ is an error probability over the entire space of $X$, it is possible for it to be sub-constant. While $\rho$ can be subconstant, the constant-$\rho$ regime is more interesting, and our theorem handles the case when $\rho$ is in fact fairly large, for example $\rho \ge D^{-\delta }$. Thus, the error term can be thought of as $O(\rho /\delta )$, and in fact it is necessary that . Intuitively, using a $(\delta ,\rho )$ unpredictable source, in a typical run of the random walk, one expects there to be roughly $t$ steps each accumulating $\delta d$ bits of entropy (for a total of $\delta dt$ entropy gained), and roughly $\rho t$ steps that lose $d$ bits of entropy (for a total of $\rho dt$ entropy lost). Thus overall, one should not expect anything good to happen when the entropy rate of the unpredictable source is smaller than the error rate.

We can also show that even without a random stopping time, we can use our new analysis of random walks to get a result about deterministic condensing, although, as expected, the entropy gap is not constant.

Overall, Theorem 2 and Theorem 3 indicate that it is indeed possible to condense a very general class of sources in an online manner.

We are now ready to present a technical overview of how we analyze random walks via unpredictable sources. Since unpredictable sources subsume CG sources, we’ll start with discussing the challenges inherent to both sources, and the previous solution for CG sources. An initial observation is that for both types of sources, spectral analysis fails, and for two main reasons. The first one is that spectral expanders may not be lossless, and even the best spectral expanders may only be $(K,\epsilon =1/2)$-lossless. Such expansion is insufficient for us, as it intuitively means that for a distribution on a set of vertices $S$, at least half of all edges leaving $S$ may lead to collisions (with perhaps $D$ other nodes in $S$). Since, as discussed before, collisions imply a loss in entropy, even the good high entropy steps fail to mix, unless the steps were almost uniform.

The second reason is that random walks using CG sources and unpredictable sources are non-Markovian: The distribution of the next step depends on the entire history of the walk up until that point. Therefore, we cannot analyze the evolution of the vertex distribution at each step by repeatedly applying a transition matrix and bounding the norm of the corresponding probability vector. Moreover, the distribution of the next instruction $X_{i+1}$, given a prefix $x_1,\mathrm{\dots },x_i$, can be adversarial. That is, whatever the vertex distribution $p_i$ may be for each $i$, $X_{i+1}$ could be the worst possible edge distribution that yields the least amount of improvement for $p_{i+1}$ (while still satisfying the overall conditions on the source $X$).

Nevertheless, [9] provides a direct analysis that shows that the norm of the vertex distribution does evolve favorably over time. Specifically, they show that for the $q$-norm, setting $q=1+\alpha$, if $p_i$ is the vertex distribution of the random walk at step $i$, then ${\Vert p_{i+1}\Vert }_q^q\le \frac{1}{D^{\delta \alpha }}{\Vert p_i\Vert }_q^q$. More concretely they prove:

This essentially implies that the entropy of the vertex distribution increases by at least $\delta d$. Thus, inductively, the final distribution will have ${\Vert p_t\Vert }_q^q\le \frac{1}{K^{\alpha }}$, implying that it has min entropy roughly $k$.

For ease of exposition, for the remainder of the section, we consider unpredictable sources where for every $i$, ${\rho }_i=\rho$ for some constant $\rho$. This case captures most of the intuition and difficulty at a high level.

So far, the main takeaway from our results is that lossless expanders can handle unpredictable sources with low entropy rate. On the other hand, spectral expanders can handle unpredictable sources with high entropy rate, as can be seen by looking at the classic random walks based extractor.

However, even for the case of sources with high entropy, the lossless expander random walk yields a quantitatively better result. In the classic expander random walk extractor (or sampler), based on the expander Chernoff bound, in order to achieve an error of $\rho$ in the output distribution, it is necessary for the entropy of the input source $X$ to be at least $(1-{\rho }^2/C)n$ for some constant $C$.

The ${\rho }^2$ factor is inherent in the use of the expander Chernoff bound. On the other hand, if one uses our new lossless expander random walk to condense to constant entropy gap (and then apply known constructions of extractors for sources with constant entropy gap with short seed length), one only needs the input source to have entropy $(1-\rho /C^{\prime })n$ for some constant $C^{\prime }$ in order to obtain final output error $\rho$. In addition, all of this can be implemented in a fully online manner, even when $n$ is not known ahead of time.

Before introducing $\rho$-almost CG sources, [9] first generalizes CG sources by introducing what is coined $\lambda$-error.

Unlike $\rho$-error, for $\lambda$-error, [9] is still able to construct condensers by running a random walk using $X$, although not with a constant entropy gap. Instead, the gap is roughly $\lambda m$, for reasons inherent to the random walk construction itself. Intuitively, for the $\lambda$ fraction of bad indices $i$, $X_i$ could be completely determined (and adversarially chosen) based on $x_{i-1}$. Therefore, whatever edge $x_{i-1}$ instructs the walk to take, $x_i$ could instruct to return via the same edge, effectively wiping out the progress made from $x_{i-1}$. Overall, when all the bad indices are at the end, it can wipe out $\lambda t$ steps of entropy accumulation, leaving an entropy gap of $\lambda t$.¹³¹³13When $\lambda >0$ but the $\lambda$-fraction of bad blocks is nicely distributed in the sense that each suffix contains at most $\lambda$-fraction of bad blocks (up to an additive term), we can regain constant entropy gap. See [9, Section 3.1], where this property is called suffix friendliness. The case of $\lambda$-error is interesting in its own right. In fact, a recent work of Chattopadhyay, Gurumukhani, and Ringach [4], shows that deterministic condensing of $\lambda$-almost $\delta$-CG sources is impossible, even with large entropy gap, in the regime where $\lambda \ge \frac{1}{2}$.

Goodman, Li, and Zuckerman [13] showed how to condense CG sources even when the blocks are long, and the entropy rate is subconstant. However, their constructions are not online, and they don’t address the case of almost CG sources.¹⁴¹⁴14However, their constructions work for suffix-friendly CG sources.

Previous works that directly consider (deterministic) online extraction [7, 8] assume a strong notion of unpredictability, wherein the $X_i$-s are independent (but with some min-entropy). In their model, they assume that for every $i$, $|S_i|=|X_i|=n$, with the length of the stream $t$ sufficiently long that the total entropy $k$ of $X$ is at least $n$. Recall that in our work, we generally think of each $X_i\sim {\{0,1\}}^d$ for some constant $d$, $n=dt$, and $|S_t|\approx k\ll n$. More specifically, [7] considers how entropy accumulates for specific update functions that are based off of practical random number generation. They show that entropy accumulates when the $X_i$-s are independent draws from certain classes of distributions known as 2-monotone distributions. [8], considers linear update functions and shows that entropy accumulates when the $X_i$-s are independent $k$-sources.

Other previously studied notions of sequential sources include Somewhere Honest Entropy Look Ahead (SHELA) sources [1], also known as online Non-Oblivious Symbol Fixing (oNOSF) sources [4]. Such sources are essentially the $\lambda$-error CG sources discussed above, except for two distinctions. The first is that the good steps are all high entropy distributions that are independent from each other. The second is that each bad step only depends on previous blocks.¹⁵¹⁵15The latter property is why those sources are called “online” – an adversary corrupts the bad blocks while only knowing the history. They do not give online condensers for such sources. Aggarwal et a. [1] shows that extracting from oNOSF sources is impossible, however one can convert oNOSF sources into uniform oNOSF sources. Chattopadhyay, Gurumukhani, and Ringach explored the limits of online condensing of such sources [4], and later achieved constructions with essentially optimal parameters [3].

A recent work by Xun and Zuckerman [19] provides constructions of strong offline extractors whose seed length has nearly optimal dependence on $n$ and $\epsilon$: for any desired $\alpha >0$, their construction gives an extractor with seed length $(1+\alpha )\log (n-k)+(2+\alpha )\log 1/\epsilon +O(1)$, as long as the entropy rate $k/n$ is sufficiently close to $1$ (depending on $\alpha$). To compare, our results discussed in Section 1.6 provide online extractors with seed length $\log n+O(\log 1/\epsilon )+O(1)$ when $k/n\ge 1-\mathrm{\Theta }(\epsilon )$.