# Difference between revisions of "With high probability"

From Algorithmist

(O as lower bound makes no sense. Omega is needed here.) |
(→Example: latex) |
||

Line 4: | Line 4: | ||

Since we can choose <math>\alpha</math>, we can make the probability arbitrarily low, at a cost of time and/or space. | Since we can choose <math>\alpha</math>, we can make the probability arbitrarily low, at a cost of time and/or space. | ||

== Example == | == Example == | ||

− | With high probability, a set of N random numbers will contain at least <math>\Omega | + | With high probability, a set of N random numbers will contain at least <math>\Omega</math>(N) evens. |

What it means is: For any <math>\alpha</math>, there exists a k (that doesn't depend on N), such that a set of N random numbers will contain at least k*N evens with probability <math>1 - \frac{c_\alpha}{n^\alpha}</math>, where <math>c_\alpha</math> depends only on <math>\alpha</math>. | What it means is: For any <math>\alpha</math>, there exists a k (that doesn't depend on N), such that a set of N random numbers will contain at least k*N evens with probability <math>1 - \frac{c_\alpha}{n^\alpha}</math>, where <math>c_\alpha</math> depends only on <math>\alpha</math>. | ||

[[Category:Randomized Algorithms]] | [[Category:Randomized Algorithms]] |

## Latest revision as of 08:51, 3 April 2014

## Definition[edit]

An event occurs **with high probability** if, for any , the event occurs with probability at least , where depends only on .

Since we can choose , we can make the probability arbitrarily low, at a cost of time and/or space.

## Example[edit]

With high probability, a set of N random numbers will contain at least (N) evens.

What it means is: For any , there exists a k (that doesn't depend on N), such that a set of N random numbers will contain at least k*N evens with probability , where depends only on .