"With high
probability" (often abbreviated w.h.p.) is a
mathematical concept common to
computer science. It generally refes to a statement of the form:
With high probability, a set of N random numbers will contain at least O(N) evens.
What it means is:
For any p, there exists a k, such that a set of N random numbers will contain at least k N evens with probability 1 - C / np, where C depends only on p.
In less mathematically precise terms, the idea is that you can change the conditions slightly to make the probability of failure very very small.
The usefulness of this concept is from the power of the statement. The statement is parameterized to allow the probability to vary as necessary to prove other statements. Proving the first couple things in terms of "with high probability" may be a bit tedious, but it allows you to lax about proving other things. You can rely on picking a large enough p to make your statement simple to prove.