Open main menu

In probability theory, an event is said to happen almost surely (sometimes abbreviated as a.s.) if it happens with probability 1 (or Lebesgue measure 1).[1][2] In other words, the set of possible exceptions may be non-empty, but it has probability 0. The concept is essentially analogous to the concept of "almost everywhere" in measure theory.

In probability experiments on a finite sample space, there is often no difference between almost surely and surely (since having a probability of 1 often entails including all the sample points). However, this distinction becomes important when the sample space is an infinite set,[3] because an infinite set can have non-empty subsets of probability 0.

Some examples of the use of this concept include the strong and uniform versions of the law of large numbers, and the continuity of the paths of Brownian motion.

The terms almost certainly (a.c.) and almost always (a.a.) are also used. Almost never describes the opposite of almost surely: an event that happens with probability zero happens almost never.[1][4]

Formal definitionEdit

Let   be a probability space. An event   happens almost surely if  . Equivalently,   happens almost surely if the probability of   not occurring is zero:  . More generally, any event   (not necessarily in  ) happens almost surely if   is contained in a null set: a subset   in   such that  .[5] The notion of almost sureness depends on the probability measure  . If it is necessary to emphasize this dependence, it is customary to say that the event   occurs P-almost surely, or almost surely  .

Illustrative examplesEdit

In general, an event can happen "almost surely", even if the probability space in question includes outcomes which do not belong to the event— as the following examples illustrate.

Throwing a dartEdit

Imagine throwing a dart at a unit square (i.e. a square with area 1) so that the dart always hits an exact point in the square, in such a way that each point in the square is equally likely to be hit.

Now, notice that since the square has area 1, the probability that the dart will hit any particular subregion of the square is equal to the area of that subregion. For example, the probability that the dart will hit the right half of the square is 0.5, since the right half has area 0.5.

Next, consider the event that "the dart hits exactly a point in the diagonals of the unit square". Since the area of the diagonals of the square is 0, the probability that the dart will land exactly on a diagonal is 0. That is, the dart will almost never land on a diagonal (equiv., it will almost surely not land on a diagonal), even if the set of points on the diagonals is not empty, and a point on a diagonal is no less possible than any other point (after all, the diagonal does contain valid outcomes of the experiment).

Tossing a coin repeatedlyEdit

Consider the case where a (possibly biased) coin is tossed, corresponding to the probability space  , where the event   occurs if a head is flipped, and   if a tail is flipped. For this particular coin, we assume that the probability of flipping a head is  , from which it follows that the complement event, that of flipping a tail, has probability  .

Now, suppose that we were to conduct an experiment where the coin is tossed repeatedly, with outcomes   and the assumption that each flip's outcome is independent of all the others (i.e., they are i.i.d.). Define the sequence of random variables on the coin toss space,   where  . i.e. each   records the outcome of the  th flip.

In this case, any infinite sequence of heads and tails is a possible outcome of the experiment. However, any particular infinite sequence of heads and tails has probability 0 of being the exact outcome of the (infinite) experiment. To see why, note that the i.i.d. assumption implies that the probability of flipping all heads over   flips is simply  . Letting   yields 0, since   by assumption. Note that the result is the same no matter how much we bias the coin towards heads, so long as we constrain   to be strictly between 0 and 1. In fact, the same result even holds in non-standard analysis—where infinitesimal probabilities are not allowed.[6]

Moreover, the event "the sequence of tosses contains at least one  " will also happen almost surely (i.e., with probability 1). But if instead of an infinite number of flips, we stop flipping after some finite time, say 1,000,000 flips, then the probability of getting an all-heads sequence,  , would no longer be 0, while the probability of getting at least one tails,  , would no longer be 1 (i.e., the event is no longer almost sure).

Asymptotically almost surelyEdit

In asymptotic analysis, a property is said to hold asymptotically almost surely (a.a.s.), if over a sequence of sets, the probability converges to 1. For instance, in number theory, a large number is asymptotically almost surely composite, by the prime number theorem; and in random graph theory, the statement "  is connected" (where   denotes the graphs on   vertices with edge probability  ) is true a.a.s. when, for some  

    [7]

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".[8]

See alsoEdit

NotesEdit

  1. ^ a b "The Definitive Glossary of Higher Mathematical Jargon — Almost". Math Vault. 2019-08-01. Retrieved 2019-11-16.
  2. ^ Weisstein, Eric W. "Almost Surely". mathworld.wolfram.com. Retrieved 2019-11-16.
  3. ^ "Almost surely - Math Central". mathcentral.uregina.ca. Retrieved 2019-11-16.
  4. ^ Grädel, Erich; Kolaitis, Phokion G.; Libkin, Leonid; Marx, Maarten; Spencer, Joel; Vardi, Moshe Y.; Venema, Yde; Weinstein, Scott (2007). Finite Model Theory and Its Applications. Springer. p. 232. ISBN 978-3-540-00428-8.
  5. ^ Jacod, Jean; Protter, (2004). Probability Essentials. Springer. p. 37. ISBN 978-3-540-438717.CS1 maint: extra punctuation (link)
  6. ^ Williamson, Timothy (2007-07-01). "How probable is an infinite sequence of heads?". Analysis. 67 (3): 173–180. doi:10.1093/analys/67.3.173. ISSN 0003-2638.
  7. ^ Friedgut, Ehud; Rödl, Vojtech; Rucinski, Andrzej; Tetali, Prasad (January 2006). "A Sharp Threshold for Random Graphs with a Monochromatic Triangle in Every Edge Coloring". Memoirs of the American Mathematical Society. AMS Bookstore. 179 (845): 3–4. ISSN 0065-9266.
  8. ^ Spencer, Joel H. (2001). "0. Two Starting Examples". The Strange Logic of Random Graphs. Algorithms and Combinatorics. 22. Springer. p. 4. ISBN 978-3540416548.

ReferencesEdit

  • Rogers, L. C. G.; Williams, David (2000). Diffusions, Markov Processes, and Martingales. 1: Foundations. Cambridge University Press. ISBN 978-0521775946.
  • Williams, David (1991). Probability with Martingales. Cambridge Mathematical Textbooks. Cambridge University Press. ISBN 978-0521406055.