With high probability

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$.