With high probability

From Algorithmist
Jump to: navigation, search

[edit] Definition

An event occurs with high probability if, for any \alpha \geq 1, the event occurs with probability at least 1 - \frac{c_\alpha}{n^\alpha}, where cα depends only on α.

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

[edit] Example

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 1 - \frac{c_\alpha}{n^\alpha}, where cα depends only on α.

Personal tools
Namespaces
Variants
Actions
Navigation
Toolbox