Chapter 46: Pseudorandomness and Expander Structures

When do spectral guarantees make a deterministic graph behave randomly?

Random-like behavior is a property to specify, not a synonym for looking irregular. For a finite undirected $d$-regular graph, let $A$ be its adjacency matrix and let $P=A/d$ be the transition matrix of the walk that chooses a neighbor uniformly. The uniform distribution $u$ on the $N$ vertices is stationary because every row and column of $P$ sums to one.

The all-ones vector has adjacency eigenvalue $d$. Let $\lambda$ be the largest absolute eigenvalue on its orthogonal complement, and put $\rho=\lambda/d$. If $\rho\lt1$, repeated multiplication contracts every centered vector by at least a factor $\rho$ per step. For a walk starting at a fixed vertex,

$$\lVert P^t\delta_v-u\rVert_2\le\rho^t\sqrt{1-1/N}.$$

Total variation distance is half the sum of absolute coordinate differences. Cauchy–Schwarz therefore gives the useful bound

$$d_{\mathrm{TV}}(P^t\delta_v,u)\le\frac12\sqrt{N-1}\,\rho^t.$$

The left side is always at most one, so truncate the bound at one when needed. This is a proof of a sampling guarantee from a spectral hypothesis: it does not assert independence between consecutive walk positions.

For a fully explicit model, use the Petersen graph. Its vertices are the ten two-element subsets of $\{1,2,3,4,5\}$, with two vertices adjacent exactly when their subsets are disjoint. Each vertex has three neighbors, so the graph has fifteen edges. Its adjacency spectrum is $3$ once, $1$ five times, and $-2$ four times. Thus $\rho=2/3$, and the variation bound is $(3/2)(2/3)^t$.

The spectrum can be certified without trusting a numerical eigensolver. Adjacent vertices have no common neighbor, while two distinct nonadjacent vertices have exactly one common neighbor. Hence

$$A^2=2I-A+J,$$

where $J$ is the all-ones matrix. On the centered subspace, $J=0$, so every eigenvalue satisfies $z^2+z-2=0$ and is $1$ or $-2$. Their multiplicities sum to nine and their sum is $-3$, because $\operatorname{tr}A=0$ and the constant eigenvalue is three. This gives multiplicities five and four. The same identity rules out a second eigenvector of eigenvalue three, establishing connectedness.

This exact graph definition, spectral proof, and variation bound are the foundation needed for the core investigation. The numbered sections are optional research extensions. Earlier connections are the probabilistic method, entropy methods, spectral combinatorics, and coding and designs.

46.1 Spectral expanders

Optional extension; not required to complete the chapter foundation.

A bounded-degree expander family is a sequence of graphs whose sizes grow while a uniform expansion parameter stays bounded away from its failure value. In a two-sided spectral convention, $d$ is fixed and $\rho\le\rho_0\lt1$ throughout the family. A single graph with a good spectrum is a finite model, not an infinite family by itself.

It is useful to distinguish $\rho$ from the one-sided spectral gap $\gamma=1-\theta_2$, where $\theta_2$ is the second-largest eigenvalue of $P$ in ordinary decreasing order. For a connected regular graph, define conductance

$$\Phi(G)=\min_{0\lt\lvert S\rvert\le N/2}\frac{e(S,V\setminus S)}{d\lvert S\rvert}.$$

The established Cheeger inequalities give $\gamma/2\le\Phi\le\sqrt{2\gamma}$. Proof scope: the lower bound follows by applying the Laplacian Rayleigh quotient to a centered cut indicator; the sweep-cut proof of the upper bound is omitted. These use the one-sided gap, so a bipartite graph can have good cut expansion while its nonlazy walk fails to mix. The spectral-expansion framework and algorithmic constructions are treated in the primary paper of Reingold, Vadhan, and Wigderson.

Solved example. For the Petersen graph, $\theta_2=1/3$, so $\gamma=2/3$ and $\Phi\ge1/3$. A five-cycle in the graph has five boundary edges, since each of its five vertices has two cycle neighbors and one outside neighbor. Its conductance is $5/(3\cdot5)=1/3$. Thus the exact conductance is $1/3$, while the two-sided contraction parameter is $2/3$. These are different numbers describing different guarantees.

A lazy walk uses $P_L=(I+P)/2$. Its eigenvalues are $(1+\theta_i)/2$, eliminating period-two behavior. It changes the sampling process: a step now stays put with probability one-half.

Exercise. Compute the lazy Petersen spectrum and its centered operator norm. Hint: transform each normalized eigenvalue. Solution: the spectrum is $1$, $2/3$ with multiplicity five, and $1/6$ with multiplicity four. Its centered norm is $2/3$, numerically equal here to the nonlazy absolute norm, though the distributions at individual times differ.

46.2 Expander mixing lemma

Optional extension; not required to complete the chapter foundation.

For vertex subsets $S,T$, define $e^{\mathrm{ord}}(S,T)=\sum_{s\in S,t\in T}A_{st}$. This counts ordered adjacent pairs: when $S=T$, each internal undirected edge contributes twice. Suppose $A$ is symmetric, the graph is $d$-regular, and its centered eigenvalues have absolute value at most $\lambda$. Then the established expander mixing lemma says

$$\left\lvert e^{\mathrm{ord}}(S,T)-\frac dN\lvert S\rvert\lvert T\rvert\right\rvert\le\lambda\sqrt{\lvert S\rvert\left(1-\frac{\lvert S\rvert}N\right)\lvert T\rvert\left(1-\frac{\lvert T\rvert}N\right)}.$$

Complete proof. Put $x=\mathbf1_S-(\lvert S\rvert/N)\mathbf1$ and $y=\mathbf1_T-(\lvert T\rvert/N)\mathbf1$. Their coordinates sum to zero. Regularity identifies the deviation with $x^{\mathsf T}Ay$, the centered operator bound gives absolute value at most $\lambda\lVert x\rVert_2\lVert y\rVert_2$, and expanding the two norms gives the formula. Dropping the factors in parentheses yields the common weaker bound $\lambda\sqrt{\lvert S\rvert\lvert T\rvert}$. The relevant spectral operator framework is in Reingold–Vadhan–Wigderson; the argument here is supplied in full.

Exercise. Bound the size of an independent set using the same centered formula with $S=T$. Hint: the ordered incidence count is zero. Solution: for $s=\lvert S\rvert\gt0$, $ds^2/N\le\lambda s(1-s/N)$, hence $s\le\lambda N/(d+\lambda)$. For the Petersen graph this gives $s\le4$, attained by the four vertices containing label one.

46.3 Explicit expander constructions

Optional extension; not required to complete the chapter foundation.

An explicit description allows one to produce the graph deterministically. A strongly explicit family supports neighbor queries from a vertex label and an edge label in time polynomial in the bit length of the vertex label. This is stronger than an algorithm taking polynomial time in the total number of vertices to print every edge.

Solved example. For the Petersen construction, the neighbors of $ij$ are the three two-subsets of its three-element complement. For instance, the neighbors of $12$ are $34,35,45$. This rule generates all fifteen edges without search. The SVG labels vertices by their defining subsets and shows an outer cycle, five spokes, and an inner star. Every drawn edge joins disjoint subsets, and every vertex has degree three.

For scalable explicit families, the zig-zag product gives a combinatorial route. Let $G$ be a $D$-regular graph on $N$ vertices with a rotation map that pairs the two labeled ends of each edge. Let $H$ be a $d$-regular graph on the $D$ edge labels. The product has vertices $(v,i)\in V(G)\times[D]$ and degree $d^2$. A step moves within the label graph, traverses one rotated edge of $G$, then moves within the new label graph. Its normalized operator is

$$Z=(I\otimes P_H)R(I\otimes P_H),$$

where $R$ is the symmetric permutation operator encoding the rotation. A classical established bound is $\rho(Z)\le\rho(G)+\rho(H)+\rho(H)^2$. Used with graph powering and a suitable fixed seed graph, the construction yields constant-degree expander families. Primary source: Reingold, Vadhan, and Wigderson.

Proof sketch and omitted prerequisites. Split vectors into cloud-constant and within-cloud-centered parts. The small graph contracts the second part; the large graph controls the first after rotation. The detailed operator estimate and the recursion giving efficient neighbor queries are omitted. The displayed bound can exceed one for poorly chosen parameters, so arbitrary inputs do not automatically give a useful expander. Product graphs may have loops and parallel edges; their stochastic-operator convention must be retained.

Exercise. If $G$ has $N$ vertices and degree $D$, and $H$ has $D$ vertices and degree $d$, what are the product's size and degree? Hint: count vertex-label pairs and the two small steps. Solution: $ND$ vertices and degree $d^2$. Squaring $G$ separately keeps its vertex count but changes its walk degree to $D^2$ and squares its centered contraction parameter, with multiplicities retained.

46.4 Extractors and dispersers

Optional extension; not required to complete the chapter foundation.

A source $X\in\{0,1\}^n$ has min-entropy $H_\infty(X)=-\log_2\max_x\Pr(X=x)$. A strong seeded $(k,\varepsilon)$-extractor is a function $\operatorname{Ext}(x,s)$ with $m$ output bits such that for every source of min-entropy at least $k$, and an independent uniform seed $S$, the joint distribution $(S,\operatorname{Ext}(X,S))$ has total variation distance at most $\varepsilon$ from $(S,U_m)$.

A disperser has a weaker support guarantee: for every input set of size at least $2^k$, outputs over that set and all seeds cover at least a $(1-\varepsilon)$ fraction of the output alphabet. An extractor implies this disperser property by applying it to the uniform source on the input set; missing output mass contributes to statistical distance. The converse need not control output frequencies.

A two-universal hash family satisfies $\Pr_S(h_S(x)=h_S(x'))\le2^{-m}$ for distinct inputs. The established leftover hash lemma gives

$$d_{\mathrm{TV}}\bigl((S,h_S(X)),(S,U_m)\bigr)\le\frac12\sqrt{2^{m-k}}.$$

Proof sketch: the collision-probability calculation uses the universal collision bound and $\sum_x\Pr(X=x)^2\le2^{-k}$; Cauchy–Schwarz converts the resulting squared-distance estimate to total variation. The full weighted calculation is omitted. A primary extractor treatment using this tool is Nisan and Zuckerman's Randomness is Linear in Space.

Solved example. Let $X$ be uniform on $00,01$, so $H_\infty(X)=1$. Seed the affine hash $h_{a,b}(x)=a\cdot x+b$ over $\mathbb F_2$, with $a\in\mathbb F_2^2$ and $b\in\mathbb F_2$ independent uniform. Distinct inputs collide for exactly half the $a$ values, so the family is two-universal. For half the seeds, the coefficient of the varying second input bit is one, and output is uniform. For the other half it is zero, and output is constant, giving conditional variation distance $1/2$. The joint strong distance is therefore $1/4$, below the lemma's bound $1/2$ for $m=k=1$.

Exercise. Why must the seed be independent? Hint: consider $X\oplus S$ for uniform bits with $S=X$. Solution: each marginal is uniform but the output is always zero. With independent uniform bits the output would be uniform even jointly with the seed. Uniform seed marginals alone are insufficient.

46.5 k-wise independence

Optional extension; not required to complete the chapter foundation.

Random variables $Y_1,\ldots,Y_N$ are $k$-wise independent if every selection of at most $k$ distinct coordinates has the product of its marginal distributions. It is a joint-distribution guarantee, weaker than full independence when $k\lt N$.

Over $\mathbb F_q$, choose independent uniform coefficients $a_0,\ldots,a_{k-1}$ and evaluate

$$Y_t=a_0+a_1t+\cdots+a_{k-1}t^{k-1}$$

at distinct field elements $t$, with $N\le q$. Any $k$ evaluations determine the coefficients through an invertible Vandermonde matrix, so the evaluations are uniform and $k$-wise independent. Smaller selections are uniform by marginalization. This is a complete proof of the construction's independence guarantee. It uses $k$ uniform field elements rather than $N$; for $q$ a power of two the exact seed length is $k\log_2q$ bits.

Solved example. In $\mathbb F_3$, use $Y_t=a+bt$ for $t=0,1,2$. The nine equally likely coefficient pairs give:

$$000,\ 012,\ 021,\ 111,\ 120,\ 102,\ 222,\ 201,\ 210.$$

Every coordinate pair takes all nine ordered field pairs once. Nevertheless, $Y_0+Y_1+Y_2=0$ always, so the three coordinates are not fully independent. Their field-valued seed needs an exact uniform ternary sampling rule; one must not pretend that $\log_2 9$ is an integer number of fair bits with no sampling overhead.

Pairwise independence is sufficient for variance calculations of sums, but it does not justify arbitrary Chernoff bounds requiring higher independence or other structure. Primary limited-randomness applications appear in Naor and Naor's small-bias constructions. The polynomial evaluation proof here is self-contained, without invoking their broader construction theorem.

Exercise. For pairwise independent unbiased bits $B_1,\ldots,B_N$, compute the variance of their sum. Hint: covariance vanishes between distinct coordinates. Solution: $\operatorname{Var}(\sum_iB_i)=N/4$. Chebyshev gives $\Pr(\lvert\sum_iB_i-N/2\rvert\ge t)\le N/(4t^2)$. This guarantee is valid without asserting exponentially small tails.

46.6 Pseudorandom generators and combinatorial constructions

Optional extension; not required to complete the chapter foundation.

A pseudorandom generator for a specified test class $\mathcal F$ is a deterministic function $G:\{0,1\}^s\to\{0,1\}^n$ such that

$$\left\lvert\mathbb E f(G(U_s))-\mathbb E f(U_n)\right\rvert\le\varepsilon\qquad(f\in\mathcal F).$$

Here tests take values in $\{0,1\}$. The test class is part of the theorem. When $s\lt n$, no generator can fool every test with small error: membership in its image distinguishes it from uniform with advantage at least $1-2^{s-n}$.

Solved example. Define $G(a,b)=(a,b,a\oplus b)$ for two independent uniform bits. Its image is $000,011,101,110$. Any test depending on at most two specified output coordinates is fooled exactly because those coordinates are uniform and independent. But the three-bit parity test accepts every generated output and exactly half the uniform outputs, giving advantage $1/2$. Thus the same distribution is excellent for one test class and fails another.

A distribution is $\varepsilon$-biased if every nonempty parity character has absolute expectation at most $\varepsilon$. This fools every single parity predicate within $\varepsilon/2$, but not automatically every Boolean function. Explicit small-bias constructions and applications are established in Naor and Naor. Proof scope: parity-test conversion is immediate; their seed-length/construction theorem is not reproduced or claimed optimal here.

An expander walk is another limited-randomness device. Once a uniform starting vertex and a sequence of independent neighbor choices are supplied, it gives a correlated sample sequence. The spectrum bounds correlations of observables; it does not make the entire trajectory uniformly distributed over all vertex strings. Nor does a spectral sampler alone establish cryptographic security against arbitrary efficient distinguishers.

Exercise. Give an explicit test proving the three-bit example is not $\varepsilon$-biased for any $\varepsilon\lt1$. Hint: use its deterministic parity relation. Solution: $(-1)^{Y_1+Y_2+Y_3}=1$ always, so this character has expectation one. Pairwise independence did not control a three-coordinate parity.

46.7 Quasirandom graphs and hypergraphs

Optional extension; not required to complete the chapter foundation.

Dense quasirandomness concerns a sequence of graphs with edge density tending to a fixed $p\in(0,1)$ and discrepancy $o(N^2)$ across all vertex subsets. A central established theorem of Chung, Graham, and Wilson makes several dense properties equivalent, including the appropriate edge-density and four-cycle-count conditions and random-like counts of every fixed graph. Copies and asymptotic normalizations must be fixed consistently; labeled injective copies of a fixed graph $H$ have leading count $p^{e(H)}N^{v(H)}$.

Proof sketch and omitted prerequisites. Four-cycle counts control codegree fluctuations by Cauchy–Schwarz, leading to cut discrepancy; iterative embedding then gives fixed-subgraph counts. The equivalence proof and its handling of repeated vertices are omitted. The theorem is a dense asymptotic result; it is not a statement that every sparse expander has the same relative counts as an Erdős–Rényi graph.

Solved example. The Petersen graph has density $15/\binom{10}2=1/3$ and no triangles. A $G(10,1/3)$ graph has expected triangle count $\binom{10}3/27=40/9$. This finite discrepancy does not contradict its spectral guarantees, and it does not refute a dense asymptotic theorem. Its degree-three model sits in a different regime from growing dense quasirandom graphs.

Hypergraphs have genuinely different quasirandomness notions. To see why, independently label each pair of $[N]$ with a random bit, and include a triple when the sum of its three pair labels is zero modulo two. Each triple is present with probability one-half. On a four-vertex set, however, the parities of its four triples sum to zero because each pair label appears twice. Hence a pattern with exactly three present triples is impossible, though independently sampled triple bits would permit it. Hyperedge density and some coarse tests therefore do not imply all higher-order pattern counts. The example is a direct proof of a dependence; richer hypergraph notions are treated in Gowers's hypergraph regularity theorem.

Exercise. In that four-vertex pair-label model, compute the probability all four triples are present. Hint: three parity equations are independent and the fourth follows. Solution: it is $2^{-3}=1/8$, whereas independent triple bits would give $1/16$. The four constraints have rank three over $\mathbb F_2$.

46.8 High-dimensional expanders

Optional extension; not required to complete the chapter foundation.

A simplicial complex is a collection of vertex subsets closed under taking subsets. A face with $k+1$ vertices has dimension $k$. Graphs control vertices and edges; higher-dimensional expansion adds constraints involving triangles and larger faces. There are several inequivalent definitions, including coboundary expansion, cosystolic expansion, and local spectral expansion. A theorem in one framework must state the bridge before claiming another.

For a concrete cochain model over $\mathbb F_2$, a zero-cochain labels vertices and a one-cochain labels edges. The coboundaries are

$$\delta_0f(uv)=f(u)+f(v),\qquad \delta_1g(uvw)=g(uv)+g(uw)+g(vw).$$

Every vertex label appears twice in a triangle sum, so $\delta_1\delta_0=0$. A one-cocycle satisfies $\delta_1g=0$; a one-coboundary is a cut labeling $\delta_0f$. Their quotient is the first cohomology group. A quantitative coboundary-expansion inequality compares the normalized number of violated triangle constraints with distance from the coboundary space; weights and normalization are essential parts of such an inequality.

Solved example. Use the boundary of a tetrahedron: four vertices, all six edges, all four triangles, and no four-vertex face. If a one-cochain satisfies every triangle parity, choose vertex $1$ as an anchor, set $f(1)=0$ and $f(i)=g(1i)$ for $i=2,3,4$. The triangle $1ij$ implies $g(ij)=f(i)+f(j)$. Thus every cocycle is a cut. There are exactly eight such edge labelings, since vertex colorings have the global-complement redundancy. In matrix terms $\delta_1$ has rank three on a six-dimensional edge space, and its kernel equals the three-dimensional cut space.

This verifies vanishing first cohomology for one finite complex. It is not a proof of uniform quantitative expansion for a growing bounded-degree family. Established explicit high-dimensional constructions with agreement-testing applications appear in Dinur and Kaufman. Omitted prerequisites: Ramanujan complexes and the local-to-global agreement theorem.

Exercise. Label only edge $12$ by one. Which triangle checks fail? Hint: inspect triangles containing that edge. Solution: $123$ and $124$ fail, while $134$ and $234$ pass. The violation fraction is $1/2$ under uniform triangle weighting. Its edge distance to the zero cut is at most $1/6$; asserting a global expansion constant requires minimizing over every cochain and nearest cut, not this one test.

46.9 Local spectral expansion

Optional extension; not required to complete the chapter foundation.

The link of a face $\sigma$ in a complex $X$ is the complex

$$X_\sigma=\{\tau:\tau\cap\sigma=\varnothing,\ \tau\cup\sigma\in X\}.$$

For a two-dimensional pure complex, the link of a vertex is a graph whose edges correspond to triangles containing that vertex. A two-sided local spectral condition asks that these graph walks, and the relevant lower links including the empty-face graph, have centered absolute eigenvalues bounded by $\lambda\lt1$. In nonregular links, use the reversible normalized walk and its stationary measure; uniform vertex measure is not automatic.

Solved example. In the full tetrahedron boundary, the empty-face graph is $K_4$ with normalized centered eigenvalues $-1/3$, and every vertex link is $K_3$ with centered eigenvalues $-1/2$. Thus this exact model satisfies the stated two-sided local bound $\lambda=1/2$.

Now remove triangle $234$, keeping the other three triangles and all their faces. The one-skeleton is still $K_4$, and the complex remains pure. The link of vertex $2$ becomes a three-vertex path: its edges are $13$ and $14$. The normalized walk has eigenvalues $1,0,-1$, hence centered absolute norm one. The global graph spectrum is unchanged while the local two-sided guarantee fails. This proves why one-skeleton expansion alone is insufficient to check this local condition.

There are established local-to-global results for walks and agreement tests under specified dimension, connectedness, weighting, and spectral hypotheses; see Dinur–Kaufman. Proof scope: the link calculations are complete; the general theorem and its parameter losses are not reproduced. A local graph bound does not, by its name alone, imply every version of topological expansion.

Exercise. What is the stationary distribution of the three-vertex path link? Hint: it is proportional to degree. Solution: its middle vertex has probability $1/2$ and each endpoint probability $1/4$. Treating this link as regular would give the wrong sampling measure and operator comparison.

46.10 Applications to coding, algorithms, and complexity

Optional extension; not required to complete the chapter foundation.

For a bipartite Tanner graph with variable vertices on the left, each of degree $d$, impose a binary parity check at every right vertex. Suppose every nonempty left set $S$ of size at most $s_0$ has more than $d\lvert S\rvert/2$ distinct check neighbors. Then no nonzero codeword can have support size at most $s_0$. Indeed, if every neighboring check touched the support at least twice, counting incidences would give $d\lvert S\rvert\ge2\lvert\Gamma(S)\rvert$, a contradiction. A check touching it exactly once fails its parity equation. This proves minimum distance at least $s_0+1$.

This is a complete distance certificate. Efficient bit-flipping decoding needs stronger expansion hypotheses and an algorithm analysis; it does not follow automatically from this half-neighborhood inequality. Sipser and Spielman's Expander Codes is a primary source for coding constructions and decoding guarantees.

Solved example. Take three variable bits $x_1,x_2,x_3$ and checks $x_1+x_2=0$, $x_2+x_3=0$, $x_3+x_1=0$. Every variable has degree two. A singleton has two check neighbors, more than one; a pair has three neighbors, more than two. Thus $s_0=2$ and distance is at least three. The code is exactly $\{000,111\}$, so distance is three. Majority decoding corrects one error; a single zero check does not prove that every check vanishes.

For a spectral sampler, let $X_0,\ldots,X_{t-1}$ be a stationary walk with centered absolute norm $\rho\lt1$, and let $f:V\to[0,1]$. If $\sigma^2=\operatorname{Var}_u(f)$, then

$$\left\lvert\operatorname{Cov}(f(X_0),f(X_k))\right\rvert\le\sigma^2\rho^k,$$

so the sample mean satisfies

$$\operatorname{Var}\left(\frac1t\sum_{j=0}^{t-1}f(X_j)\right)\le\frac{\sigma^2}{t}\frac{1+\rho}{1-\rho}.$$

The covariance bound follows from the centered operator, and summing the geometric series over time lags proves the variance bound. Chebyshev gives an error probability bound by dividing it by the squared desired error. For the Petersen walk, this is at most $5/(4t)$ because $\rho=2/3$ and $\sigma^2\le1/4$. This bound can exceed one at small $t$ and should be truncated there. A nonuniform start requires a separate burn-in or nonstationary analysis.

The walk uses one uniform vertex choice followed by $t-1$ uniform choices among $d$ neighbors. In the ideal alphabet model this is entropy $\log_2N+(t-1)\log_2d$, compared with $t\log_2N$ for independent vertex samples. Exact fair-bit implementations for non-power-of-two alphabets require rejection sampling or another explicit method. Such randomness recycling and the use of expanders in complexity are established themes in Reingold–Vadhan–Wigderson; no general PRG or cryptographic guarantee is inferred from this variance calculation.

Exercise. Use the Petersen stationary variance bound to guarantee error at most $1/10$ with failure probability at most $1/10$. Hint: apply Chebyshev to the mean. Solution: it suffices that $[5/(4t)]/(1/10)^2\le1/10$, giving $t\ge12500$. This conservative proved guarantee is not a sharp mixing-time claim or a claim that $12500$ samples are empirically necessary.

Compare an explicit expander with a random construction

Compare deterministic guarantees with finite random evidence under the same degree and vertex count. Use the Petersen graph as the explicit object and uniformly sampled simple cubic graphs on ten labeled vertices as the random objects. Mixing supports sampling with fewer random choices; expansion also supplies parity-code distance certificates under a separate Tanner-neighborhood hypothesis. A network or distributed-sampling application benefits from these precisely stated cut and correlation guarantees rather than from a picture that merely looks random.