{"id":901,"date":"2010-04-04T18:07:19","date_gmt":"2010-04-05T02:07:19","guid":{"rendered":"http:\/\/obliviousrounding.com\/blog\/?p=901"},"modified":"2026-09-30T09:15:58","modified_gmt":"2026-09-30T17:15:58","slug":"probabilistic-method","status":"publish","type":"page","link":"https:\/\/algnotes.info\/on\/background\/probabilistic-method\/","title":{"rendered":"Probabilistic method"},"content":{"rendered":"
\n
\n
\n
\n

A brief introduction to the probabilistic method, followed by some basic bounds and a few examples.<\/em><\/center><\/p><\/blockquote>\n

Alon, Spencer, and Erd\u0151s (1992) describe the method as follows: <\/p>\n

In order to prove the existence of a combinatorial structure with certain properties, we construct an appropriate probability space and show that a randomly chosen element in the space has the desired properties with positive probability.<\/em>[1<\/a>]<\/span> <\/p><\/blockquote>\n

The method has come into wide use since about 1950, even in areas of mathematics that, a-priori, have nothing to do with probability. This is roughly because probability provides a useful high-level conceptual framework for understanding (formalizing, organizing, communicating) many widely applicable counting and averaging arguments. This probabilistic viewpoint is called the probabilistic lens<\/em>. <\/p>\n

Alon et al. note that, although in principle<\/em> analysis with the probabilistic method can be replaced by direct arguments, <\/p>\n

\u2026in practice, the probability is essential. It would be hopeless to replace the applications of many of the tools [by counting arguments].\u00a0[1<\/a>, page 2]<\/span><\/em> <\/p><\/blockquote>\n

In Computer Science, the method is used in randomized rounding<\/a>, to design approximation algorithms for combinatorial optimization problems.<\/p>\n

<\/div>\n<\/p>\n
\n
\n
\nClick for background material\u2026<\/summary>\n
\n