Effective dimension

Effective dimension

In mathematics, effective dimension is a modification of Hausdorff dimension and other fractal dimensions which places it in a computability theory setting. There are several variations (various notions of effective dimension) of which the most common is effective Hausdorff dimension. Dimension, in mathematics, is a particular way of describing the size of an object (contrasting with measure and other, different, notions of size). Hausdorff dimension generalizes the well-known integer dimensions assigned to points, lines, planes, etc. by allowing one to distinguish between objects of intermediate size between these integer-dimensional objects. For example, fractal subsets of the plane may have intermediate dimension between 1 and 2, as they are "larger" than lines or curves, and yet "smaller" than filled circles or rectangles. Effective dimension modifies Hausdorff dimension by requiring that objects with small effective dimension be not only small but also locatable (or partially locatable) in a computable sense. As such, objects with large Hausdorff dimension also have large effective dimension, and objects with small effective dimension have small Hausdorff dimension, but an object can have small Hausdorff but large effective dimension. An example is an algorithmically random point on a line, which has Hausdorff dimension 0 (since it's a point) but effective dimension 1 (because, roughly speaking, it can't be effectively localized any better than a small interval, which has Hausdorff dimension 1).

Rigorous definitions

This article will define effective dimension for subsets of Cantor space 2ω; closely related definitions exist for subsets of Euclidean space R"n". We will move freely between considering a set "X" of natural numbers, the infinite sequence chi_X given by the characteristic function of "X", and the real number with binary expansion 0."X".

Martingales and other gales

A "martingale" on Cantor space 2ω is a function "d": 2ωR≥0 from Cantor space to nonnegative reals which satisfies the fairness condition:

: d(sigma)=frac12 (d(sigma 0)+d(sigma 1))

A martingale is thought of as a betting strategy, and the function d(sigma) gives the capital of the better after seeing a sequence σ of 0s and 1s. The fairness condition then says that the capital after a sequence σ is the average of the capital after seeing σ0 and σ1; in other words the martingale gives a betting scheme for a bookie with 2:1 odds offered on either of two "equally likely" options, hence the name fair.

(Note that this is subtly different from the probability theory notion of martingale.cite journal | author = John M. Hitchcock and Jack H. Lutz | title = Why computational complexity requires stricter martingales | journal = Theory of Computing Systems | year = 2006] That definition of martingale has a similar fairness condition, which also states that the expected value after some observation is the same as the value before the observation, given the prior history of observations. The difference is that in probability theory, the prior history of observations just refers to the capital history, whereas here the history refers to the exact sequence of 0s and 1s in the string.)

A "supermartingale" on Cantor space is a function "d" as above which satisfies a modified fairness condition:

: d(sigma) geq frac12 (d(sigma 0)+d(sigma 1))

A supermartingale is a betting strategy where the expected capital after a bet is no more than the capital before a bet, in contrast to a martingale where the two are always equal. This allows more flexibility, and is very similar in the non-effective case, since whenever a supermartingale "d" is given, there is a modified function "d"' which wins at least as much money as "d" and which is actually a martingale. However it is useful to allow the additional flexibility once one starts talking about actually giving algorithms to determine the betting strategy, as some algorithms lend themselves more naturally to producing supermartingales than martingales.

An "s"-"gale" is... (essentially, a martingale under inflation)

An "s"-"supergale" is... (a supermartingale under inflation)

Collectively, these objects are known as "gales".

A gale "d" succeeds on a subset "X" of the natural numbers if limsup_n d(X|n)=infty where X|n denotes the "n"-digit string consisting of the first "n" digits of "X".

All of these notions of various gales have no effective content, but one must necessarily restrict ones self to a small class of gales, since some gale can be found which succeeds on any given set. After all, if one knows a sequence of coin flips in advance, it is easy to make money by simply betting on the known outcomes of each flip. A standard way of doing this is to require the gales to be either computable or close to computable:

A gale "d" is called "constructive", "c.e.", or "lower semi-computable" if the numbers d(sigma) are uniformly left-c.e. reals (i.e. can uniformly be written as the limit of an increasing computable sequence of rationals). A gale "d" is called "computable" if the numbers d(sigma) are uniformly computable reals. A gale "d" is called "partial computable" if there is a partial computable procedure which either gives an approximation of "d" to any desired accuracy on some input, or else fails to halt and give an answer. One additionally requires that if "d" is defined on some string sigma, it is also defined on all prefixes of sigma, and that if "d" is defined on either of sigma 0 or sigma 1, it is defined on both. Partial gales also require modifying the other definitions slightly: if a gale is allowed to be partial, one only requires the above equalities/inequalities to be satisfied when all terms are defined, and one says that a partial gale "d" succeeds on a set "X" if "d" is defined on all initial segments of the characteristic function of "X", and that the limsup_n d(X|n)=infty as before.

Kolmogorov complexity definition

Comparison to Hausdorff dimension

References

*cite journal
author = J. H. Lutz
title = Effective fractal dimensions
journal = Mathematical Logic Quarterly
volume = 51
pages = 62–72
year = 2005
doi = 10.1002/malq.200310127
[http://www.cs.iastate.edu/~lutz/papers.html]
*citation
author = J. Reimann
title = Computability and fractal dimension, PhD thesis
publisher = Ruprecht-Karls Universität Heidelberg
year = 2004
[http://www.math.uni-heidelberg.de/logic/reimann/publications.html]


Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

  • Effective medium approximations — or effective medium theory (sometimes abbreviated as EMA or EMT) are physical models that describe the macroscopic properties of a medium based on the properties and the relative fractions of its components. They can be discrete models such as… …   Wikipedia

  • Effective Medium Approximations — are analytical models that describe the macroscopic properties of a medium based on the properties and the relative fractions of its components. They are continuous theories and do not relate directly to percolating systems. Indeed, among the… …   Wikipedia

  • effective throat thickness — dimension that is responsible for carrying the load, dependent on the shape and penetration of the weld Источник: ГОСТ Р ИСО 17659 2009: Сварка. Термины многоязычные для сварных соединений оригинал доку …   Словарь-справочник терминов нормативно-технической документации

  • dimension effective — faktinis matmuo statusas T sritis fizika atitikmenys: angl. actual size vok. Istmaß, n; tatsächliches Maß, n rus. действительный размер, m; истинный размер, m pranc. dimension effective, f; dimension réelle, f …   Fizikos terminų žodynas

  • dimension effective — faktinis matmuo statusas T sritis Standartizacija ir metrologija apibrėžtis Matmuo, gautas matuojant gaminį reikiamu tikslumu. atitikmenys: angl. actual size vok. Istmaß, n; tatsächliches Maß, n rus. действительный размер, m; истинный размер, m… …   Penkiakalbis aiškinamasis metrologijos terminų žodynas

  • dimension réelle — faktinis matmuo statusas T sritis fizika atitikmenys: angl. actual size vok. Istmaß, n; tatsächliches Maß, n rus. действительный размер, m; истинный размер, m pranc. dimension effective, f; dimension réelle, f …   Fizikos terminų žodynas

  • Dimension œcuménique — Œcuménisme Christianisme Religions abrahamiques (arbre) Judaïsme · Christianisme · Islam Courants Arbre du christianisme Grandes confessions : Catholicisme · Orthodoxie · Protestantisme …   Wikipédia en Français

  • effective plug diameter —   n.    the dimension obtained by adding the root depth of a key cut to the length of its corresponding bottom pin which establishes a perfect shear line. This will not necessarily be the same as the actual plug diameter …   Locksmith dictionary

  • Slowly changing dimension — Dimension is a term in data management and data warehousing that refers to logical groupings of data such as geographical location, customer information, or product information. Slowly Changing Dimensions (SCD) are dimensions that have data that… …   Wikipedia

  • Température effective — Transfert de rayonnement Le transfert de rayonnement est le domaine de la physique décrivant l interaction du rayonnement électromagnétique et de la matière. Cette discipline permet notamment d analyser la propagation de la lumière à travers un… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”