What is the easiest randomized algorithm to motivate to the layperson? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-19T18:36:59Z http://mathoverflow.net/feeds/question/38245 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/38245/what-is-the-easiest-randomized-algorithm-to-motivate-to-the-layperson What is the easiest randomized algorithm to motivate to the layperson? miforbes 2010-09-09T23:27:17Z 2012-01-07T14:57:07Z <p>When trying to explain complexity theory to laypeople, I often mention randomized algorithms but seemingly lack good examples to motivate their usage. I often want to mention primality testing but the standard randomized algorithms don't admit a simple description (or proof of correctness) in a lay-atmosphere. I often resort to the saying that randomized algorithms allow "finding hay in a haystack", but that has little mathematical substance. </p> <p>The question: Is there a good example of a problem that:</p> <ul> <li><p>is easily explained (and sufficiently interesting)</p></li> <li><p>has a simple randomized algorithm</p></li> <li><p>appears non-trivial to get an efficient deterministic algorithm</p></li> </ul> <p>and ideally also satisfies:</p> <ul> <li>the randomized algorithm has a somewhat understandable proof of correctness - so no Markov/Chernoff/random-walk-mixing-times</li> </ul> http://mathoverflow.net/questions/38245/what-is-the-easiest-randomized-algorithm-to-motivate-to-the-layperson/38248#38248 Answer by Robin Kothari for What is the easiest randomized algorithm to motivate to the layperson? Robin Kothari 2010-09-09T23:47:08Z 2010-09-09T23:47:08Z <p>I like the non-technical examples given by Anup Rao in this essay: <a href="http://docs.google.com/Doc?id=dq6zxpq_473cvj8ggfx" rel="nofollow">http://docs.google.com/Doc?id=dq6zxpq_473cvj8ggfx</a></p> <p>It's available from <a href="http://www.cs.washington.edu/homes/anuprao/index.html" rel="nofollow">his website</a></p> <p>He gives two example of randomized algorithms, one of them is an example of an interactive proof system with the zero knowledge property.</p> http://mathoverflow.net/questions/38245/what-is-the-easiest-randomized-algorithm-to-motivate-to-the-layperson/38251#38251 Answer by Louigi Addario-Berry for What is the easiest randomized algorithm to motivate to the layperson? Louigi Addario-Berry 2010-09-10T00:39:39Z 2010-09-10T00:39:39Z <p>If you're willing to flex a bit on "non-trivial to get an efficient deterministic algorithm" (or at least on the definition of "non-trivial"), max-cut is a very easy one. Given a graph $G=(V,E)$, the aim is to partition $V$ into $(V_1,V_2)$ to maximize the number of edges between $V_1$ and $V_2$. Picking a random partition into sets of equal size -- up to parity -- gives you something that on average has at least half the edges of the graph, so is on average at least halfway to optimal. </p> <p>This example is also nice in my view because the <a href="http://portal.acm.org/citation.cfm?doid=195058.195216" rel="nofollow">Goemans--Williamson algorithm</a>, the algorithm achieving the best-known approximation ratio (and best possible assuming a certain complexity result) for the problem, about 0.878, is also randomized. (It can be derandomized using the method of conditional expectations, but at a fair cost in terms of ease of explanation.)</p> http://mathoverflow.net/questions/38245/what-is-the-easiest-randomized-algorithm-to-motivate-to-the-layperson/38259#38259 Answer by Artem Kaznatcheev for What is the easiest randomized algorithm to motivate to the layperson? Artem Kaznatcheev 2010-09-10T01:48:59Z 2011-05-03T15:03:46Z <p>If you are willing to sacrifice the non-trivial deterministic requirement, then I would suggest the <a href="http://en.wikipedia.org/wiki/Deutsch%E2%80%93Jozsa_algorithm" rel="nofollow">Deutsch-Jozsa problem</a>. To summarize: you are given a black-box $f: {0,1}^n \rightarrow {0,1}$ it is promised that either $f$ is constant or balanced (i.e. $|f^{-1}(0)| = |f^{-1}(1)|$). You have to tell me which it is. The randomized algorithm works exponentially faster than the deterministic one, and has small error.</p> <p>The best feature is that if you want to continue and mention quantum algorithms, you can do so to recover an error-less algorithm.</p> http://mathoverflow.net/questions/38245/what-is-the-easiest-randomized-algorithm-to-motivate-to-the-layperson/38270#38270 Answer by Suresh Venkat for What is the easiest randomized algorithm to motivate to the layperson? Suresh Venkat 2010-09-10T05:30:14Z 2010-09-10T05:30:14Z <p>While this requires the use of approximation as well as randomization, I always find the idea that you can get a good estimate of a population by sampling a constant sized set to be very non-intuitive and powerful. The way I usually phrase it in class is: you want to poll the population so that any reasonably popular group is represented. If "reasonably" popular" is defined as a constant fraction, then you only need to sample a <strong>constant number of people</strong> to hit all groups. Judging by how the general population gets confused by polls, this seems like a good example. </p> <p>Another example that's more useful for a "CS-aware" layperson is one that requires knowledge of the notion of a median. You can get a quick and dirty approximation for the median in <strong>constant</strong> time by sampling (in fact, the median of THREE random elements suffices), and the more you sample, the better the approximation. </p> <p>Probably the most spectacular demonstration of the power of randomness, but one alas that isn't easy to prove to a layman, <a href="http://www.eecs.harvard.edu/~michaelm/postscripts/handbook2001.pdf" rel="nofollow">is the power of two choices</a>. It seems almost impossible that it's true, but it is. </p> http://mathoverflow.net/questions/38245/what-is-the-easiest-randomized-algorithm-to-motivate-to-the-layperson/38271#38271 Answer by Alon Amit for What is the easiest randomized algorithm to motivate to the layperson? Alon Amit 2010-09-10T05:54:48Z 2010-09-10T05:54:48Z <p>I sometimes mention the efficient generation of expander graphs. In layspeak, an expander graph is "a network where every node is connected to say only 5 other nodes, but you have to cut a million such connections in order to separate two substantial portions of the network from each other". It is possible to generate large expander graphs explicitly, but this is very far from trivial (see Lubotzky, Phillips and Sarnak); on the other hand, in an appropriate sense, a random large network is amazingly good.</p> <p>(how do you make a random network with 5 neighbors per node? start by imagining that each node is made up of 5 pebbles, pair up the pebbles randomly, and merge the pebbles into nodes). </p> <p>This is an algorithm-to-generate, not an algorithm-to-decide, but this shouldn't cause too much trouble with most layfolks. </p> http://mathoverflow.net/questions/38245/what-is-the-easiest-randomized-algorithm-to-motivate-to-the-layperson/38277#38277 Answer by Roland Bacher for What is the easiest randomized algorithm to motivate to the layperson? Roland Bacher 2010-09-10T07:33:16Z 2010-09-10T07:33:16Z <p>Why not mention evolution? It looks very similar to a (still running) random algorithm and its current output does not seem without interest.</p> http://mathoverflow.net/questions/38245/what-is-the-easiest-randomized-algorithm-to-motivate-to-the-layperson/38279#38279 Answer by Henry Yuen for What is the easiest randomized algorithm to motivate to the layperson? Henry Yuen 2010-09-10T08:12:07Z 2010-09-10T08:12:07Z <p>I love the following example: approximating pi. Ask a person to come up with a relatively efficient algorithm to compute the digits of pi, and unless they already know some math, most will draw a blank. </p> <p>Here's something that anybody with a basic geometry background will understand: Simply generate many random 2D points (x,y) in the box [-1,1]x[-1,1], and count the number of points within distance 1 of 0 (call this number A) and the number of points in the box total (call this number T).</p> <p>You can then approximate pi with $\pi r^2 /4r^2 \approx A/T$, but $r=1$, so $\pi \approx 4A/T$. </p> http://mathoverflow.net/questions/38245/what-is-the-easiest-randomized-algorithm-to-motivate-to-the-layperson/38281#38281 Answer by Grönwall for What is the easiest randomized algorithm to motivate to the layperson? Grönwall 2010-09-10T08:37:35Z 2010-09-10T08:37:35Z <p>I'm not an expert, but I know that for path planning randomized algorithms are very good, and that good deterministic algorithms are very hard to come by. The advantage being that the path planning problem should be easy to explain to lay people.</p> http://mathoverflow.net/questions/38245/what-is-the-easiest-randomized-algorithm-to-motivate-to-the-layperson/38282#38282 Answer by Ricky Demer for What is the easiest randomized algorithm to motivate to the layperson? Ricky Demer 2010-09-10T08:41:51Z 2010-09-10T08:41:51Z <p>Input: n</p> <p>.</p> <p>Output:</p> <p>a quadratic nonresidue mod n, if n is an odd prime</p> <p>0, otherwise</p> <p>.</p> <p>.</p> <p>According to <a href="http://docs.google.com/viewer?a=v&amp;q=cache:Frx9w_Bcqo8J:arxiv.org/pdf/math/0502214+deterministic+quadratic+nonresidue&amp;hl=en&amp;gl=us&amp;pid=bl&amp;srcid=ADGEESh34pmQ1Z03L-cOoQGPVS32PaaqyDxUPUHe51KDJ2LNS-oePI_oFV9evwypGcE-rztfHC2UplriwbNM4hnOjZkDzyxgnpJ4VzCGXMhzGKp7n9dC_ehb0yXxFnh1-AxEBi8nZGOf&amp;sig=AHIEtbT_wVTw8C_5kQEmjaORNa8rRm2JVg" rel="nofollow">this article</a>, there is a known deterministic polynomial time algorithm for it, although the randomized algorithm really is "searching for hay in a haystack". Furthermore, the article is either wrong or poorly enough known that wikipedia is unaware of it.</p> http://mathoverflow.net/questions/38245/what-is-the-easiest-randomized-algorithm-to-motivate-to-the-layperson/38298#38298 Answer by Scott Aaronson for What is the easiest randomized algorithm to motivate to the layperson? Scott Aaronson 2010-09-10T12:35:43Z 2010-09-10T12:35:43Z <p>Michael, how about approximating the volume of some shape in $\Re^n$ by sampling random points?</p> <p>This example has the following advantages:</p> <ul> <li><p>It seems easy enough to explain at a cocktail party (depending, of course, on the guests).</p></li> <li><p>It's used constantly in "real life" (indeed, pretty much any Monte Carlo simulation in physics, etc. could be interpreted as solving this problem).</p></li> <li><p>We don't know how to derandomize it. Indeed, the problem is easily seen to be PromiseBPP-complete (assuming of course that whether a point $x \in \Re^n$ belongs to the shape is decidable in polynomial time).</p></li> </ul> http://mathoverflow.net/questions/38245/what-is-the-easiest-randomized-algorithm-to-motivate-to-the-layperson/38373#38373 Answer by avr-white for What is the easiest randomized algorithm to motivate to the layperson? avr-white 2010-09-11T01:07:06Z 2010-09-11T01:07:06Z <p>Ant algorithms to determine and select the best path from one place to another; ant algorithms can also be used to select the goals along with the paths.</p> <p>Ant trails and pheremones are easy to describe. Every one has seen them and it's fascinating to explain how miniscule ant-brains can carry out a parallel distributed algorithm that can also be used to select the best routing path on the internet or for a quick and dirty solution to the traveling salesman problem.</p> http://mathoverflow.net/questions/38245/what-is-the-easiest-randomized-algorithm-to-motivate-to-the-layperson/57342#57342 Answer by none for What is the easiest randomized algorithm to motivate to the layperson? none 2011-03-04T11:14:45Z 2011-03-04T11:14:45Z <p>Nobody has mentioned the Solovay-Strassen primality test? It's easy to explain (at least with handwaving) that the Jacobi symbol and the modular exponential are straightforward to compute. Then for odd prime n, $a^{(n-1)/2}\equiv \big({a\over n}\big)$ for all bases a, but for composite n, the equality doesn't hold for at least half the bases. So you choose bases at random until you find a compositeness witness or satisfy yourself that you're not going to find one (probability $\le 2^{-k}$ after k tests). I think this was one of the earliest ones? It's very easy to motivate and understand IMHO.</p> http://mathoverflow.net/questions/38245/what-is-the-easiest-randomized-algorithm-to-motivate-to-the-layperson/63846#63846 Answer by Alex R. for What is the easiest randomized algorithm to motivate to the layperson? Alex R. 2011-05-03T20:32:20Z 2011-05-03T20:38:14Z <p>How about using Monte Carlo for deciphering encrypted messages? <a href="http://www.scribd.com/doc/36753044/Diaconis-P-the-Markov-Chain-Monte-Carlo-Revolution" rel="nofollow">This</a> paper by Diaconis deciphers a prison message that involves prison lingo, multiple languages, bad spelling and centers around a prison slashing. The younger TV-detective-show obsessed crowd will love it. The algorithm is very simple. Showing precise rate-of-convergence estimates is a bit if a mixing time problem, but perhaps they can take it on faith?</p> <p>I remember reading it a while ago and feeling inspired by random algorithms. I'll be honest I know very little cryptography, but it seems to me that the given problem in the reference can ONLY be solved by a randomized algorithm. The fact that it converges so quickly and even has a moderate window for "data corruption" (such as bad spelling and different languages) really makes you appreciate the power of this stuff.</p> http://mathoverflow.net/questions/38245/what-is-the-easiest-randomized-algorithm-to-motivate-to-the-layperson/63872#63872 Answer by Zen Harper for What is the easiest randomized algorithm to motivate to the layperson? Zen Harper 2011-05-04T03:50:05Z 2011-05-06T00:46:21Z <p>[<strong>EDIT: disclaimer! I probably shouldn't have posted this answer, because it's nowhere near my area of expertise; so beware, it may contain nonsense!</strong>]</p> <p>[<strong><em>EDIT: sorry; I saw this nice problem in a book, but it seems a nice deterministic algorithm in $O(n (\log n)^4)$ time was found later, so this answer is inapplicable; reference:</em></strong></p> <p><em>Matching nuts and bolts</em> by Noga Alon, Manuel Blum, Amos Fiat, Sampath Kannan, Moni Naor, Rafail Ostrovsky;</p> <p>citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.103 ]</p> <p>The "nuts and bolts" problem, which I saw just a few days ago in the Algorithm Design Manual [precise reference to follow when I get time to edit]:</p> <p>You are given $n$ pairs of nuts and bolts, all very slightly different sizes (so, each nut fits exactly one bolt); but unfortunately they have all been disassembled, and you have to fit them together.</p> <p>You cannot see the difference in size by eye, so the only way to see if a nut fits a bolt is to try it. If a nut is too large/small for a bolt, you will discover this; but note that <em>you can't compare two nuts, or two bolts, with each other directly</em>.</p> <p>Abstractly: we have 2 real unknown sequences $(x_1, x_2, \ldots, x_n)$ and $(y_1, y_2, \ldots, y_n)$.</p> <p>The $x_i$ are all distinct, and $(y_j)$ is an unknown rearrangement of $(x_i)$. We want to match them up, but the ONLY measurement we can make is to pick $i,j$ and compare $x_i$ with $y_j$.</p> <p>The obvious algorithm of trying all of them one-by-one takes $O(n^2)$ time.</p> <p>However, a variant of <em>randomised</em> quicksort takes $O(n \log n)$ time on average. The randomness just comes from picking each nut/bolt at random.</p> <p>Details: pick a <em>nut</em>, use that as the pivot element for the <em>bolts</em>; then use the matching <em>bolt</em> as the pivot element for the <em>nuts</em>, etc. - like quicksort, but going back-and-forth between $x$ and $y$ elements.</p> http://mathoverflow.net/questions/38245/what-is-the-easiest-randomized-algorithm-to-motivate-to-the-layperson/63885#63885 Answer by Per Alexandersson for What is the easiest randomized algorithm to motivate to the layperson? Per Alexandersson 2011-05-04T06:20:50Z 2011-05-04T06:20:50Z <p>I would say that the flame fractal algorithm is a monte-carlo way of approximating the invariant measure of a Hutchinson operator. Easy to explain in laymans terms, and produces pretty pictures.</p> http://mathoverflow.net/questions/38245/what-is-the-easiest-randomized-algorithm-to-motivate-to-the-layperson/64358#64358 Answer by Manfred Sauter for What is the easiest randomized algorithm to motivate to the layperson? Manfred Sauter 2011-05-09T07:12:13Z 2011-05-09T07:12:13Z <p>This suggestion is not quite as good as Scott Aaronson's, but the following expected time $O(n)$ algorithm for the smallest enclosing circle (also known as minimum spanning/covering circle/disc) of a set of $n$ points in the plane definitely meets the requirements.</p> <p><strong>Problem:</strong> Given are $n$ points in the plane, $p_1,\dotsc,p_n$. Find the circle of minimal radius that encloses all those points, i.e., all points are in the interior or on the boundary of that smallest circle.</p> <p><strong>Algorithm:</strong> The algorithm itself was introduced in the following article:</p> <blockquote> <p>Emo Welzl, <a href="http://dx.doi.org/10.1007/BFb0038202" rel="nofollow">Smallest enclosing disks (balls and ellipsoids)</a>. New results and new trends in computer science (Graz, 1991), 359–370, Lecture Notes in Comput. Sci., 555, Springer, Berlin, 1991.</p> </blockquote> <p>The document is accessible <a href="http://citeseer.ist.psu.edu/viewdoc/download;?doi=10.1.1.46.1450&amp;rep=rep1&amp;type=pdf" rel="nofollow">via CiteSeer</a>.</p> <p>Let $P$ and $R$ be finite sets of points, possibly empty. We describe a recursive procedure $MD(P,R)$ that tries to compute the smallest circle that encloses $P$ and such that all points in $R$ lie on the boundary. Of course, in general such a circle need not exist (say $R$ contains more than 4 points that are not cocircular or the points of $R$ are strictly in the inside of the convex hull of $P$). Note that a circle is already determined by any 3 distinct points on its boundary. Anyhow, that will not be a problem as we call the procedure only for $R=\emptyset$ and $P=\{p_1,\dotsc,p_n\}$. </p> <blockquote> <p>Definition of $MD(P,R)$:</p> <p>If $P=\emptyset$ or $\operatorname{card}(R)=3$, then directly calculate and return $MD(\emptyset,R)$.<br> Otherwise, take a random point $p\in P$ and recursively calculate $D:=MD(P\setminus\{p\},R)$.<br> If $p$ is enclosed by $D$, return $D$.<br> Otherwise, return the recursively calculated $MD(P\setminus\{p\},R\cup\{p\})$.</p> </blockquote> <p>It is possible to cast this in a short and efficient iterative computer program. Regarding the randomization, it actually suffices to randomly shuffle the points only once. Also note that the method can be generalized to higher dimensions and ellipses.</p> <p><strong>Deterministic algorithms:</strong> The obvious try-every-circle brute-force algorithm runs in $O(n^4)$. It is not hard to come up with some improvements, but starting by calculating the convex hull first already results in $O(n\log n)$ at best (at least in usual models of computation). Anyhow, there exist deterministic optimal $O(n)$ algorithms, but they are (as far as I know) quite involved and not used in practice. See <a href="http://en.wikipedia.org/wiki/Smallest_circle_problem" rel="nofollow">Wikipedia</a> or this <a href="http://www.personal.kent.edu/~rmuhamma/Compgeometry/MyCG/CG-Applets/Center/centercli.htm" rel="nofollow">webpage</a> by Rashid Bin Muhammad.</p> <p><strong>Reasonably simple analysis:</strong> Only elementary geometrical considerations are required to prove the correctness of the algorithm. They are easily justified to laymen (maybe even more easily than to experts). To prove the expected time complexity, a simple backward analysis argument is employed. This basically uses that the smallest enclosing circle is unlikely to change if a random point is removed. See the above article for details.</p> http://mathoverflow.net/questions/38245/what-is-the-easiest-randomized-algorithm-to-motivate-to-the-layperson/64374#64374 Answer by Pait for What is the easiest randomized algorithm to motivate to the layperson? Pait 2011-05-09T11:03:34Z 2011-05-09T11:03:34Z <p>The randomized algorithm most familiar to newspaper readers is the electoral poll. Polls select a very small fraction of voters and manage to predict the result of an election within a few percent. The hard part is how to sample randomly. But f irst show an example such as finding a volume or computing $\pi$, to avoid getting caught in a political argument.</p> http://mathoverflow.net/questions/38245/what-is-the-easiest-randomized-algorithm-to-motivate-to-the-layperson/64380#64380 Answer by Zsbán Ambrus for What is the easiest randomized algorithm to motivate to the layperson? Zsbán Ambrus 2011-05-09T12:22:09Z 2011-05-09T12:22:09Z <p>Suppose that hundreds of undergraduates have written a test and some people in the department have to score these all with a tight deadline. There are a few tests that are tricky to score and so take more time to score, but you can't tell which ones these tests are in advance without actually scoring them. A professor has to divide the tests among all the teachers so they score them. No teacher should get too many hard to score tests, because then they can't finish even if they work all night. </p> <p>There's no deterministic method to divide the tests in a fair way. On the other hand, it works fine to shuffle the tests and divide them randomly. (You must shuffle because there are many people who leave after fifteen minutes and write almost nothing are very easy to correct, and often many such tests are clustered together in the stack.)</p> http://mathoverflow.net/questions/38245/what-is-the-easiest-randomized-algorithm-to-motivate-to-the-layperson/85129#85129 Answer by maldini.ua for What is the easiest randomized algorithm to motivate to the layperson? maldini.ua 2012-01-07T14:57:07Z 2012-01-07T14:57:07Z <p>Multiplication checking: does $ab$ be equal to $c$ (or does $a(x)b(x)$ be equal to $c(x)$)? Analysis of randomized solution is pretty easy; also it provides a huge gap in asymptotic compared to straightforward multiplication.</p>