{"id":8676,"date":"2014-12-07T13:44:04","date_gmt":"2014-12-07T21:44:04","guid":{"rendered":"http:\/\/algnotes.info\/b\/?page_id=8676"},"modified":"2023-09-14T17:14:48","modified_gmt":"2023-09-15T01:14:48","slug":"background","status":"publish","type":"page","link":"https:\/\/algnotes.info\/on\/background\/","title":{"rendered":"Misc. background material"},"content":{"rendered":"
\n
\n
\n
\n

Misc. background material.<\/em><\/center><\/p><\/blockquote>\n

\u00a0<\/p>\n<\/div>\n<\/div>\n

\n
\n
\n

Excerpts<\/h1>\n
\r\n
\r\n

\r\nProbabilistic method<\/a>\r\n<\/h1>\r\n<\/header>\r\n
\r\n

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

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

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> <\/blockquote>

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>

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

\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> <\/blockquote>

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