Self-Similar Symbols Sequence Synthesis
Long-memory is a feature of many natural sequences, closely relate to statistical self-similarity. In the past, numerical sequences starting with the size of Nile river floods have been the main topic of study. But there are many domains where there are (hypothesised) long-memory sequences that are non-numerical, symbolic sequences. For instance: human writing, DNA, and so forth.
SymbolicLongMemorySequences.jl is a Julia package for generating Long-Range Dependent (LRD) sequences of non-numerical (categorical/symbolic) data. It provides controllable synthetic sequences for testing LRD estimators, probing information-theoretic quantities, and training or stress-testing sequence models on non-language data with language-like long context.
The package was previously developed as S5.jl. It has been renamed to
SymbolicLongMemorySequences.jl for Julia package registration, where clear
descriptive names are preferred over short acronym-heavy names.
This is an early version. Lots of changes and tests still to come.
SymbolicLongMemorySequences.jl is useful beyond basic generator benchmarking:
-
Estimator testing: generate labelled NN-LRD (NonNumerical LRD) sequences where alphabet, marginal distribution, local structure, and nominal LRD mechanism are known.
-
Information-theoretic experiments: create controlled cases for ideas such as excess entropy rate, entropy-rate convergence, and the gap between local and long-range predictability in LRD processes.
-
Non-language sequence modelling: train or stress-test LLM-style neural sequence models on symbolic data that is not text, such as event logs, vulnerability classes, genomic symbols, workflow traces, or synthetic protocol states.
-
Context-length diagnostics: test whether models exploit genuinely long context rather than only short-range bigram/trigram cues.
-
Anomaly and change-detection studies: create controlled shifts in marginal, local Markov structure, regime persistence, or long-range behaviour.
-
Privacy-preserving simulation: produce synthetic categorical sequences with realistic burstiness without copying a sensitive corpus.
These applications require the abililty to generate
-
very long sequences (million or billions of tokens seems a reasonable starting point); with
-
control over short-term behaviour (marginals) as well as enforcing long-memory.
Long-Range Dependence (LRD) means that the large-scale statistical structure of a sequence is as important as its short-range structure. Formally, a sequence is LRD if its autocovariance function (ACF) decays as a power law,
so that the sum of the tail ACF diverges. LRD is characterised by closely related
parameters: the ACF decay exponent
LRD is ubiquitous in human-generated data (text, Internet traffic, genomics, social
media), yet almost all synthesis tools target numerical data. SymbolicLongMemorySequences.jl fills that gap for
symbol sequences — data that takes values in a finite, unordered alphabet such as
{Orange, Apple, Pear, ...} or {G, A, C, T}.
Methods are broadly classified into property-based and model-based. The former largely aim to synthesize LRD by starting with a numerical sequence with known LRD properties and then crafting a symbolic sequence by transforming the numerical data. The latter start from a model that has properties such as hierarchical structure or power-law distributed times to drive the sequence generation directly.
The model taxonomy is summarized below. MB1 and MB4 are shown as subfamilies because their variants make materially different tradeoffs.
Complexity notation used below:
n: generated sequence length;d: configured history depth or effective memory cutoff;k: alphabet size;I: number of calibration iterations.
Standard cases can be constructed through the uniform factory API:
using SymbolicLongMemorySequences, StableRNGs
alphabet = [:a, :b, :c]
g = make_generator(:PB1, alphabet; H = 0.8, marginal = [0.2, 0.3, 0.5])
seq = generate(g, 10_000; rng = StableRNG(42))
method_ids()
method_info(:PB1).defaults
method_parameters(:PB1)make_generator(id, alphabet; kwargs...) accepts IDs such as :PB1, "MB1c",
or type-name aliases such as :SpectralFGN. It is intended for common starting
points. Use method_parameters(id) to inspect accepted keyword names, defaults,
domains, and short descriptions. The explicit constructors below remain the
full-control API.
These generate one or more underlying numerical LRD processes and then map them
to symbols. In code, this can now be expressed directly as a composition of a
LatentSource and a Symbolizer:
source = SpectralFGNSource(0.8)
symbolizer = QuantileSymbolizer([:a, :b, :c], [0.2, 0.3, 0.5])
g = PropertyBasedGenerator(source, symbolizer)
seq = generate(g, 10_000; rng = StableRNG(42))The named PB methods remain the standard, documented cases. The composable API makes the latent-source/symbolization split explicit, while still checking compatibility at construction time. For example, a quantile symbolizer needs one latent series, an argmax symbolizer needs one latent series per symbol, and an intermittent-map source is currently single-stream only.
For validation and research workflows, property-based generators also expose the numerical process before symbolization:
seq, latent = generate_with_latent(g, 10_000; rng = StableRNG(42))
size(latent) # width × nThis is useful when a symbolic diagnostic looks weak: the latent ACF and spectrum can be checked separately from the quantization, argmax, or Markov-regime transformation.
| Named method | Latent source | Symbolizer |
|---|---|---|
| PB1 | SpectralFGNSource |
QuantileSymbolizer |
| PB2 | SpectralFGNSource |
ArgmaxSymbolizer |
| PB3 | SpectralFGNSource or HaarLRDSource |
MarkovRegimeSymbolizer |
| PB4 | IntermittentMapSource |
QuantileSymbolizer |
The LRD property is inherited from the numerical layer, then altered by the symbolization step. Validation therefore reports the behavior of the full composition, not just the latent process.
| ID | Name | LRD mechanism | Short-range control | Complexity | Novel? |
|---|---|---|---|---|---|
| PB1 | Spectral fGn + quantization | Spectral |
Poor (set by quantization) | No | |
| PB2 | Latent Gaussian categorical (LGCM) | fGn streams + argmax | Via calibrated offsets | No | |
| PB3 | Spectral/wavelet driver + Markov state machine | Latent LRD driver rank-binned into regimes | Markov transition matrices | Partial | |
| PB4 | Intermittent map + quantization | Latent intermittent dynamics | Poor (set by quantization) | No |
PB1 — Spectral fGn + quantization.
Fractional Gaussian noise with Hurst parameter
PB2 — Latent Gaussian categorical model (LGCM).
A vector of
PB3 — Latent LRD driver with a Markov state machine.
A latent long-memory driver controls which Markov regime is active at each step.
Each regime has its own symbol transition matrix, so local bigram structure can be
prescribed while the latent driver injects persistence across scales. The default
driver = :spectral uses approximate spectral fGn synthesis followed by
rank-binning into regimes; driver = :haar retains the original Haar-like cascade
as a comparison path. This is a practical implementation of the wavelet/state-machine
idea in Roughan, Veitch & Abry (2000), with a fully calibrated wavelet variant left
as a research extension.
PB4 — Intermittent map + quantization. A Pomeau-Manneville-style intermittent map generates a latent real-valued driver with long laminar episodes. The driver is rank-binned to symbols, so finite-sample marginal counts are controlled in the same spirit as PB1. This keeps the method in the property-based family: long-range structure lives in a latent dynamical system, not in an explicit symbolic transition rule.
These produce LRD through the stochastic model itself rather than via mapping.
| ID | Name | LRD mechanism | Short-range control | Complexity | Novel? |
|---|---|---|---|---|---|
| MB1a | Linear-Additive Markov Process (LAMP) | Exact power-law history weights | History-weighted transition matrix | No | |
| MB1b | Dyadic-bucket LAMP | Dyadic approximation to power-law history | History-weighted transition matrix | Partial | |
| MB1c | Calibrated additive Markov chain | Centered power-law memory function | Symbol recurrence through additive memory | No | |
| MB2 | Heavy-tailed On/Off doubly-stochastic Markov chain | Pareto regime sojourn times | Per-regime Markov chains | No | |
| MB3 | Fractal Symbol Sequence (FSS) via FRP/FSNP | Fractal point process inter-arrivals | Poor (independent streams) | Yes | |
| MB4a | Normalized Hawkes-style symbolic process | Normalized power-law self/cross-excitation | Excitation matrix | No | |
| MB4b | Self-exciting mass process | Unnormalized power-law self/cross-excitation mass | Target marginal plus excitation matrix | Partial | |
| MB4c | Logit self-exciting mass process | Centered log-contrast of unnormalized power-law mass | Target marginal plus excitation matrix |
|
Yes |
| MB5 | Duplication-mutation growth | Power-law lag copy/mutate growth | Poor (copy structure induced by growth) | No |
MB1a/MB1b/MB1c — Additive history models. Transition probabilities are a weighted sum over transition-matrix rows selected by the observed history,
with weights d exceeds the sequence length, only observed
history contributes and the missing pre-history mass is assigned to the target
marginal. The default transition matrix is identity, recovering copy-from-history
behavior. A simple repeat-biased choice is
lamp_repeat_transition(marginal; repeat_probability), an identity/dyad mixture
whose dyad rows equal the requested marginal. The small innovation term
LAMP is now treated as MB1a, the exact finite-history implementation. It is
useful for testing and moderate sequence lengths, but becomes expensive when
d >= n. DyadicLAMP is MB1b, a scalable approximation that groups history
lags into dyadic age buckets such as 1, 2:3, 4:7, and so on. Each bucket
contributes its total power-law weight times the empirical symbol mix in that age
range. MB1b keeps the same transition-matrix controls while making much larger
effective memory depths feasible.
CalibratedAdditiveMarkov is MB1c, a centered additive Markov-chain memory
function:
with
MB2 — Heavy-tailed On/Off doubly-stochastic Markov chain.
The sequence is generated by a Markov chain that alternates between two or more regimes.
Sojourn times in each regime follow a Pareto distribution with tail index
MB3 — Fractal Symbol Sequence (FSS) via FRP/FSNP.
Each symbol
MB4a/MB4b/MB4c — Hawkes-style self-exciting symbol processes.
HawkesSymbol is retained as MB4a, a normalized discrete-time analogue of
Hawkes-process word-occurrence models. Each symbol has a positive baseline
intensity, and each recent symbol adds a power-law weighted row of an excitation
matrix to the current intensity vector. This follows the self-excitation idea in
Hawkes processes and is motivated by Ogura, Hanada, Amano & Kondo (2022), who
model long-range dynamic correlations of word occurrences in written text with
Hawkes processes. However, MB4a normalizes the memory kernel before the
categorical draw. In validation this can produce local burstiness while leaving a
nearly white centered one-hot spectrum, so MB4a is best treated as a cautionary
baseline.
SelfExcitingMass is MB4b, the recommended replacement. It uses a default
symbol mass in the direction of the requested marginal plus an unnormalized
power-law self-excitation mass. The categorical probabilities are normalized only
after these masses are added. The default mass and smoothing floor keep all
symbols reachable and stabilize startup; the unnormalized history mass lets
self-excitation dominate over long represented scales when the data support it.
This is a discrete-time categorical adaptation of Hawkes-style self-excitation,
not a fitted continuous-time Hawkes process.
LogitSelfExcitingMass is MB4c, an experimental contrast version motivated
by the remaining flat-spectrum behavior of MB4b. It first builds the same kind
of unnormalized power-law mass, then converts the mass vector to centered
log-mass contrasts and samples with weights proportional to
marginal[j] * exp(contrast_strength * contrast[j]). This removes common-mode
growth in the total history mass before the final categorical normalization.
Validation smoke tests show that larger contrast_strength can steepen the
spectrum, but too much contrast causes symbol lock-in and poor marginal control,
so MB4c should currently be treated as a tunable experimental model rather than
as a solved replacement.
For MB4b and MB4c, beta is the asymptotic power-law decay exponent. The offset
c is only a short-lag regularizer: using c = 0 gives the clean discrete-time
kernel lag^(-beta), while positive c softens the first few lags and delays
the apparent power-law onset. The depth d should be read as a computational
truncation of an intended long or infinite memory kernel. In MB4c, d = nothing
uses all previous generated observations, which is conceptually clean but costs
MB5 — Duplication-mutation symbolic growth.
DuplicationMutation starts from an iid seed and grows the sequence by repeatedly
copying from a power-law-distributed previous lag and mutating copied symbols.
The method is motivated by expansion-modification and duplication-mutation models
for DNA-like symbolic sequences; it is a finite copy/mutate simulator, not a
biological genome model. The lag-copy mechanism is deliberate: validation showed
that power-law block lengths with uniformly chosen source blocks mostly created
local patches rather than the intended decaying autocorrelation curve.
All implemented generators accept an explicit ordered alphabet and reject duplicate
alphabet entries. target_marginal(g) reports the marginal distribution the generator
claims to target; empirical_marginal(seq, alphabet) and empirical_bigram(seq, alphabet) provide lightweight checks for simulated data.
| Type | Alphabet | Marginal control | Bigram/trigram control |
|---|---|---|---|
SpectralFGN |
explicit alphabet |
direct marginal; rank binning gives near-exact finite-sample counts |
no direct control |
LGCM |
explicit alphabet |
direct marginal; calibrated latent offsets |
no direct control |
WaveletMarkov |
explicit alphabet |
aggregate stationary marginal implied by regimes | direct per-regime bigram matrices |
IntermittentMapSymbols |
explicit alphabet |
direct marginal; rank binning gives near-exact finite-sample counts |
no direct control |
LAMP |
explicit alphabet |
direct marginal mixed through epsilon; larger epsilon improves marginal control but weakens history dependence |
exact history-weighted transition matrix |
DyadicLAMP |
explicit alphabet |
direct marginal mixed through epsilon; larger epsilon improves marginal control but weakens history dependence |
dyadic-bucket approximation to history-weighted transition matrix |
CalibratedAdditiveMarkov |
explicit alphabet |
centered additive memory around marginal; strength = 0 is iid |
additive memory induces recurrence, not arbitrary bigrams |
OnOffMarkov |
explicit alphabet |
aggregate stationary marginal implied by regimes | direct per-regime bigram matrices |
FSS |
explicit alphabet |
rates / sum(rates) asymptotically |
no direct control |
HawkesSymbol |
explicit alphabet |
baseline distribution reported, but output marginal is implied by excitation and finite history | normalized excitation matrix induces bursty local structure; retained as MB4a |
SelfExcitingMass |
explicit alphabet |
default marginal target, but strong excitation can distort finite-sample marginals |
unnormalized excitation mass induces long-context recurrence; MB4b recommended |
LogitSelfExcitingMass |
explicit alphabet |
default marginal target, but contrast strength can distort finite-sample marginals |
centered log excitation contrasts induce long-context recurrence; MB4c experimental |
DuplicationMutation |
explicit alphabet |
seed/mutation replacement distribution; output marginal is shaped by copied history | copy/mutate growth induces local and long-context structure |
For regime-driven methods (WaveletMarkov and OnOffMarkov), symbol-level ACF
and spectrum diagnostics only see the LRD regime process when regimes have
different observable stationary symbol distributions. Regimes with identical
stationary marginals can carry latent long memory while looking nearly
short-memory to one-hot symbol diagnostics.
Reproducible simulation studies live in validation/. For example:
julia --project=. validation/marginal_control.jl
julia --project=. validation/local_structure.jl
julia --project=. validation/lrd_method_diagnostics.jl
julia --project=validation validation/longmemory_comparison.jlThese studies test controllability of simulated data; LRD-parameter estimation is intended for a future separate estimator package.
The marginal-control validation includes a paper-ready uniform categorical test
with k = 8. For each method it drops the first and last 10% of the generated
sequence, compares the remaining symbol frequencies with the intended uniform
marginal, writes a CSV table of chi-squared diagnostics, and creates a combined
histogram grid under validation/results/marginal_control/. The chi-squared
p-values use the iid multinomial reference distribution, so they are useful
frequency diagnostics rather than exact hypothesis tests for dependent LRD
sequences. In fact, LRD can make empirical marginals converge more slowly than
the iid multinomial model assumes, so the strict chi-squared reference is often
too conservative even though large values remain indicative of a control issue.
The same CSV also reports an approximate effective-sample-size correction:
centered one-hot indicators are used to estimate an integrated autocorrelation
time for each symbol, the smallest symbol ESS is used as a conservative
sequence-level effective_n, and the chi-squared statistic is scaled by
effective_n / trimmed_n. These ESS-adjusted p-values are still diagnostics,
not exact dependent categorical tests, but they are less misleading for strongly
dependent sequences than the iid reference alone.
The CSV reports both full-sequence and trimmed-window marginal errors, because
rank-binning or empirical calibration can control the whole generated sample
while an interior window still fluctuates under dependence.
For the LAMP-family marginal-control cases, validation uses
lamp_repeat_transition(p; repeat_probability = 0.4), whose stationary
distribution is the requested marginal. The pure identity transition remains
available as a stress case but can preserve early imbalances for a long time.
The LRD diagnostic transformation is formalized in
validation/lrd_symbol_diagnostics.jl: symbols are converted to centered one-hot
numeric series before autocorrelation, autocovariance, and periodogram
calculations. The LongMemory.jl comparison script documents and tests the needed
adaptations to LongMemory.jl's lag and frequency conventions.
Autocorrelation validation plots include dashed vertical interpretation limits:
a finite-sample n / 10 lag limit, and explicit generator limits where they
exist, such as LAMP.d. Spectrum plots show the same scales as reciprocal
frequencies. Where the model has a defensible asymptotic-onset scale, plots also
mark an approximate power-law onset. For example, OnOffMarkov uses its Pareto
scale L_min, while HawkesSymbol, SelfExcitingMass, and LogitSelfExcitingMass use the lag where the offset kernel
(lag + c)^(-beta) reaches 90% of its asymptotic log-log slope. Autocorrelation
plots also include a gray dashed nominal power-law reference line with slope
lag^(-beta), anchored to the first positive plotted autocorrelation value.
Power-spectrum plots include the corresponding gray dashed low-frequency
reference with slope frequency^(beta - 1).
Current MB4a (HawkesSymbol) diagnostics should be read cautiously: the finite
discrete-time normalized implementation can produce short-range burstiness while
its centered one-hot power spectrum remains close to white noise. MB4b
(SelfExcitingMass) addresses the main failure mode by leaving the power-law
memory mass unnormalized until the final categorical draw, while retaining a
small default/smoothing mass for support and stability. MB4c
(LogitSelfExcitingMass) applies centered log contrasts to reduce common-mode
normalization, but can lock onto too few symbols when the contrast is too strong.
Both MB4b and MB4c should still be validated empirically rather than treated as
theorem-backed LRD constructions.
Validation policy is documented in VALIDATION_POLICY.md. The fast package test
suite remains the main development pathway, while larger empirical studies are run
manually or behind explicit flags such as SLMS_VALIDATION_LARGE=true.
Benchmarks live in benchmark/ and use a separate Project.toml with
BenchmarkTools.jl:
julia --project=benchmark benchmark/benchmarks.jl
SLMS_BENCHMARK_LARGE=true julia --project=benchmark benchmark/benchmarks.jl
SLMS_BENCHMARK_SCALING=true julia --project=benchmark benchmark/benchmarks.jlThe default benchmark run writes benchmark/RESULTS.md, a CSV table under
benchmark/results/benchmarks.csv, histogram-style relative-time SVGs, and
log-log scaling plots by alphabet size. The retained scaling results use
n = 100, 1_000, 10_000, 100_000, 1_000_000, defer k = 64, and average each
BenchmarkTools trial over 10 independently seeded syntheses. They show the
expected cost split: direct sequential methods such as OnOffMarkov, FSS, and
DuplicationMutation are fastest, FFT/rank-binning methods scale well with n,
LGCM grows with alphabet size, and explicit history methods such as LAMP,
HawkesSymbol, SelfExcitingMass, LogitSelfExcitingMass, and DyadicLAMP pay for their configured memory depth.
First-order local-structure controls use MarkovSpec. Trigram diagnostics are
available through empirical_trigram, but a concrete trigram-control
specification is intentionally left for future work. The code now exposes
LocalStructureSpec and local_structure_order as the extension path for that
higher-order API.
For one-step Markov behavior, direct matrix testing has k^2 cells and quickly
needs much more data than marginal testing. A practical shortcut is to test
low-dimensional contrasts of the transition matrix: repeat probability, selected
row total-variation errors, stationary-weighted row error, and application-level
symbol groups, while reserving full row-by-row tests for smaller alphabets or
large validation runs.
A more formal marginal test than the approximate ESS-adjusted chi-squared diagnostic would estimate the null distribution under dependence. Practical options are block/subsampling tests or a parametric Monte Carlo envelope generated from the same configured method. Those are validation extensions rather than fast package tests.
- Paxson, V. (1997). Fast, approximate synthesis of fractional Gaussian noise. CCR 27.
- Dieker, T. (2004). Simulation of fractional Brownian motion. PhD thesis, U. Twente.
- Roughan, M., Veitch, D., & Abry, P. (2000). Real-time estimation of LRD parameters. IEEE/ACM ToN 8(4).
- Gal, Y., Chen, Y., & Ghahramani, Z. (2015). Latent Gaussian processes for distribution estimation of multivariate categorical data. ICML.
- Li, W. (1991). Expansion-modification systems: a model for spatial 1/f spectra. Physical Review A 43.
- Li, W., Marr, T. G., & Kaneko, K. (1994). Understanding long-range correlations in DNA sequences. Physica D 75.
- Melnyk, S. S., Usatenko, O. V., & Yampol'skii, V. A. (2006). Memory functions of the additive Markov chains. Physica A 361.
- Mayzelis, Z. A., Apostolov, S. S., Melnyk, S. S., Usatenko, O. V., & Yampol'skii, V. A. (2006). Additive N-step Markov chains as prototype model of symbolic stochastic dynamical systems with long-range correlations.
- Kumar, R., Raghu, M., Sarlós, T., & Tomkins, A. (2017). Linear additive Markov processes. WWW '17.
- Singh, M., Greenberg, C., & Klakow, D. (2016). The custom decay language model. TSD.
- Ryu, B., & Lowen, S. (1998). Point process models for self-similar network traffic. Stochastic Models 14(3).
- Roughan, M., Yates, J., & Veitch, D. (1999). The mystery of the missing scales. Heavy Tails Workshop.
- Provata, A., & Beck, C. (2012). Coupled intermittent maps modelling the statistics of genomic sequences: a network approach. arXiv:1205.2249.
- Pipiras, V., & Taqqu, M. S. (2017). Long-Range Dependence and Self-Similarity. Cambridge UP.
This package was developed with assistance from Claude Sonnet 4.6 (Anthropic), and Codex; AI coding assistants. The design goals, overall architecture, methods design were human, but Claude and Codex contributed to the design of the package architecture, the coding itself, and some of the write-up of synthesis methods.