# A crossover code for high-dimensional composition

Rich Pang
Computational Neuroscience Center
University of Washington
Seattle, WA 98195
rpang at uw dot edu

###### Abstract

We present a novel way to encode compositional information in high-dimensional
(HD) vectors. Inspired by chromosomal crossover, random HD vectors are
recursively interwoven, with a fraction of one vector’s components masked out
and replaced by those from another using a context-dependent mask. Unlike many
HD computing schemes, "crossover" codes highly overlap with their base
elements’ and sub-structures’ codes without sacrificing relational
information, allowing fast element readout and decoding by greedy
reconstruction. Crossover is mathematically tractable and has several
properties desirable for robust, flexible representation.

##  1 Introduction

A common problem faced by intelligent systems is how to encode objects of
variable complexity in fixed dimensions. Ideally, similar objects should have
similar codes, new objects should not require rearranging existing codes, and
there should be no limit on object complexity. Distributing codes across high-
dimensional (HD) vectors offers a solution with potential robustness,
flexibility, and generalization [1, 2]; but how does one store compositional
relations, like order or binding, in such a code, e.g. to distinguish AB vs BA
or ((A,B), (C,D)) vs ((A,D), (C,B)), respectively? While trained systems like
deep networks have some implicit capacity for this [3, 4, 5], it is unclear
how these might handle complexity beyond that of their training data and
challenging to quantify internal distributed representations [6]. An
alternative approach, known as HD computing (HDC), is to assign random HD
vector codes to a set of "base" elements of the data (e.g. symbols), then
impose a priori rules for composing these into richer structures (e.g. words)
[7, 8, 9]. HDC’s advantages are (1) random HD vectors tend to have very low
overlap, enabling large element codebooks, (2) there is no hard limit on data
complexity, and (3) encoding is often analytically tractable. While most
systems must of course undergo some amount of training, HDC provides a
compelling blueprint for flexible representation.

An ideal code should allow fast readout of both a composition’s base elements
and their relations, but most HDC schemes support one or the other. Sums of
random HD vectors, for instance, have high overlap (low distance under usual
metrics) to their elements, enabling element readout via overlaps with the sum
[10, 11, 12]; but cannot encode relations. HDC operations like circular
convolution [7], permutation [13, 14], or matrix multiplication [15], yield
codes with cue-recoverable relations (cue A recovers B from ((A,B),(C,D))),
but low overlap to the composition’s base elements, precluding fast element
readout without cues (but see [16]); this also conflicts with our desire that
AB’s code should resemble A’s more than C’s. Here we present a new HD
composition operation inspired by chromosomal crossover, where two vectors $X$
and $X^{\prime}$ are ordered or bound by masking out a fraction of $X$’s
components and replacing them with those from $X^{\prime}$; relational
information is encoded in the context-dependent mask $\mu_{:}(X,X^{\prime})$.
"Crossover" codes thus highly overlap with their base elements, allowing fast
recovery of both elements and relations, and decoding by greedy
reconstruction. Further, they evenly distribute information and exhibit
object-complexity-invariant statistics, ideal for robust intelligent systems.
We describe crossover for sequences first, then generalize to binding and
trees.

##  2 Coding scheme

Let $X$ be a vector of $N$ components, each of which can take any of $Z$
states: $x_{j}\in G\equiv\\{1,...,Z\\}$; and let $d(X,X^{\prime})$ be the
Hamming distance from $X$ to $X^{\prime}$. For a symbol sequence $Y\equiv
Y_{1:L}\equiv(y_{1},...,y_{L})$, where $y_{t}\in D\equiv\\{1,...,M\\}$, a
dictionary of $M$ symbols, we map $Y$ to $X^{Y}$ as follows:

We first sample a codebook $C\equiv\\{X^{1},...,X^{M},X^{*}\\}$, where $X^{*}$
is a "start code", and $x_{j}$ are i.i.d. across all components and symbols
and sampled uniformly from $G$. Next, we sample a mask function $\mu$, an
$N\times Z^{2N}$ matrix with i.i.d. real-valued elements from
$\textrm{Uniform}(0,1)$, referenced as $\mu_{j}(X,X^{\prime})$. In practice,
columns of $\mu$ can be sampled "as needed" using a pseudorandom number
generator.

Using $C$ and $\mu$ we encode sequences as shown in Algorithm 1 and Figure 1a:
starting with $X^{*}$, we sequentially "weave" in symbol codes $X^{y_{1}}$,
.., $X^{y_{L}}$ via an operation "CrossoverSeq": for the $t$’th element we
mask out $1/(t+1)^{\gamma}$ of the evolving code’s components and replace them
with those from $X^{y_{t}}$. The mask selects components where
$\mu_{j}(X^{Y_{1:t-1}},X^{y_{t}})<1/(t+1)^{\gamma}$, so is unique for all
$(X^{Y_{1:t-1}},X^{y_{t}})$, yielding context-dependent mixing. $\gamma\geq 1$
prevents decay of early symbols in $X^{Y}$.

Algorithm 1 Sequence Encoding

function CrossoverSeq($X,X^{\prime};t$) $\rightarrow X^{\prime\prime}$

$mask\leftarrow(\mu_{:}(X,X^{\prime})<1/(t+1)^{\gamma})\quad$ # context-
dependent mask with about $1/(t+1)^{\gamma}$ 1’s

$X^{\prime\prime}\leftarrow X$

$X^{\prime\prime}[mask]\leftarrow X^{\prime}[mask]\quad$ # replace $X$’s
masked components with those from $X^{\prime}$

function EncodeSequence($Y$) $\rightarrow X^{Y}$

$X^{Y}\leftarrow X^{*}$

for $t\in 1,...,|Y|$ do

$X^{Y}\leftarrow\textrm{CrossoverSeq}(X^{Y},X^{y_{t}},t)$

Figure 1: Sequence encoding via crossover ($N=1024,Z=8,M=26,\gamma=1$). (a)
Example encoding of CAFE; colors are states; inscribed symbols are visual
aids, not used by the algorithm. (b) Sequence-symbol code distances. (c) State
distributions for example short and long sequence for one $C,\mu$ sample. (d,
e) Distances of CAFE’s and CICADA’s code to other sequence codes. (f) Decoding
vs code corruption. All plots here/elsewhere were made via 100 $C,\mu$
samples. "x"s denote exact calculations and bars average simulation results.
"*" prefixes distinguish sequences from symbols.

For large $Z$ and $\gamma=1$, mean similarity ($1-d$) of symbol code $X^{i}$
to the final sequence code $X^{Y}$ scales with $i$’s count within the
sequence, $n^{i}$ (Figure 1b), with variance $\sim 1/N$. Precisely,
$d(X^{Y},X^{i})\sim\textrm{Binomial}(N,1-q)/N$, with $q\equiv
P(x^{Y}_{j}=x^{i}_{j})=n^{i}/(L+1)+(1/Z)(L+1-n^{i})/(L+1)$. As exemplified by
Figure 1c, crossover code component distributions are uniform and i.i.d. for a
given $Y$, and invariant to sequence statistics (e.g. length); this results
from the i.i.d. nature of $C,\mu$ and the interchangeability of component
states, suggesting crossover as a robust, scale-invariant encoding.

For two sequences $Y$ and $Y^{\prime}$ sharing their first $t$ symbols,
$d(X^{Y},X^{Y^{\prime}})$ is also a scaled Binomial variable, and $q$ can be
computed exactly for arbitrary $\gamma$; we present the $\gamma=1$ case here.
Let $\mathbf{n}_{u}$ be the length-$M$ symbol count vector for
$Y_{1:t}=Y^{\prime}_{1:t}$ with $\mathbf{1}^{T}\mathbf{n}_{u}=t$, and
$\mathbf{n}_{v}$ and $\mathbf{n}_{v^{\prime}}$ be the symbol count vectors for
$Y_{t+1:L}$ and $Y^{\prime}_{t+1:L^{\prime}}$, respectively, with
$\mathbf{1}^{T}\mathbf{n}_{v}=L-t$ and
$\mathbf{1}^{T}\mathbf{n}_{v^{\prime}}=L^{\prime}-t$. Then:

$q\equiv
P(x_{j}^{Y}=x_{j}^{Y^{\prime}})=\frac{t+1}{L+1}\frac{t+1}{L^{\prime}+1}+\frac{1}{L+1}\frac{1}{L^{\prime}+1}\left[\mathbf{n}^{T}_{v}\mathbf{n}_{v^{\prime}}+\left((L-t)(L^{\prime}-t)-\mathbf{n}^{T}_{v}\mathbf{n}_{v^{\prime}}\right)\frac{1}{Z}\right]$
$+\frac{1}{L+1}\frac{1}{L^{\prime}+1}\left[\mathbf{n}^{T}_{u}(\mathbf{n}_{v}+\mathbf{n}_{v^{\prime}})+\left((t+1)(L^{\prime}+L-2t)-\mathbf{n}^{T}_{u}(\mathbf{n}_{v}+\mathbf{n}_{v^{\prime}})\right)\frac{1}{Z}\right]$

For most $Y$, $X^{Y}$ overlaps little with codes for $Y$’s anagrams, and more
with correct than incorrect starting subsequences, e.g. CI’s and CIC’s codes
are closer than CD’s and CIA’s codes, respectively, to CICADA’s code (Figure
1d,e). This is because different next-symbols yield different $\mu$, which
quickly decreases overlap with $X^{Y}$ for sequence codes with out-of-order
symbols. Consequently, $Y$ can be "greedily" decoded by rebuilding $X^{Y}$
from $X^{*}$, outputting at the $t$-th rebuild step the symbol $i$ that
maximizes overlap with $X^{Y}$ when $X^{i}$ is woven into the current code,
then weaving in $X^{i}$ and advancing to $t+1$. Decoding is robust to noise
added to $X^{Y}$, and when a prior $P(Y)$ exists, the mutual information
between $x_{j}^{Y}$ and $Y$ is i.i.d. across $j$; robustness is thus
equivalent for random and targeted attacks, with decoding accuracy depending
only on the number of corrupted $x_{j}^{Y}$ (Figure 1f).

While crossover intrinsically supports sequences with repeated symbols (either
consecutive or not), for $Y$ with many symbol repeats distinct from $y_{1}$
(e.g. REFEREE), $X^{*}$ crossed over with $X^{y_{1}}$ can be further from
$X^{Y}$ than $X^{*}$ crossed with the repeated symbol, impairing decoding.
Making $\gamma>1$ fixes this by more heavily weighting early symbols (Figure
2a). Surprisingly, while this front-loaded weighting improves decoding of,
say, ABBBBBB, it does not equivalently degrade decoding of AAAAAAB, and
optimal $\gamma$ are shared by many sequences (Figure 2b). In general,
decoding accuracy decreases (increases) with $L$ ($N$), since
$\textrm{Var}[P(x_{j}^{Y_{1:t}}=x_{j}^{Y})]\sim 1/N$. Decoding accuracy is
also robust to large $M$, the dictionary size, due at heart to the low
expected overlap of HD random vectors.

Figure 2: Crossover modifications ($N=1024,Z=8,M=26$). (a) Distance of
*REFEREE to symbols/sequences for two $\gamma$. (b) Decoding vs. $\gamma$ for
several sequences. (c) Decoding of *CAFE vs number of corrupted components at
each encoding step for i.i.d. vs correlated $\mu$. (d) Decoding of *CICADA for
i.i.d. $\mu$, correlated $\mu$, and correlated $\mu$ with quadrupled $N$.

While crossover with i.i.d. $\mu$ is robust to noise added to the final code
(Figure 1f), it fails when noise is added during encoding (Figure 2c,d), as
one altered component yields an entirely different mask. This is fixed by
introducing correlations into $\mu_{j}(X,X^{\prime})$ (i.e. making $\mu$ a
smooth function of $X,X^{\prime}$ [see Appendix C]). The cost of this is
decreased decoding accuracy for certain sequences, since correlated are less
distinct than i.i.d. masks, but this can be corrected by increasing $N$
(Figure 2c,d).

Beyond sequences, crossover naturally generalizes to k-ary trees. Key to
encoding trees is binding elements into groups that can themselves be bound,
yet without forgetting initial group identities: ((A,B), (C,D)) must be
encoded differently from ((A,D), (C,B)). In crossover, $k$ elements
$i_{1},...,i_{k}$ can be bound into a group using a context-dependent mask
function $\mu_{j}(X^{i_{1}},...,X^{i_{k}})$ (which can optionally commute).
The vector for the group takes components from $X^{i_{1}}$ where $0<\mu<1/k$,
from $X^{i_{2}}$ where $1/k<\mu<2/k$, etc. This can then be bound itself in
the exact same manner (Figure 3a), allowing recursive encoding of an arbitrary
tree. The result is a vector overlapping more with elements in vs not in the
tree, and with groups in vs not in the tree, even if the latter contain the
same base elements (Figure 3b). A generic tree encoding will also tend to
overlap more with its included sub-trees than with alternative sub-trees of
equal complexity. Similar to sequence encoding, this means both base elements
and their recursive relations can be extracted via their overlap with the
final code, and that decoding of the full tree can occur through recursive but
greedy reconstruction.

Figure 3: Tree/binding encoding via crossover ($N=1024,Z=8,M=26$). (a) Example
crossover encoding of ((A,B), (C,D), (E,F)). (b) Distances of final code to
element and pair/group codes.

##  3 Discussion

While intelligent systems must typically undergo at least some amount of
training to function, it can be useful for certain computational features to
be built in [17]. Flexible compositional coding is of particular relevance as
it provides a substrate for computing with novel objects or events if they are
made from familiar elements: an autonomous vehicle should be able to
manipulate a representation of "child on scooter behind car in front of bus",
even if previously it had only worked with the isolated scene elements. While
many trained systems, e.g. translation networks [3, 4, 5], have some implicit
capacity for compositional encoding (otherwise outputs would be disordered),
it is unclear how they could handle complexity beyond their training data, and
understanding their internal representations can be challenging [6], although
exciting progress is being made in interpretability [18, 19]. Alternatively,
one can design HDC algorithms with a priori flexibility, then attach or embed
them in trainable systems. Basing training on convolutional binding, for
instance, allowed an artificial network to efficiently and scalably learn
knowledge graphs and out-perform state-of-the-art methods at link prediction
[20]. It stands to reason that identifying robust HDC codes could prove useful
to improving artificial systems, and potentially guiding investigation of
neural computation in biology.

"Crossover" shares advantages with existing HDC schemes but is distinct in key
ways also. As in other schemes [8], crossover preserves recoverable relational
information, and relation codes can be reused as elements, allowing
arbitrarily deep composition. For instance, in crossover one can add CAFE’s or
other words’ codes to the dictionary (perhaps with minor noise added),
enabling encoding of long sequences made from short ones. To encode relations,
previous schemes have used circular convolution [7], XOR (for binary vectors)
[21], permutation [14, 13], or matrix multiplication [15], which yield
relation codes that little overlap their elements. While these distinguish
different compositions of the same elements and allow cue-based recall, base
elements cannot be read out directly from their overlap with the relation
code, and the entire dictionary must be used (instead of just the relevant
symbols) when reading out relations, potentially greatly slowing decoding for
large $M$. An exception is "context-dependent thinning" (CDT), which stores
relations via the union of the elements, then "stamps" the code with a
context-dependent set of zeros [16]; while the stamp shape retains relational
information without erasing element overlaps, however, information beneath its
imprint is discarded, and it is not clear how CDT could construct recursive
sequence codes without early elements decaying exponentially. Crossover
overcomes these limitations, as both elements and their relations can be read
out directly, and in sequences no element overlaps decay exponentially.
Further, crossover yields i.i.d. information across code components, and code
statistics are invariant to object complexity, suggesting it may be a useful
representation for a robust intelligent system.

Crossover is also conceptually distinct from its predecessors since one need
not define arithmetical operations over code components. Whereas previous HDC
algorithms require summing components, either directly or through convolution
[7, 13, 14, 15, 16, 21], crossover’s component states $1,...,Z$ are just
labels, with no numeric value; they need only a comparison operation.
Crossover thus outlines a distributed computation substrate that can exist
outside vector spaces, and instead within more generic metric spaces. This is
relevant to biological implementation, as it allows one to envision $x_{j}$
not only as firing rates of neurons or populations, but also as neural
assembly states that might not make sense to add, multiply, or rank. For
instance, each component of a crossover code could correspond to the attractor
state of a small Hopfield-like assembly [22], with the collective state of a
pool of $N$ such assemblies encoding a complex data object. This could serve,
e.g., as a crude implementation of a combinatorially expressive working memory
substrate, yet with sufficient code-overlap statistics to be usefully read out
and manipulated by further downstream and recurrent computations.

#### Acknowledgments

I would like to thank Taliesin Beynon for many helpful suggestions in
contextualizing this work within the broader scope of high-dimensional
computing and vector symbolic architectures.

## References

  * [1] Geoffrey E Hinton, James L McClelland, David E Rumelhart, et al.  Distributed representations.  Carnegie-Mellon University Pittsburgh, PA, 1984.
  * [2] Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg S Corrado, and Jeff Dean.  Distributed representations of words and phrases and their compositionality.  In Advances in neural information processing systems, pages 3111–3119, 2013.
  * [3] Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio.  Neural machine translation by jointly learning to align and translate.  arXiv preprint arXiv:1409.0473, 2014.
  * [4] Minh-Thang Luong, Hieu Pham, and Christopher D Manning.  Effective approaches to attention-based neural machine translation.  arXiv preprint arXiv:1508.04025, 2015.
  * [5] Yonghui Wu, Mike Schuster, Zhifeng Chen, Quoc V Le, Mohammad Norouzi, Wolfgang Macherey, Maxim Krikun, Yuan Cao, Qin Gao, Klaus Macherey, et al.  Google’s neural machine translation system: Bridging the gap between human and machine translation.  arXiv preprint arXiv:1609.08144, 2016.
  * [6] Zachary C Lipton.  The mythos of model interpretability.  arXiv preprint arXiv:1606.03490, 2016.
  * [7] Tony A Plate.  Holographic reduced representations.  IEEE Transactions on Neural networks, 6(3):623–641, 1995.
  * [8] Pentti Kanerva.  Hyperdimensional computing: An introduction to computing in distributed representation with high-dimensional random vectors.  Cognitive computation, 1(2):139–159, 2009.
  * [9] Ross W Gayler.  Vector symbolic architectures answer jackendoff’s challenges for cognitive neuroscience.  arXiv preprint cs/0412059, 2004.
  * [10] Burton H Bloom.  Space/time trade-offs in hash coding with allowable errors.  Communications of the ACM, 13(7):422–426, 1970.
  * [11] James A Anderson.  A theory for the recognition of items from short memorized lists.  Psychological Review, 80(6):417, 1973.
  * [12] Tony A Plate.  Distributed representations and nested compositional structure.  University of Toronto, Department of Computer Science, 1994.
  * [13] Ross W Gayler.  Multiplicative binding, representation operators & analogy (workshop poster).  1998\.
  * [14] Magnus Sahlgren, Anders Holst, and Pentti Kanerva.  Permutations as a means to encode order in word space.  2008\.
  * [15] Jan Gosmann and Chris Eliasmith.  Vector-derived transformation binding: An improved binding operation for deep symbol-like processing in neural networks.  Neural computation, 31(5):849–869, 2019.
  * [16] Dmitri A Rachkovskij and Ernst M Kussul.  Binding and normalization of binary sparse distributed representations by context-dependent thinning.  Neural Computation, 13(2):411–452, 2001.
  * [17] Anthony M Zador.  A critique of pure learning and what artificial neural networks can learn from animal brains.  Nature communications, 10(1):1–7, 2019.
  * [18] Matthew D Zeiler and Rob Fergus.  Visualizing and understanding convolutional networks.  In European conference on computer vision, pages 818–833. Springer, 2014.
  * [19] Grégoire Montavon, Wojciech Samek, and Klaus-Robert Müller.  Methods for interpreting and understanding deep neural networks.  Digital Signal Processing, 73:1–15, 2018.
  * [20] Maximilian Nickel, Lorenzo Rosasco, and Tomaso Poggio.  Holographic embeddings of knowledge graphs.  In Thirtieth Aaai conference on artificial intelligence, 2016.
  * [21] Pentti Kanerva.  The spatter code for encoding concepts at many levels.  In International Conference on Artificial Neural Networks, pages 226–229. Springer, 1994.
  * [22] John J Hopfield.  Neural networks and physical systems with emergent collective computational abilities.  Proceedings of the national academy of sciences, 79(8):2554–2558, 1982.

##  Appendix A Properties of crossover codes

###  A.1 Proof that sequence codes have i.i.d. components

Denoting $Y_{1:t}\equiv(y_{1},...,y_{t})$ with $Y_{1:L}=Y$, and
$C_{j}\equiv(x^{1}_{j},...,x^{M}_{j},x^{*}_{j})$, we show that
$x_{j}^{Y_{1:t}}$ are independent across $j$ for all $t$.

We will use the fact that if $A_{1},...,A_{N}$ are independent, then so are
$f(A_{1}),...,f(A_{N})$. In particular, define
$\xi^{t}_{j}\equiv\\{x_{j}^{Y_{1:t-1}},...,x_{j}^{Y_{1:0}},C_{j},\mu(j,X^{*},X^{y_{1}}),\mu(j,X^{Y_{1:1}},X^{y_{2}}),...,\mu(j,X^{Y_{1:t-1}},X^{y_{t}})\\}$.
Then $x_{j}^{Y_{1:t}}$ is a strict function of $\xi^{t}_{j}$ so it suffices to
show $\xi^{t}_{j}$ are independent across $j$ for all $t$.

We proceed by induction:

Base case:
$\xi^{1}_{j}=\\{x^{Y_{1:0}}_{j},C_{j},\mu(j,X^{Y_{1:0}},X^{y_{1}})\\}=\\{x^{*}_{j},C_{j},\mu(j,X^{*},X^{y_{1}})\\}$,
which are all i.i.d., so $\xi^{1}_{j}$ are independent across $j$.

Inductive step: If $\xi^{t}_{j}$ are independent across $j$ then so are
$\\{x_{j}^{Y_{1:t}}\\}\cup\xi^{t}_{j}$, since this is a deterministic function
of $\xi^{t}_{j}$. Further,
$\\{x_{j}^{Y_{1:t}}\\}\cup\xi^{t}_{j}\cup\\{\mu(j,X^{Y_{1:t}},X^{y_{t+1}})\\}$
must also be independent across $j$. To see this, consider the following two
cases.

First, most likely is that $\mu(j,X^{Y_{1:t}},X^{y_{t+1}})$ has never been
used in the construction of $X^{Y_{1:t-1}}$, so it is independent from
$\\{x_{j}^{Y_{1:t}}\\}\cup\xi^{t}_{j}$ while also independent across $j$.
Therefore, their union is independent across $j$.

In the second, less likely case, $\mu(j,X^{Y_{1:t}},X^{y_{t+1}})$ was used to
construct $X^{Y_{1:t-1}}$ at some point in the past, i.e.
$(X^{Y_{1:t}},X^{y_{t+1}})=(X^{Y_{1:t^{\prime}}},X^{y_{t^{\prime}+1}})$ for
some $t^{\prime}<t$. In this case, however, the term
$\mu(j,X^{Y_{1:t}},X^{y_{t+1}})=\mu(j,X^{Y_{1:t^{\prime}}},X^{y_{t^{\prime}+1}})$
is already included in $\xi^{t}_{j}$, and so the independence across $j$ is
not affected because no new random variables are added. Thus,
$\\{x_{j}^{Y_{1:t}}\\}\cup\xi^{t}_{j}\cup\\{\mu(j,X^{Y_{1:t}},X^{y_{t+1}})\\}$
is independent across $j$.

Since
$\\{x_{j}^{Y_{1:t}}\\}\cup\xi^{t}_{j}\cup\\{\mu(j,X^{Y_{1:t}},X^{y_{t+1}})\\}=\xi^{t+1}_{j}$,
we have that $\xi^{t}_{j}$ being independent across $j$ implies that
$\xi^{t+1}_{j}$ is independent across $j$, completing the inductive step.

Therefore $x_{j}^{Y_{1:t}}$ is independent across $j$ for all $t$, in other
words $P(X^{Y}|Y)=\prod\limits_{j=1}^{N}P(x^{Y}_{j}|Y)$.

The equality $P(x^{Y}_{j}|Y)=P(x^{Y}_{j^{\prime}}|Y)\quad\forall j,j^{\prime}$
arises because no component is treated differently from any other in our
algorithm, so symmetry implies they can have no statistical differences.

###  A.2 Proof that component distributions are uniform over component states

$P(x^{Y}_{j}=g|Y)=P(x^{Y}_{j}=g^{\prime}|Y)$ for $g\neq g^{\prime}$ arises
because all $g$ in our model are treated identically, so symmetry implies any
functions of them can have no statistical differences. Since these must add to
$1$ when summed over $g\in G$, and $|G|=Z$, we must also have
$P(x^{Y}_{j}=g|Y)=1/Z.$

This also implies that the marginal statistics of crossover codes do not
depend on $Y$ or any feature of $Y$ e.g. sequence length. This distinguishes
crossover, for instance, from representations that would grow denser or
sparser with the length of the sequence they represent.

###  A.3 Proof that sequence information is i.i.d. across components

Given $C$, $\mu$, and a prior distribution over sequences $P_{Y}(Y)$ with
entropy $H[Y]$ over $N_{Y}$ different sequences in total, define the
information $I_{j}|C,\mu$ in component $j$ as the mutual information between
$Y$ and $x_{j}$, i.e.

$I_{j}|C,\mu\equiv MI[Y|x_{j};C,\mu]=H[Y]-H[Y|x_{j};C,\mu]=$
$H[Y]-\sum_{g}H[Y|x_{j}=g;C,\mu]P_{Y}(x_{j}=g|C,\mu).$

The components for one sequence $Y$ are i.i.d. Therefore, while the
$x^{Y}_{j}$ and $x^{Y^{\prime}}_{j}$ might be dependent (e.g. if $Y$ and
$Y^{\prime}$ are similar), there can be no dependencies between $x^{Y}_{j}$
and $x^{Y^{\prime}}_{j^{\prime}}$ for $j\neq j^{\prime}$. Therefore
$\\{x^{Y_{1}}_{j},...,x^{Y_{N_{Y}}}_{j}\\}$ is independent across $j$. Since
$I_{j}$ is a deterministic function of
$\\{x^{Y_{1}}_{j},...,x^{Y_{N_{Y}}}_{j}\\}$ (quantifying how many possible
sequences get eliminated upon knowing the value of $x^{Y}_{j}$), $I_{j}$ is
independent across $j$ also. Since no $j$ is treated specially in our
algorithm, $I_{j}$ must also be identically distributed, so given an initial
prior over sequences to encode $P_{Y}(Y)$, $I_{j}$ is i.i.d.

##  Appendix B Code overlap derivations for symbols and sequences

Since $x^{Y}_{j}$ are i.i.d., the similarity, or overlap, between two sequence
codes (1 minus the Hamming distance)
$s(X^{Y},X^{Y^{\prime}})\sim\frac{1}{N}\textrm{Bi}(N,q)$, where
$\textrm{Bi}(N,q)$ is a binomial distribution with success probability
$q=P(x^{Y}_{j}=x^{Y^{\prime}}_{j})$. The randomness giving rise to the
distribution is over samples of $C$ and $\mu$. Thus,
$\textrm{E}[s(X^{Y},X^{Y^{\prime}})]=q$ and
$\textrm{Var}[s(X^{Y},X^{Y^{\prime}})]=q(1-q)/N$, and it suffices to only
compute $q$. Similar results hold for the similarity of a sequence and symbol
code, $s(X^{Y},X^{i})$. For conciseness, we drop the $j$ and write $x\equiv
x_{j}$ from now on.

Our goal is to compute $q$ for an arbitrary sequence $Y$ and symbol $i$ and
for two arbitrary sequences $Y$ and $Y^{\prime}$, since this gives us the full
distribution of similarity values over samples of $C$ and $\mu$.

###  B.1 Useful quantities

We first compute a few quantities to keep calculations more concise.

1\. $f^{\gamma,L}_{t}\equiv P(x^{Y}\leftarrow y_{t})$ is the probability that
$x^{Y}$ was taken from the $t$-th element of $Y$. This is $1/(t+1)^{\gamma}$
times the probability the component was not overwritten between $t+1$ and $L$
(including occasions where it was overwritten by the same state). We then
have:

$f^{\gamma,L}_{t}\equiv P(x^{Y}\leftarrow
y_{t})=\frac{1}{(t+1)^{\gamma}}\prod\limits_{t^{\prime}=t+1}^{L}\left(1-\frac{1}{(t^{\prime}+1)^{\gamma}}\right).$

Note that this is not a function of $x^{Y}$. Also note that
$f^{1,L}_{t}=1/(L+1)$, which is independent of $t$.

2\. $P(x^{Y}\leftarrow i)$ is the probability that $x^{Y}$ was taken from
symbol $i$, which will depend on how many times $i$ was present in $Y$. We
compute this by summing the probabilities of all ways this could have
occurred.

Suppose $y_{t}=i$ for $t_{1}<...<t_{n^{i}}$, with $\sum_{i}n^{i}=L$. We can
divide the combinatorial ways $x^{Y}$ could have been taken from $i$ into
$n^{i}$ cases. First, $x^{Y}$ could have been taken from $y_{t_{1}}$ then
never overwritten, whose probability is $f^{\gamma,L}_{t_{1}}$. Next, it could
have been taken from $y_{t_{2}}$ then never overwritten (regardless of whether
it was taken from $y_{t_{1}}$), whose probability is $f^{\gamma,L}_{t_{2}}$.
And so forth until $t_{n^{i}}$. These $n^{i}$ cases are mutually non-
overlapping and cover all possible ways that $x^{Y}$ could have been taken
from $i$. Thus

$P(x^{Y}\leftarrow i)=f^{\gamma,L}_{t_{1}}+...+f^{\gamma,L}_{t_{n^{i}}}$

.

When $\gamma=1$, $P(x^{Y}\leftarrow i)=n^{i}/(L+1)$.

3\. $P(x^{Y}\leftarrow Y_{1:t})$ is the probability that $x^{Y}$ was not
overwritten from $t+1$ to $L$. This is just

$P(x^{Y}\leftarrow
Y_{1:t})=\prod\limits_{t^{\prime}=t+1}^{L}\left(1-\frac{1}{(t^{\prime}+1)^{\gamma}}\right)=(t+1)^{\gamma}f^{\gamma,L}_{t}.$

When $\gamma=1$, $P(x^{Y}\leftarrow Y_{1:t})=(t+1)/(L+1)$.

4\. $P(x^{Y}\leftarrow i|x^{Y}\not\leftarrow Y_{1:t})$ is the probability that
$x^{Y}$ came from $i$ given that it did not come from $Y_{1:t}$ (i.e. given
that it was overwritten at some point from $t+1$ to $L$). Suppose $y_{s}=i$
for $t<s_{1}<...<s_{n^{i}_{v}}$ where $n^{i}_{v}$ is the number of times
symbol $i$ appears in $Y_{t+1:L}\equiv(y_{t+1},...,y_{L})$, with
$\sum\limits_{i}n^{i}_{v}=L-t$.

We compute $P(x^{Y}\leftarrow i|x^{Y}\not\leftarrow Y_{1:t})$ by summing over
the probabilities of all the ways this could have occurred. Similar to the
calculation for $P(x^{Y}\leftarrow i)$, we have

$P(x^{Y}\leftarrow i|x^{Y}\not\leftarrow Y_{1:t})=P(x^{Y}\leftarrow
y_{s_{1}}|x^{Y}\not\leftarrow Y_{1:t})+...+P(x^{Y}\leftarrow
y_{s_{n^{i}_{v}}}|x^{Y}\not\leftarrow Y_{1:t}).$

By Bayes’ Rule:

$P(x^{Y}\leftarrow y_{s_{k}}|x^{Y}\not\leftarrow
Y_{1:t})=\frac{P(x^{Y}\not\leftarrow Y_{1:t}|x^{Y}\leftarrow
y_{s_{k}})P(x^{Y}\leftarrow y_{s_{k}})}{P(x^{Y}\not\leftarrow
Y_{1:t})}=\frac{P(x^{Y}\leftarrow y_{s_{k}})}{P(x^{Y}\not\leftarrow Y_{1:t})}$

since if $x^{Y}$ came from $y_{s_{k}}$, which is in the part of $Y$ after $t$,
then $x^{Y}$ could have not have come from $Y_{1:t}$. We have already computed
the numerator and denominator (which is just $1-P(x^{Y}\leftarrow Y_{1:t}))$,
so

$P(x^{Y}\leftarrow i|x^{Y}\not\leftarrow
Y_{1:t})=\frac{1}{P(x^{Y}\not\leftarrow
Y_{1:t})}\left(f^{\gamma,L}_{s_{1}}+...+f^{\gamma,L}_{s_{n^{i}_{v}}}\right).$

When $\gamma=1$ this reduces to $P(x^{Y}\leftarrow i|x^{Y}\not\leftarrow
Y_{1:t})=n^{i}_{v}/(L-t)$, i.e. it is proportional to how many times $i$
appears in the second part of the sequence $Y_{t+1:L}$.

We now calculate how similar a sequence code is to any symbol code, as well as
to other sequence codes.

###  B.2 Similarity between symbol and sequence codes

$P(x^{Y}=x^{i})=P(x^{Y}\leftarrow i)P(x^{Y}=x^{i}|x^{Y}\leftarrow
i)+P(x^{Y}\not\leftarrow i)P(x^{Y}=x^{i}|x^{Y}\not\leftarrow i)$
$=P(x^{Y}\leftarrow i)+P(x^{Y}\not\leftarrow i)\frac{1}{Z}$

$=\sum\limits_{t\in(t_{1},...,t_{n^{i}})}f^{\gamma,L}_{t}+\left(1-\sum\limits_{t\in(t_{1},...,t_{n^{i}})}f^{\gamma,L}_{t}\right)\frac{1}{Z}=\sum\limits_{t\in(t_{1},...,t_{n^{i}})}\left(1-\frac{1}{Z}\right)f^{\gamma,L}_{t}+\frac{1}{Z}$

When $\gamma=1$, $f_{t}^{1,L}=1/(L+1)$ so $P(x^{Y}=x_{i})$ simplifies to
$n^{i}/(L+1)+(1/Z)(L+1-n^{i})/(L+1)$, which tends to $n^{i}/(L+1)$ for large
$Z$.

###  B.3 Similarity between codes for two sequences

Let $u^{i}$ index the times $i$ appears in $Y_{1:t}$, $v^{i}$ the times $i$
appears in $Y_{t+1:L}$, and $(v^{\prime})^{i}$ the times $i$ appears in
$Y^{\prime}_{t+1:L^{\prime}}$. Let $n^{i}_{u}$ count how many times $i$
appears in $Y_{1:t}$, $n^{i}_{v}$ the number of times $i$ appears in
$Y_{t+1:L}$, and $n^{i}_{v^{\prime}}$ the number of times $i$ appears in
$Y^{\prime}_{t+1:L^{\prime}}$. We also write these in vector format as
$\mathbf{n}_{u}$, $\mathbf{n}_{v}$, and $\mathbf{n}_{v^{\prime}}$,
respectively, where $\mathbf{n}_{u}$, $\mathbf{n}_{v}$, and
$\mathbf{n}_{v^{\prime}}$ are length-$M$ vectors, with one component per
symbol in the dictionary $D$.

Since $Y_{1:t}=Y^{\prime}_{1:t}$, first note that
$X^{Y_{1:t}}=X^{Y^{\prime}_{1:t}}$, so $x^{Y_{1:t}}=x^{Y^{\prime}_{1:t}}$. We
wish to find $P(x^{Y}=x^{Y^{\prime}})$.

The event $x^{Y}=x^{Y^{\prime}}$ can occur in 4 distinct ways, whose
probabilities sum to $P(x^{Y}=x^{Y^{\prime}})$. At present we assume a
negligible chance two sequence or symbol codes are exactly identical.

Case 1: $(x^{Y}\leftarrow Y_{1:t})\land(x^{Y^{\prime}}\leftarrow
Y^{\prime}_{1:t})$, i.e. neither $x$ is overwritten at $t+1$ or later. These
events are independent, so

$P(\textrm{Case 1})=P(x^{Y}\leftarrow Y_{1:t})P(x^{Y^{\prime}}\leftarrow
Y^{\prime}_{1:t})=(t+1)^{\gamma}f^{\gamma,L}_{t}(t+1)^{\gamma}f^{\gamma,L^{\prime}}_{t}$

When $\gamma=1$, then:

$P(\textrm{Case 1})=\frac{t+1}{L+1}\frac{t+1}{L^{\prime}+1}$

.

Case 2: $(x^{Y}\not\leftarrow Y_{1:t})\land(x^{Y^{\prime}}\not\leftarrow
Y^{\prime}_{1:t})\land(x^{Y}=x^{Y^{\prime}})$, i.e. $x$ is overwritten in both
sequences at some point between $t+1$ and $L$ or $L^{\prime}$, but by the same
component state. Since the first two conditions are again independent we have

$P(\textrm{Case 2})=P(x^{Y}\not\leftarrow
Y_{1:t})P(x^{Y^{\prime}}\not\leftarrow
Y^{\prime}_{1:t})P(x^{Y}=x^{Y^{\prime}}|x^{Y},x^{Y^{\prime}}\not\leftarrow
Y_{1:t})$

$=[1-(t+1)^{\gamma}f^{\gamma,L}_{t}][1-(t+1)^{\gamma}f^{\gamma,L^{\prime}}_{t}]P(x^{Y}=x^{Y^{\prime}}|x^{Y},x^{Y^{\prime}}\not\leftarrow
Y_{1:t})$

where we recall that $Y_{1:t}=Y^{\prime}_{1:t}$. When $\gamma=1$ this
simplifies to

$P(\textrm{Case
2})=\frac{L-t}{L+1}\frac{L^{\prime}-t}{L^{\prime}+1}P(x^{Y}=x^{Y^{\prime}}|x^{Y},x^{Y^{\prime}}\not\leftarrow
Y_{1:t})$

To find $P(x^{Y}=x^{Y^{\prime}}|x^{Y},x^{Y^{\prime}}\not\leftarrow Y_{1:t})$
we note that if both $x$’s are overwritten, they can end up with the same
component state if (1) $x^{Y}$ and $x^{Y^{\prime}}$ are taken from the same
symbol $i$, whose probability we write as $P(x^{Y},x^{Y^{\prime}}\leftarrow
same|x^{Y},x^{Y^{\prime}}\not\leftarrow Y_{1:t})$ or (2) $x^{Y}$ and
$x^{Y^{\prime}}$ are taken from different symbols but end up with the same
component state by chance. That is,

$P(x^{Y}=x^{Y^{\prime}}|x^{Y},x^{Y^{\prime}}\not\leftarrow X^{Y_{1:t}})=$

$P(x^{Y},x^{Y^{\prime}}\leftarrow same|x^{Y},x^{Y^{\prime}}\not\leftarrow
X^{Y_{1:t}})+[1-P(x^{Y},x^{Y^{\prime}}\leftarrow
same|x^{Y},x^{Y^{\prime}}\not\leftarrow Y_{1:t})]\frac{1}{Z}.$

$P(x^{Y},x^{Y^{\prime}}\leftarrow same|x^{Y},x^{Y^{\prime}}\not\leftarrow
X^{Y_{1:t}})$ is the sum over $i\in\\{1,...,M\\}$ of the probabilities that
both $x^{Y}$ and $x^{Y^{\prime}}$ were taken from $i$. These events are
independent, so:

$P(x^{Y},x^{Y^{\prime}}\leftarrow i|x^{Y},x^{Y^{\prime}}\not\leftarrow
X^{Y_{1:t}})=P(x^{Y}\leftarrow i|x^{Y},x^{Y^{\prime}}\not\leftarrow
X^{Y_{1:t}})P(x^{Y^{\prime}}\leftarrow i|x^{Y},x^{Y^{\prime}}\not\leftarrow
X^{Y_{1:t}})$

$=\frac{\sum\limits_{v^{i}}f_{v^{i}}^{\gamma,L}}{1-(t+1)^{\gamma}f^{\gamma,L}_{t}}\frac{\sum\limits_{(v^{\prime})^{i}}f^{\gamma,L^{\prime}}_{(v^{\prime})^{i}}}{1-(t+1)^{\gamma}f^{\gamma,L^{\prime}}_{t}}.$

When $\gamma=1$, this simplifies to

$\frac{n^{i}_{v}}{L-t}\frac{n^{i}_{v^{\prime}}}{L^{\prime}-t}$

.

Thus

$P(x^{Y},x^{Y^{\prime}}\leftarrow same|x^{Y},x^{Y^{\prime}}\not\leftarrow
X^{Y_{1:t}})=\sum_{i}\frac{\sum\limits_{v^{i}}f^{\gamma,L}_{v^{i}}}{1-(t+1)^{\gamma}f^{\gamma,L}_{t}}\frac{\sum\limits_{(v^{\prime})^{i}}f^{\gamma,L^{\prime}}_{(v^{\prime})^{i}}}{1-(t+1)^{\gamma}f^{\gamma,L^{\prime}}_{t}}.$

When $\gamma=1$ this is

$P(x^{Y},x^{Y^{\prime}}\leftarrow same|x^{Y},x^{Y^{\prime}}\not\leftarrow
X^{Y_{1:t}})=\sum_{i}\frac{n^{i}_{v}n^{i}_{v^{\prime}}}{(L-t)(L^{\prime}-t)}=\frac{\mathbf{n}^{T}_{v}\mathbf{n}_{v^{\prime}}}{(L-t)(L^{\prime}-t)}$

i.e. when $\gamma=1$ the probability that $x^{Y}$ came from the same symbol,
given that it was overwritten in the second part of both sequence
constructions, is just the normalized dot product of the symbol-count vectors
for the second parts of the two sequences.

Thus

$P(x^{Y}=x^{Y^{\prime}}|x^{Y},x^{Y^{\prime}}\not\leftarrow X^{Y_{1:t}})=$

$\sum_{i}\frac{\sum\limits_{v^{i}}f^{\gamma,L}_{v^{i}}}{1-(t+1)^{\gamma}f^{\gamma,L}_{t}}\frac{\sum\limits_{(v^{\prime})^{i}}f^{\gamma,L^{\prime}}_{(v^{\prime})^{i}}}{1-(t+1)^{\gamma}f^{\gamma,L^{\prime}}_{t}}+\left(1-\sum_{i}\frac{\sum\limits_{v^{i}}f^{\gamma,L}_{v^{i}}}{1-(t+1)^{\gamma}f^{\gamma,L}_{t}}\frac{\sum\limits_{(v^{\prime})^{i}}f^{\gamma,L^{\prime}}_{(v^{\prime})^{i}}}{1-(t+1)^{\gamma}f^{\gamma,L^{\prime}}_{t}}\right)\frac{1}{Z}$

When $\gamma=1$

$P(x^{Y}=x^{Y^{\prime}}|x^{Y},x^{Y^{\prime}}\not\leftarrow
X^{Y_{1:t}})=\frac{\mathbf{n}^{T}_{v}\mathbf{n}_{v^{\prime}}}{(L-t)(L^{\prime}-t)}+\left(1-\frac{\mathbf{n}^{T}_{v}\mathbf{n}_{v^{\prime}}}{(L-t)(L^{\prime}-t)}\right)\frac{1}{Z}.$

Thus

$P(\textrm{Case
2})=[1-(t+1)^{\gamma}f^{\gamma,L}_{t}][1-(t+1)^{\gamma}f^{\gamma,L^{\prime}}_{t}]\times$

$\left[\sum_{i}\frac{\sum\limits_{v^{i}}f^{\gamma,L}_{v^{i}}}{1-(t+1)^{\gamma}f^{\gamma,L}_{t}}\frac{\sum\limits_{(v^{\prime})^{i}}f^{\gamma,L^{\prime}}_{(v^{\prime})^{i}}}{1-(t+1)^{\gamma}f^{\gamma,L^{\prime}}_{t}}+\left(1-\sum_{i}\frac{\sum\limits_{v^{i}}f^{\gamma,L}_{v^{i}}}{1-(t+1)^{\gamma}f^{\gamma,L}_{t}}\frac{\sum\limits_{(v^{\prime})^{i}}f^{\gamma,L^{\prime}}_{(v^{\prime})^{i}}}{1-(t+1)^{\gamma}f^{\gamma,L^{\prime}}_{t}}\right)\frac{1}{Z}\right]$

When $\gamma=1$:

$P(\textrm{Case
2})=\frac{L-t}{L+1}\frac{L^{\prime}-t}{L^{\prime}+1}\left[\frac{\mathbf{n}^{T}_{v}\mathbf{n}_{v^{\prime}}}{(L-t)(L^{\prime}-t)}+\left(1-\frac{\mathbf{n}^{T}_{v}\mathbf{n}_{v^{\prime}}}{(L-t)(L^{\prime}-t)}\right)\frac{1}{Z}\right].$

Case 3: $(x^{Y}\leftarrow Y_{1:t})\land(x^{Y^{\prime}}\not\leftarrow
Y^{\prime}_{1:t})\land(x^{Y}=x^{Y^{\prime}})$, i.e. $x$ is untouched in the
first sequence but overwritten in the second, but happens to be overwritten by
$x^{Y_{1:t}}$. Once again the first two events are independent, so

$P(\textrm{Case
3})=(t+1)^{\gamma}f^{\gamma,L}_{t}[1-(t+1)^{\gamma}f^{\gamma,L^{\prime}}_{t}]P(x^{Y}=x^{Y^{\prime}}|x^{Y}\leftarrow
Y_{1:t},x^{Y^{\prime}}\not\leftarrow Y^{\prime}_{1:t}).$

When $\gamma=1$:

$P(\textrm{Case
3})=\frac{t+1}{L+1}\frac{L^{\prime}-t}{L^{\prime}+1}P(x^{Y}=x^{Y^{\prime}}|x^{Y}\leftarrow
Y_{1:t},x^{Y^{\prime}}\not\leftarrow Y^{\prime}_{1:t}).$

By similar reasoning as in Case 2, the event
$(x^{Y}=x^{Y^{\prime}}|x^{Y}\leftarrow
X^{Y_{1:t}},x^{Y^{\prime}}\not\leftarrow X^{Y^{\prime}_{1:t}})$ can occur if
(1) $x^{Y}$ and $x^{Y^{\prime}}$ are taken from the same symbol $i$ or (2)
$x^{Y}$ and $x^{Y^{\prime}}$ are taken from different symbols but end up with
the same component state.

Following similar logic as in Case 2, except swapping $Y^{t+1:L}$ with
$Y^{1:t}$ we thus have

$P(x^{Y}=x^{Y^{\prime}}|x^{Y}\leftarrow Y_{1:t},x^{Y^{\prime}}\not\leftarrow
Y^{\prime}_{1:t})=$

$\left[\sum_{i}\frac{\sum\limits_{u^{i}}f_{u^{i}}^{\gamma,t}\sum\limits_{(v^{\prime})^{i}}f_{(v^{\prime})^{i}}^{\gamma,L^{\prime}}}{1-(t+1)^{\gamma}f^{\gamma,L^{\prime}}_{t}}+\left(1-\sum_{i}\frac{\sum\limits_{u^{i}}f_{u^{i}}^{\gamma,t}\sum\limits_{(v^{\prime})^{i}}f_{(v^{\prime})^{i}}^{\gamma,L^{\prime}}}{1-(t+1)^{\gamma}f^{\gamma,L^{\prime}}_{t}}\right)\frac{1}{Z}\right]$

When $\gamma=1$:

$P(x^{Y}=x^{Y^{\prime}}|x^{Y}\leftarrow Y_{1:t},x^{Y^{\prime}}\not\leftarrow
Y^{\prime}_{1:t})=\frac{\mathbf{n}^{T}_{u}\mathbf{n}_{v^{\prime}}}{(t+1)(L^{\prime}-t)}+\left(1-\frac{\mathbf{n}^{T}_{u}\mathbf{n}_{v^{\prime}}}{(t+1)(L^{\prime}-t)}\right)\frac{1}{Z}$

Thus,

$P(\textrm{Case 3})=$
$(t+1)^{\gamma}f^{\gamma,L}_{t}[1-(t+1)^{\gamma}f^{\gamma,L^{\prime}}_{t}]\times\left[\sum_{i}\frac{\sum\limits_{u^{i}}f_{u^{i}}^{\gamma,t}\sum\limits_{(v^{\prime})^{i}}f_{(v^{\prime})^{i}}^{\gamma,L^{\prime}}}{1-(t+1)^{\gamma}f^{\gamma,L^{\prime}}_{t}}+\left(1-\sum_{i}\frac{\sum\limits_{u^{i}}f_{u^{i}}^{\gamma,t}\sum\limits_{(v^{\prime})^{i}}f_{(v^{\prime})^{i}}^{\gamma,L^{\prime}}}{1-(t+1)^{\gamma}f^{\gamma,L^{\prime}}_{t}}\right)\frac{1}{Z}\right]$

And when $\gamma=1$:

$P(\textrm{Case
3})=\frac{t+1}{L+1}\frac{L^{\prime}-t}{L^{\prime}+1}\left[\frac{\mathbf{n}^{T}_{u}\mathbf{n}_{v^{\prime}}}{(t+1)(L^{\prime}-t)}+\left(1-\frac{\mathbf{n}^{T}_{u}\mathbf{n}_{v^{\prime}}}{(t+1)(L^{\prime}-t)}\right)\frac{1}{Z}\right].$

Case 4: $(x^{Y}\not\leftarrow Y_{1:t})\land(x^{Y^{\prime}}\leftarrow
Y^{\prime}_{1:t})\land(x^{Y}=x^{Y^{\prime}})$, i.e. $x$ is untouched in the
second sequence but overwritten in the first, but happens to be overwritten by
$x^{Y^{\prime}_{1:t}}$. This is symmetric to Case 3, so

$P(\textrm{Case 4})=$
$[1-(t+1)^{\gamma}f^{\gamma,L}_{t}](t+1)^{\gamma}f^{\gamma,L^{\prime}}_{t}\times\left[\sum_{i}\frac{\sum\limits_{v^{i}}f_{v^{i}}^{\gamma,L}\sum\limits_{u^{i}}f_{u^{i}}^{\gamma,t}}{1-(t+1)^{\gamma}f^{\gamma,L}_{t}}+\left(1-\sum_{i}\frac{\sum\limits_{v^{i}}f_{v^{i}}^{\gamma,L}\sum\limits_{u^{i}}f_{u^{i}}^{\gamma,t}}{1-(t+1)^{\gamma}f^{\gamma,L}_{t}}\right)\frac{1}{Z}\right]$

And when $\gamma=1$:

$P(\textrm{Case
4})=\frac{L^{\prime}-t}{L+1}\frac{t+1}{L^{\prime}+1}\left[\frac{\mathbf{n}^{T}_{v}\mathbf{n}_{u}}{(L-t)(t+1)}+\left(1-\frac{\mathbf{n}^{T}_{v}\mathbf{n}_{u}}{(L-t)(t+1)}\right)\frac{1}{Z}\right].$

Sum over cases

$P(x^{Y}=x^{Y^{\prime}})=P(\textrm{Case 1})+P(\textrm{Case 2})+P(\textrm{Case
3})+P(\textrm{Case 4})=$

$(t+1)^{\gamma}f^{\gamma,L}_{t}(t+1)^{\gamma}f^{\gamma,L^{\prime}}_{t}+[1-(t+1)^{\gamma}f^{\gamma,L}_{t}][1-(t+1)^{\gamma}f^{\gamma,L^{\prime}}_{t}]\times$

$\left[\sum_{i}\frac{\sum\limits_{v^{i}}f^{\gamma,L}_{v^{i}}}{1-(t+1)^{\gamma}f^{\gamma,L}_{t}}\frac{\sum\limits_{(v^{\prime})^{i}}f^{\gamma,L^{\prime}}_{(v^{\prime})^{i}}}{1-(t+1)^{\gamma}f^{\gamma,L^{\prime}}_{t}}+\left(1-\sum_{i}\frac{\sum\limits_{v^{i}}f^{\gamma,L}_{v^{i}}}{1-(t+1)^{\gamma}f^{\gamma,L}_{t}}\frac{\sum\limits_{(v^{\prime})^{i}}f^{\gamma,L^{\prime}}_{(v^{\prime})^{i}}}{1-(t+1)^{\gamma}f^{\gamma,L^{\prime}}_{t}}\right)\frac{1}{Z}\right]$

$+(t+1)^{\gamma}f^{\gamma,L}_{t}[1-(t+1)^{\gamma}f^{\gamma,L^{\prime}}_{t}]\times\left[\sum_{i}\frac{\sum\limits_{u^{i}}f_{u^{i}}^{\gamma,t}\sum\limits_{(v^{\prime})^{i}}f_{(v^{\prime})^{i}}^{\gamma,L^{\prime}}}{1-(t+1)^{\gamma}f^{\gamma,L^{\prime}}_{t}}+\left(1-\sum_{i}\frac{\sum\limits_{u^{i}}f_{u^{i}}^{\gamma,t}\sum\limits_{(v^{\prime})^{i}}f_{(v^{\prime})^{i}}^{\gamma,L^{\prime}}}{1-(t+1)^{\gamma}f^{\gamma,L^{\prime}}_{t}}\right)\frac{1}{Z}\right]$

$+[1-(t+1)^{\gamma}f^{\gamma,L}_{t}](t+1)^{\gamma}f^{\gamma,L^{\prime}}_{t}\times\left[\sum_{i}\frac{\sum\limits_{v^{i}}f_{v^{i}}^{\gamma,L}\sum\limits_{u^{i}}f_{u^{i}}^{\gamma,t}}{1-(t+1)^{\gamma}f^{\gamma,L}_{t}}+\left(1-\sum_{i}\frac{\sum\limits_{v^{i}}f_{v^{i}}^{\gamma,L}\sum\limits_{u^{i}}f_{u^{i}}^{\gamma,t}}{1-(t+1)^{\gamma}f^{\gamma,L}_{t}}\right)\frac{1}{Z}\right]$

When $\gamma=1$ this simplifies to

$P(x^{Y}=x^{Y^{\prime}})=\frac{t+1}{L+1}\frac{t+1}{L^{\prime}+1}$

$+\frac{L-t}{L+1}\frac{L^{\prime}-t}{L^{\prime}+1}\left[\frac{\mathbf{n}^{T}_{v}\mathbf{n}_{v^{\prime}}}{(L-t)(L^{\prime}-t)}+\left(1-\frac{\mathbf{n}^{T}_{v}\mathbf{n}_{v^{\prime}}}{(L-t)(L^{\prime}-t)}\right)\frac{1}{Z}\right]$

$+\frac{t+1}{L+1}\frac{L^{\prime}-t}{L^{\prime}+1}\left[\frac{\mathbf{n}^{T}_{u}\mathbf{n}_{v^{\prime}}}{(t+1)(L^{\prime}-t)}+\left(1-\frac{\mathbf{n}^{T}_{u}\mathbf{n}_{v^{\prime}}}{(t+1)(L^{\prime}-t)}\right)\frac{1}{Z}\right]$
$+\frac{L^{\prime}-t}{L+1}\frac{t+1}{L^{\prime}+1}\left[\frac{\mathbf{n}^{T}_{v}\mathbf{n}_{u}}{(L-t)(t+1)}+\left(1-\frac{\mathbf{n}^{T}_{v}\mathbf{n}_{u}}{(L-t)(t+1)}\right)\frac{1}{Z}\right].$

##  Appendix C Correlated mask function construction

We introduced correlations into the mask function $\mu$ (Figure 2d) as
follows. We first created a random, sparse, binary matrix $W$ of size $N\times
2N$ and with density $r$ (0.004 in Fig 2d), and assigned our component states
$1,...,Z$ to evenly spaced angles between $0$ and $2\pi$. The mask value
$\mu_{j}(X,X^{\prime})$ was then determined by (1) multiplying $W$ by the
concatenated $2N$-dimensional vector $[X;X^{\prime}]$, (2) taking the circular
mean $\phi$ of the result, and (3) letting $\mu_{j}(X,X^{\prime})$ be equal to
absolute angular distance between $\phi$ and $\pi$, divided by $\pi$. This led
to mask function values uniformly distributed between $0$ and $1$ yet which
were determined in a smoother way by the values of $X$ and $X^{\prime}$ than
when $\mu$ was sampled i.i.d. Upon quadrupling $N$ (Figure 2d magenta) we
equivalently decreased $r$ by a factor of 4.

##  Appendix D Code

All code used in the preparation of this manuscript was written in the Python
programming language and is available at
https://github.com/rkp8000/crossing_over.