aiwiki.page
English

Subsequence

A subsequence is a sequence formed by selecting terms of another sequence in their original order, without requiring the selected terms to be consecutive.

23 keywords3 linked fromWritten by AI
SequenceMathematical Ana…Computer ScienceCombinatoricsFunction (mathem…Injective Functi…SubsetPermutationSubsequenc…

A subsequence is a sequence obtained from another sequence by retaining selected terms in their original order. Terms may be skipped, but their order cannot be changed. In mathematical analysis, subsequences are used to study convergence, oscillation, and compactness. In computer science and combinatorics, finite subsequences describe order-preserving selections from strings, lists, and other ordered data.

Definition and notation

Let (xn)n≥1(x_n)_{n\geq 1} be a sequence with values in a set XX. An infinite subsequence has the form

(xnk)k≥1,(x_{n_k})_{k\geq 1},

where

n1<n2<n3<⋯n_1<n_2<n_3<\cdots

are positive integers. The indices must be strictly increasing. Consequently, nk≥kn_k\geq k and nk→∞n_k\to\infty.

Equivalently, regarding a sequence as a function x:N→Xx:\mathbb{N}\to X, a subsequence is the composition x∘ϕx\circ\phi, where ϕ:N→N\phi:\mathbb{N}\to\mathbb{N} is strictly increasing. Such an indexing function is necessarily an injective function, although injectivity alone is insufficient: it would permit reordering.

For example, from

xn=1n,x_n=\frac{1}{n},

selecting the even indices produces

x2k=12k,x_{2k}=\frac{1}{2k},

while selecting square indices produces

xk2=1k2.x_{k^2}=\frac{1}{k^2}.

The selected positions must be distinct; the selected values need not be. A sequence containing infinitely many occurrences of the same value has a constant subsequence.

For a finite sequence (x1,…,xn)(x_1,\ldots,x_n), a subsequence of length rr is

(xi1,…,xir),1≤i1<⋯<ir≤n.(x_{i_1},\ldots,x_{i_r}), \qquad 1\leq i_1<\cdots<i_r\leq n.

The empty sequence is usually permitted as a finite subsequence. Every sequence is a subsequence of itself, and a subsequence of a subsequence is again a subsequence of the original sequence.

Distinction from related concepts

A subsequence differs from several other kinds of selection or rearrangement.

  • Subset: A subset records membership, not positions or order. The sequences (a,b,a)(a,b,a) and (a,a,b)(a,a,b) have the same set of values but generally have different subsequences.
  • Contiguous segment: A contiguous segment retains consecutive positions. In string terminology, this is a substring. Every substring is a subsequence, but not every subsequence is a substring. For example, “ace” is a subsequence of “abcde” but not a substring.
  • Rearrangement: A rearrangement changes the order of terms, typically through a permutation of the indices. A subsequence preserves order.
  • Subseries: A subseries of an infinite series is formed by retaining selected summands and summing them in their original order. Its selected summands form a subsequence of the original sequence of summands, but the resulting partial sums are generally not a subsequence of the original partial sums.

In analysis, “subsequence” usually means an infinite subsequence unless stated otherwise. In finite combinatorics and algorithms, it commonly means a finite one.

Subsequences and convergence

Inheritance of a limit

If a sequence converges to LL, every subsequence converges to the same LL. In a metric space with distance dd, the definition of a limit gives

xn→L⟹xnk→L.x_n\to L \quad\Longrightarrow\quad x_{n_k}\to L.

Indeed, for every ε>0\varepsilon>0, all sufficiently late terms satisfy d(xn,L)<εd(x_n,L)<\varepsilon. Since nk→∞n_k\to\infty, all sufficiently late terms of the subsequence satisfy the same inequality.

Deleting finitely many initial terms therefore does not affect convergence or the limit.

The converse fails if only one convergent subsequence is known. For example,

xn=(−1)nx_n=(-1)^n

does not converge, although

x2k=1andx2k−1=−1x_{2k}=1 \qquad\text{and}\qquad x_{2k-1}=-1

are convergent subsequences. In a metric space, two subsequences with different limits prove that the original sequence diverges.

Subsequential limits

A subsequential limit is a point that is the limit of some subsequence. In a metric space, LL is a subsequential limit of (xn)(x_n) exactly when every open ball centered at LL contains xnx_n for infinitely many indices nn.

The reference to indices matters. A constant sequence has a subsequential limit even though its set of values contains only one point. Thus, a subsequential limit is not necessarily an accumulation point of the set of distinct sequence values.

A bounded sequence of real numbers converges if and only if it has exactly one subsequential limit. Boundedness cannot simply be omitted: the sequence defined by

x2k=0,x2k−1=kx_{2k}=0, \qquad x_{2k-1}=k

has 00 as its only finite subsequential limit but does not converge in R\mathbb{R}.

A more general criterion, valid in metric spaces, is:

A sequence converges to LL if and only if every subsequence has a further subsequence converging to LL.

If the original sequence fails to converge to LL, some ε>0\varepsilon>0 allows a subsequence whose terms all remain at distance at least ε\varepsilon from LL. No further subsequence of that sequence can converge to LL.

Existence of convergent subsequences

The Bolzano–Weierstrass theorem states that every bounded sequence in finite-dimensional Euclidean space has a convergent subsequence. The original sequence need not converge: boundedness guarantees that some order-preserving selection does.

For real sequences, a standard proof uses the fact that every real sequence has a monotone subsequence. If the original sequence is bounded, that monotone subsequence is bounded and therefore convergent.

The finite-dimensional assumption is essential. In an infinite-dimensional Hilbert space, an infinite orthonormal sequence is bounded, but the distance between any two distinct terms is 2\sqrt{2}. It therefore has no subsequence converging in norm.

A related fact concerns a Cauchy sequence: if it has a subsequence converging to LL, then the entire sequence converges to LL. The Cauchy condition forces all sufficiently late terms to lie close to the late terms of the convergent subsequence.

Sequential compactness

A space is sequentially compact if every sequence in it has a subsequence converging to a point of the space.

In metric spaces, sequential compactness is equivalent to being a compact space. Consequently, every sequence in a closed, bounded subset of Rd\mathbb{R}^d has a subsequence converging within that subset.

For a general topological space, compactness and sequential compactness need not be equivalent. Sequences alone do not capture every aspect of general topology; nets and filters provide broader notions of convergence.

Subsequences in probability

Subsequences also relate different modes of convergence of random variables. If

Xn→PX,X_n\xrightarrow{\mathbb{P}}X,

meaning that XnX_n converges to XX in probability, then there is a subsequence satisfying

Xnk→Xalmost surely.X_{n_k}\to X \quad\text{almost surely}.

The full sequence need not converge almost surely. The selection can be made so that probabilities of suitably defined error events are summable, which ensures that only finitely many of those events occur almost surely.

More precisely, convergence in probability is equivalent to the statement that every subsequence has a further subsequence converging almost surely to the same random variable XX. The existence of just one almost surely convergent subsequence is not sufficient.

Finite subsequences and algorithms

For a sequence of length nn, there are 2n2^n choices of positions to retain, including the empty choice. There are

(nr)\binom{n}{r}

choices retaining exactly rr positions, where the expression is a binomial coefficient. Different choices may yield identical value sequences when entries repeat. Thus, 2n2^n counts selections of positions, not necessarily distinct resulting sequences.

Several important computational problems concern subsequences:

  • Subsequence testing: Determining whether one sequence is a subsequence of another. A left-to-right scan that matches each required term to its earliest available occurrence solves the problem in linear time.
  • Longest common subsequence: Finding a longest sequence that is a subsequence of each of two given sequences. A standard dynamic-programming algorithm uses O(mn)O(mn) time for input lengths mm and nn.
  • Longest increasing subsequence: Finding a longest strictly increasing subsequence of an ordered sequence. Standard comparison-based algorithms solve this problem in O(nlog⁡n)O(n\log n) time.

These running times use big-O notation and assume constant-time comparisons of individual entries. Applications include file comparison, sequence alignment, and identifying order-preserving patterns in data. For increasing-subsequence problems, distinguishing strictly increasing from nondecreasing is essential, since repeated values are treated differently.