Almost surely
Encyclopedia
In probability theory
, one says that an event
happens almost surely (sometimes abbreviated as a.s.) if it happens with probability one. The concept is analogous to the concept of "almost everywhere
" in measure theory. While there is no difference between almost surely and surely (that is, entirely certain to happen) in many basic probability experiments, the distinction is important in more complex cases relating to some sort of infinity
. For instance, the term is often encountered in questions that involve infinite time, regularity properties or infinite-dimension
al spaces such as function space
s. Basic examples of use include the law of large numbers
(strong form) or continuity of Brownian paths
.
Almost never describes the opposite of almost surely; an event which happens with probability zero happens almost never.
. One says that an event
E in F happens almost surely if P(E) = 1.
Equivalently, we can say an event E happens almost surely if the probability of E not occurring is zero
.
An alternative definition from a measure theoretic
-perspective is that (since P is a measure over Ω) E happens almost surely if E = Ω almost everywhere
.
If an event is sure, then it will always happen, and no outcome not in this event can possibly occur. If an event is almost sure, then outcomes not in this event are theoretically possible; however, the probability of such an outcome occurring is smaller than any fixed positive probability, and therefore must be 0. Thus, one cannot definitively say that these outcomes will never occur, but can for most purposes assume this to be true.
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 proportional 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, therefore theoretically it is possible that the dart actually hits the diagonal.
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 event would not occur, but rather almost certain.
is flipped again and again. A coin has two sides, head and tail, and therefore the event that "head or tail 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 appear), but it is very, very improbable. In fact, the probability of tail never being flipped in an infinite series is zero. Thus, though we cannot definitely say tail will be flipped at least once, we can say there will almost surely be at least one tail in an infinite sequence of flips. (Note that given the statements made in this paragraph, any predefined ordering would have zero-probability in an infinite series. This makes sense because there are an infinite number of possibilities and
.)
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 at least one tail is 1 − 2−1,000,000 < 1, and the event is no longer almost sure.
, 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,pn) is connected
" (where G(n,p)
denotes the graphs on n vertices with edge probability p) is true a.a.s when pn >
for any ε > 0.
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".
Probability theory
Probability theory is the branch of mathematics concerned with analysis of random phenomena. The central objects of probability theory are random variables, stochastic processes, and events: mathematical abstractions of non-deterministic events or measured quantities that may either be single...
, one says that an event
Event (probability theory)
In probability theory, an event is a set of outcomes to which a probability is assigned. Typically, when the sample space is finite, any subset of the sample space is an event...
happens almost surely (sometimes abbreviated as a.s.) if it happens with probability one. The concept is analogous to the concept of "almost everywhere
Almost everywhere
In measure theory , a property holds almost everywhere if the set of elements for which the property does not hold is a null set, that is, a set of measure zero . In cases where the measure is not complete, it is sufficient that the set is contained within a set of measure zero...
" in measure theory. While there is no difference between almost surely and surely (that is, entirely certain to happen) in many basic probability experiments, the distinction is important in more complex cases relating to some sort of infinity
Infinity
Infinity is a concept in many fields, most predominantly mathematics and physics, that refers to a quantity without bound or end. People have developed various ideas throughout history about the nature of infinity...
. For instance, the term is often encountered in questions that involve infinite time, regularity properties or infinite-dimension
Dimension
In physics and mathematics, the dimension of a space or object is informally defined as the minimum number of coordinates needed to specify any point within it. Thus a line has a dimension of one because only one coordinate is needed to specify a point on it...
al spaces such as function space
Function space
In mathematics, a function space is a set of functions of a given kind from a set X to a set Y. It is called a space because in many applications it is a topological space, a vector space, or both.-Examples:...
s. Basic examples of use include the law of large numbers
Law of large numbers
In probability theory, the law of large numbers is a theorem that describes the result of performing the same experiment a large number of times...
(strong form) or continuity of Brownian paths
Brownian motion
Brownian motion or pedesis is the presumably random drifting of particles suspended in a fluid or the mathematical model used to describe such random movements, which is often called a particle theory.The mathematical model of Brownian motion has several real-world applications...
.
Almost never describes the opposite of almost surely; an event which happens with probability zero happens almost never.
Formal definition
Let (Ω, F, P) be a probability spaceProbability space
In probability theory, a probability space or a probability triple is a mathematical construct that models a real-world process consisting of states that occur randomly. A probability space is constructed with a specific kind of situation or experiment in mind...
. One says that an event
Event (probability theory)
In probability theory, an event is a set of outcomes to which a probability is assigned. Typically, when the sample space is finite, any subset of the sample space is an event...
E in F happens almost surely if P(E) = 1.
Equivalently, we can say an event E happens almost surely if the probability of E not occurring is zero
0 (number)
0 is both a numberand the numerical digit used to represent that number in numerals.It fulfills a central role in mathematics as the additive identity of the integers, real numbers, and many other algebraic structures. As a digit, 0 is used as a placeholder in place value systems...
.
An alternative definition from a measure theoretic
Measure (mathematics)
In mathematical analysis, a measure on a set is a systematic way to assign to each suitable subset a number, intuitively interpreted as the size of the subset. In this sense, a measure is a generalization of the concepts of length, area, and volume...
-perspective is that (since P is a measure over Ω) E happens almost surely if E = Ω almost everywhere
Almost everywhere
In measure theory , a property holds almost everywhere if the set of elements for which the property does not hold is a null set, that is, a set of measure zero . In cases where the measure is not complete, it is sufficient that the set is contained within a set of measure zero...
.
"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, and no outcome not in this event can possibly occur. If an event is almost sure, then outcomes not in this event are theoretically possible; however, the probability of such an outcome occurring is smaller than any fixed positive probability, and therefore must be 0. Thus, one cannot definitively say that these outcomes will never occur, but can for most purposes assume this to be true.
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 proportional 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, therefore theoretically it is possible that the dart actually hits the diagonal.
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 event would not occur, but rather almost certain.
Tossing a coin
Suppose that an "ideal" (edgeless) fair coinFair coin
In probability theory and statistics, a sequence of independent Bernoulli trials with probability 1/2 of success on each trial is metaphorically called a fair coin. One for which the probability is not 1/2 is called a biased or unfair coin...
is flipped again and again. A coin has two sides, head and tail, and therefore the event that "head or tail 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
Ad infinitum
Ad infinitum is a Latin phrase meaning "to infinity."In context, it usually means "continue forever, without limit" and thus can be used to describe a non-terminating process, a non-terminating repeating process, or a set of instructions to be repeated "forever," among other uses...
, is possible in some sense (it does not violate any physical or mathematical laws to suppose that tails never appear), but it is very, very improbable. In fact, the probability of tail never being flipped in an infinite series is zero. Thus, though we cannot definitely say tail will be flipped at least once, we can say there will almost surely be at least one tail in an infinite sequence of flips. (Note that given the statements made in this paragraph, any predefined ordering would have zero-probability in an infinite series. This makes sense because there are an infinite number of possibilities and
.)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 at least one tail is 1 − 2−1,000,000 < 1, and the event is no longer almost sure.
Asymptotically almost surely
In asymptotic analysisAsymptotic analysis
In mathematical analysis, asymptotic analysis is a method of describing limiting behavior. The methodology has applications across science. Examples are...
, 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
Composite number
A composite number is a positive integer which has a positive divisor other than one or itself. In other words a composite number is any positive integer greater than one that is not a prime number....
, by the prime number theorem
Prime number theorem
In number theory, the prime number theorem describes the asymptotic distribution of the prime numbers. The prime number theorem gives a general description of how the primes are distributed amongst the positive integers....
; and in random graph theory
Random graph
In mathematics, a random graph is a graph that is generated by some random process. The theory of random graphs lies at the intersection between graph theory and probability theory, and studies the properties of typical random graphs.-Random graph models:...
, the statement "G(n,pn) is connected
Connectivity (graph theory)
In mathematics and computer science, connectivity is one of the basic concepts of graph theory: it asks for the minimum number of elements which need to be removed to disconnect the remaining nodes from each other. It is closely related to the theory of network flow problems...
" (where G(n,p)
Erdos–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 edges...
denotes the graphs on n vertices with edge probability p) is true a.a.s when pn >
for any ε > 0.In number theory
Number theory
Number theory is a branch of pure mathematics devoted primarily to the study of the integers. Number theorists study prime numbers as well...
this is referred to as "almost all
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" or "all but a countable set" ; see almost....
", as in "almost all numbers are composite". Similarly, in graph theory, this is sometimes referred to as "almost surely".
See also
- Convergence of random variablesConvergence of random variablesIn 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 statistics and stochastic processes...
, for "almost sure convergence" - Degenerate distribution, for "almost surely constant"
- Almost everywhereAlmost everywhereIn measure theory , a property holds almost everywhere if the set of elements for which the property does not hold is a null set, that is, a set of measure zero . In cases where the measure is not complete, it is sufficient that the set is contained within a set of measure zero...
, the corresponding concept in measure theory - Infinite monkey theoremInfinite monkey theoremThe infinite monkey theorem states that a monkey hitting keys at random on a typewriter keyboard for an infinite amount of time will almost surely type a given text, such as the complete works of William Shakespeare....
, a theorem using the aforementioned terms.