With high probability

From Algorithmist
Revision as of 07:46, 3 April 2014 by 134.61.167.138 (Talk) (O as lower bound makes no sense. Omega is needed here.)

Jump to: navigation, search

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_{\alpha } depends only on \alpha .

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

Example

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

What it means is: For any \alpha , 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_{\alpha } depends only on \alpha .