Almost surely

Almost surely

In probability theory, one says that an event happens almost surely (a.s.) if it happens with probability one. The concept is analogous to the concept of "almost everywhere" in measure theory. It is often encountered in questions that involve infinite time, regularity properties or infinite-dimensional spaces such as function spaces. Basic examples of use include the law of large numbers (strong form) or continuity of Brownian paths.

Formal definition

Let ("Ω", "F", "P") be a probability space. One says that an event "E" in "F" happens almost surely if "P"("E") = 1. Alternatively, an event "E" happens almost surely if the probability of "E" not occurring is zero.

An alternate definition from a measure theoretic-perspective is that (since "P" is a measure over "Ω") "E" happens almost surely if "E" = "Ω" almost everywhere.

"Almost sure" versus "sure"

The difference between an event being "almost sure" and "sure" is the same as the subtle difference between something happening "with probability 1" and happening "always".

If an event is "sure", then it will always happen. No other event (even events with probability 0) can possibly occur. If an event is "almost sure", then other events are theoretically possible in a given sample space, however as the cardinality of the sample space increases, the probability of any other event asymptotically converges toward zero. Thus, one can never definitively say for any sample space that other events will never occur, but can in the general case assume this to be true. In this respect, the concept is similar to that of a mathematical limit.

Throwing a dart

For example, imagine throwing a dart at a unit square wherein the dart will impact exactly one point, and imagine that this square is the only thing in the universe. There is physically nowhere else for the dart to land. Then, the event that "the dart hits the square" is a sure event. No other alternative is imaginable.

Next, consider the event that "the dart hits the diagonal of the unit square exactly". The probability that the dart lands on any subregion of the square is equal to the area of that subregion. But, since the area of the diagonal of the square is zero, the probability that the dart lands exactly on the diagonal is zero. So, the dart will almost surely not land on the diagonal. Nonetheless the set of points on the diagonal is not empty and a point on the diagonal is no less possible than any other point.

The same may be said of any point on the square. Any such point "P" will contain zero area and so will have zero probability of being hit by the dart. However, the dart clearly must hit the square somewhere. Therefore, in this case, it is not only possible or imaginable that an event with zero probability will occur; one must occur. Thus, we would not want to say we were certain that a given such event would not occur, but rather "almost certain".

Tossing a coin

Suppose that an "ideal" (edgeless) fair coin is flipped again and again. A coin has two sides, heads and tails, and therefore the event that "heads or tails is flipped" is a sure event. There can be no other result from such a coin.

The infinite sequence of all heads ("H-H-H-H-H-H-…"), "ad infinitum", is possible in some sense (it does not violate any physical or mathematical laws to suppose that "tails" never appears) but it is very, very improbable. In fact, the probability of "tails" never being flipped in an infinite series is zero. Thus, though we cannot definitely say tails will be flipped at least once, we can say there will "almost surely" be at least a single tails flip in an infinite sequence of flips.

However, if instead of an infinite number of flips we stop flipping after some finite time, say a million flips, then the all-heads sequence has non-zero probability. The all-heads sequence has probability 2−1,000,000, thus the probability of getting a tails is 1 − 2−1,000,000 < 1, and the event is no longer "almost sure".

Asymptotically almost surely

In asymptotic analysis, one says that a property holds asymptotically almost surely (a.a.s.) if, over a sequence of sets, the probability converges to 1. For instance, a large number is asymptotically almost surely composite, by the prime number theorem; and in random graph theory, the statement "G"("n","p""n") is connected" (where "G"("n","p") denotes the graphs on "n" vertices with edge probability "p") is true a.a.s when "p"n > frac{(1+epsilon) ln n}{n} for any ε > 0.cite journal|last=Friedgut|first=Ehud|coauthors=Rödl, Vojtech; Rucinski, Andrzej; Tetali, Prasad|date=January 2006|title=A Sharp Threshold for Random Graphs with a Monochromatic Triangle in Every Edge Coloring|journal=Memoirs of the American Mathematical Society|publisher=AMS Bookstore|volume=179|issue=845|pages=pp. 3–4|issn=0065-9266|accessdate=2008-09-21]

In number theory this is referred to as "almost all", as in "almost all numbers are composite". Similarly, in graph theory, this is sometimes referred to as "almost surely".cite book|last=Spencer|first=Joel H.|title=The Strange Logic of Random Graphs|publisher=Springer|date=2001|series=Algorithms and Combinatorics|pages=p. 4|chapter=0. Two Starting Examples|accessdate=2008-09-21]

See also

* Convergence of random variables, for "almost sure convergence"
* Constant random variable, for "almost surely constant"
* Almost everywhere, the corresponding concept in measure theory

Notes

References

*
*


Wikimedia Foundation. 2010.

Игры ⚽ Поможем сделать НИР

Look at other dictionaries:

  • Almost Mathieu operator — In mathematical physics, the almost Mathieu operator arises in the study of the quantum Hall effect. It is given by: [H^{lambda,alpha} omega u] (n) = u(n+1) + u(n 1) + 2 lambda cos(2pi (omega + nalpha)) u(n), , acting as a self adjoint operator… …   Wikipedia

  • Almost all — In mathematics, the phrase almost all has a number of specialised uses. Almost all is sometimes used synonymously with all but finitely many (formally, a cofinite set) or all but a countable set (formally, a cocountable set); see almost. An… …   Wikipedia

  • Almost everywhere — In measure theory (a branch of mathematical analysis), one says that a property holds almost everywhere if the set of elements for which the property does not hold is a null set, i.e. is a set with measure zero, or in cases where the measure is… …   Wikipedia

  • Almost — In mathematics, especially in set theory, when dealing with sets of infinite size, the term almost or nearly is used to mean all the elements except for finitely many . In other words, an infinite set S that is a subset of another infinite set L …   Wikipedia

  • Convergence of random variables — In probability theory, there exist several different notions of convergence of random variables. The convergence of sequences of random variables to some limit random variable is an important concept in probability theory, and its applications to …   Wikipedia

  • pre-Columbian civilizations — Introduction       the aboriginal American Indian (Mesoamerican Indian) cultures that evolved in Meso America (part of Mexico and Central America) and the Andean region (western South America) prior to Spanish exploration and conquest in the 16th …   Universalium

  • Europe, history of — Introduction       history of European peoples and cultures from prehistoric times to the present. Europe is a more ambiguous term than most geographic expressions. Its etymology is doubtful, as is the physical extent of the area it designates.… …   Universalium

  • Infinite monkey theorem — Not to be confused with Hundredth monkey effect. Given enough time, a hypothetical monkey typing at random would, as part of its output, almost surely produce all of Shakespeare s plays. In this image a chimpanzee is giving it a try. The infinite …   Wikipedia

  • Fatou's lemma — In mathematics, Fatou s lemma establishes an inequality relating the integral (in the sense of Lebesgue) of the limit inferior of a sequence of functions to the limit inferior of integrals of these functions. The lemma is named after the French… …   Wikipedia

  • Erdős–Rényi model — In graph theory, the Erdős Rényi model, named for Paul Erdős and Alfréd Rényi, is either of two models for generating random graphs, including one that sets an edge between each pair of nodes with equal probability, independently of the other… …   Wikipedia

Share the article and excerpts

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