With high probability

From Algorithmist
Jump to navigation Jump to search

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 .