x - input sequence

n - length of x

x=x₁x₂...x_n, x_i^j=x_ix_i+1...x_j

α - discrete alphabet

r - cardinality of α

n_x(a) - the number of times that a∈α appears in x

P_x(a) - empirical probability

Q - the true i.i.d. distribution of x

H - entropy

D(·∥·) - divergence

⌈·⌉ - rounding up

R - rate of source code

T_Q(δ) - set of inputs that are δ-typical with respect to (w.r.t.) Q

C - a code

(·)^C - complement of set

·^T - transpose of vector or matrix

l(x) - length of code in bits

x^'=S_x - step ∀n∈Z, x_n^'=x_n+1

θ - parameters of parametric source (can contain multiple scalar parameters)

M - number of states of unifilar source

S={1,...,M} - states of unifilar source

s₁,...,s_n, - state sequence

- transition probability

- next state function

Λ - class of parametric models

c_n - collection of lossless codes for length-n inputs

I(·;·) - mutual information

r_n(l,θ) - how far a coding length function l is from the entropy

h₂(·) - binary entropy

I(·) - Fisher information

J(·) - Jeffreys' prior

θ_ML - maximum likelihood parameter

R_n^–, R_n⁺ - min-max and max-min redundancy

T - set of leaves of a context tree source

s - state of context tree

n_x(s,a) - number of times that a∈α appears in context s in x

T^* - optimal context tree source

D - maximal depth of tree source

T_s^* - optimal tree structure to encode symbols whose context ends with s

MDL(s) - minimum description length required for encoding these symbols

KT(·,·) - Krichevsky-Trofimov coding length

(y,i) - BWT output consisting the permuted sequence and index

- approximate version of x

- reproduction alphabet

d(·,·) - distortion metric

- distortion between sequences

D - distortion level

R(D) - minimal rate such that can be described

t - temperature in simulated annealing

Z_t - normalization factor in Boltzmann pmf

N_r - recurrence time