For random fields on the d-dimensional integer lattice with finite state space, the basic neighborhood is the smallest region around a site that determines the conditional distribution at the site given the values at all other sites. For variable basic neighborhood random fields the basic neighborhood may vary with the values at the surrounding sites, and the sets of the values in these basic neighborhoods are called context blocks. The context blocks may be infinite. Statistical estimation of the context block system of a random field from a sample, a single realization of the random field observed in a finite region, is addressed. The Optimal Likelihood Ratio (OLR) estimator is introduced. Its nearly linear computation complexity is shown and a bound on the probability of the estimation error is proved that implies strong consistency of the estimator.

Contexts of stationary ergodic sources are considered not necessarily consecutive sequences of symbols of the past. The introduced context set model of a source provides a code that can achieve less parameter redundancy than the code the context tree and generalized context tree models provide. The problem of coding sources with unknown context set is addressed for multialphabet sources. Information on the maximum memory length of the source is not required; it may be even infinite. The Context Set Weighting method is introduced to efficiently calculate a mixture of the Krichevsky-Trofimov distributions over possible context sets. The coding distribution is proved to provide a code whose model redundancy does not exceed the order of the parameter redundancy. An algorithm is provided to compute the Context Set Weighting in a polynomial time.

Markov random fields on the d-dimensional integer lattice with finite state space are considered, and the problem of estimation of the basic neighborhood from a single realization observed in a finite region is addressed. The Optimal Likelihood Ratio (OLR) estimator is introduced. Its nearly linear computation complexity is shown, and a bound on the probability of the estimation error is proved that implies strong consistency.

Stationary ergodic processes with finite alphabets are estimated by finite memory processes from a sample, an n-length realization of the process. Both the transition probabilities and the memory depth of the estimator process are estimated from the sample using penalized maximum likelihood (PML). Under some assumptions on the continuity rate and the assumption of non-nullness, a rate of convergence in d̅-distance is obtained, with explicit constants. The results show an optimality of the PML Markov order estimator for not necessarily finite memory processes. Moreover, the notion of consistent Markov order estimation is generalized for infinite memory processes using the concept of oracle order estimates, and generalized consistency of the PML Markov order estimator is presented.

Context trees of arbitrary stationary ergodic processes with finite alphabets are considered. Such a process is not necessarily a Markov chain, so the context tree may be of infinite depth. Calculated from a sample of sizen, the Bayesian information criterion (BIC) is shown to provide a strongly consistent estimator of the context tree of the process, via minimization over hypothetical context trees, without any restriction on the hypothetical context trees. Strong consistency means that the estimated context tree recovers the true one up to a levelK, eventually almost surely asntends to infinity. Under some conditions on the process, it is shown that the recovery levelKcan grow withnat a specific rate determined by the distribution of the process; thus, the BIC estimator can recover the true context tree to larger and larger depths. The results include for the special case ofKbeing an arbitrary constant that the strong consistency is satisfied without any assumption on the stationary ergodic process, which itself improves the existing results, where either the true context tree was assumed to be of finite depth or the depth of the hypothetical context trees was bounded byo(logn).

For finite-alphabet stationary ergodic processes with infinite memory, Markov order estimators that optimize an information criterion over the candidate orders based on a sample of size n are investigated. Three familiar information criteria are considered: the Bayesian information criterion (BIC) with generalized penalty term yielding the penalized maximum likelihood (PML), and the normalized maximum likelihood (NML) and the Krichevsky-Trofimov (KT) code lengths. A bound on the probability that the estimated order is greater than some order is obtained under the assumption that the process is weakly non-null and α-summable. This gives an O(log n) upper bound on the estimated order eventually almost surely as n → +∞. Moreover, a bound on the probability that the estimated order is less than some order is obtained if the decay of the continuity rate of the weakly non-null process is in some exponential range. This implies that then the estimated order attains the O(log n) divergence rate eventually almost surely as n → +∞.

Stationary ergodic processes with finite alphabets are approximated by finite memory processes based on an n-length realization of the process. Under the assumptions of summable continuity rate and non-nullness, a rate of convergence ind̅-distance is obtained, with explicit constants. Asymptotically, asn→ ∞, the result is near the optimum.

Context trees of arbitrary stationary ergodic processes with finite alphabets are considered. Such a process is not necessarily a Markov chain, so the context tree may be of infinite depth. Calculated from a sample of size n, the Bayesian information criterion (BIC) is shown to provide a strongly consistent estimator of the context tree of the process, via minimization over hypothetical context trees, without any restriction on the hypothetical context trees. Strong consistency means that the estimated context tree recovers the true one up to any fixed level K, eventually almost surely as n tends to infinity. This generalizes the previous results, where either the context trees were assumed to be of finite depth or the depth of the hypothetical context trees was bounded by O(log n). Moreover, under some conditions on the process it is also shown that the level K above can grow with n at a specific rate determined by the distribution of the process; thus the BIC estimator can recover the true context tree to larger and larger depths.

The concept of context tree, usually defined for finite memory processes, is extended to arbitrary stationary ergodic processes (with finite alphabet). These context trees are not necessarily complete, and may be of infinite depth. The familiar Bayesian information criterion (BIC) and minimum description length (MDL) principles are shown to provide strongly consistent estimators of the context tree, via optimization of a criterion for hypothetical context trees of finite depth, allowed to grow with the sample size n as o(logn). Algorithms are provided to compute these estimators in O(n) time, and to compute them on-line for all i les n in o(nlogn) time

The concept of context tree, usually defined for finite memory processes, is extended to arbitrary stationary ergodic processes (with finite alphabet). These context trees are not necessarily complete, and may be of infinite depth. The familiar BIC and MDL principles are shown to provide strongly consistent estimators of the context tree, via optimization of a criterion for hypothetical context trees of finite depth, allowed to grow with the sample size n as o(log n). Algorithms are provided to compute these estimators in O(n) time, and to compute them on-line for all i les n in o(nlog n) time

For Markov random fields with finite set of states, a modification of the Bayesian information criterion admits strongly consistent estimation of the smallest region that determines the conditional distributions. Phase transition or nonstationarity do not affect the result.