The traditional way to prove the existence of a desirable object is to construct it explicitly. However, in many cases, finding explicit constructions can be very hard. One can overcome this difficulty by creating a probabilistic space in which the desirable object can be shown to have positive probability. A good example is the Ramsey problem. By a probabilistic argument it is very easy to show the existence of 2-coloring of the edges of the complete graph on n vertices so that the largest monochromatic clique has size O(log n)  However, despite the effort of many prominent mathematicians in the last 60 years or so, no explicit construction is known.

Some representative publications:

(1) On a refinement of Waring’s problem, Duke Math. Journal,105, (1 )(2000).

Waring asserts that for any fixed r and k sufficiently large compared to r, any large natural number n can be written as sum of k rth powers (such as sum of four squares, nine cubes and so on). In other words, the set of all rth powers is a base of order k; this is known as the classical Waring problem. 

But do we really need all the rth powers ? The answer is NO, a small fraction is sufficient. By a probabilistic argument, we showed that there exists a subsequence of rth powers of density C (n log n)^{1/k} that already forms a base of order k. This density is optimal up to the logarithmic term. No explicit construction is known.

In the paper, we take k roughly 2^r. Wooley extends the theorem to k as small as C r log r, which is the state of the art of the Waring problem.

(2) (with J.H. Kim) Small complete arcs in projective planes, Combinatorica, 23 (2003), no. 2,311–363.

In the 1950s, italian geometer B. Segre introduced the notion of arc in a projective plane. An arc is a set with no three collinear points. An arc is complete if it cannot be extended. It is easy to show that in a plane of order q, one cannot have a complete arc of more than
q+2 points, and there are various constructions matching this bound, which lead to the important notion of ovals and hyper ovals. The lower bound is much harder. A simple double counting argument shows that any complete arc should have at least c q^{1/2} elements, for some constant c, but there are only few construction matching this bound (by Szonyi, for instance) for special classes of planes. In PG(2,q) (the most basic plane build on the finite field of order q), the best explicit construction is of order q^{3/4} (Szonyi).

By a probabilistic construction, we show that there exists complete arc with at most q^{1/2} log^C q points, where C is a positive constant. This is sharp up to the logarithmic term. It is a tantalizing open question to determine whether the log term is needed.

The probabilistic construction is given by a fast probabilistic algorithm which succeeds with probability close to 1, so it is effective in the algorithmic sense.