What is the easiest randomized algorithm to motivate to the layperson? - MathOverflow

What is the easiest randomized algorithm to motivate to the layperson?

2010-09-09T23:27:17Z

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.

The question: Is there a good example of a problem that:

is easily explained (and sufficiently interesting)
has a simple randomized algorithm
appears non-trivial to get an efficient deterministic algorithm

and ideally also satisfies:

the randomized algorithm has a somewhat understandable proof of correctness - so no Markov/Chernoff/random-walk-mixing-times

Answer by Robin Kothari for What is the easiest randomized algorithm to motivate to the layperson?

2010-09-09T23:47:08Z

I like the non-technical examples given by Anup Rao in this essay: http://docs.google.com/Doc?id=dq6zxpq_473cvj8ggfx

It's available from his website

He gives two example of randomized algorithms, one of them is an example of an interactive proof system with the zero knowledge property.

Answer by Louigi Addario-Berry for What is the easiest randomized algorithm to motivate to the layperson?

2010-09-10T00:39:39Z

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.

This example is also nice in my view because the Goemans--Williamson algorithm, 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.)

Answer by Artem Kaznatcheev for What is the easiest randomized algorithm to motivate to the layperson?

2010-09-10T01:48:59Z

If you are willing to sacrifice the non-trivial deterministic requirement, then I would suggest the Deutsch-Jozsa problem. 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.

The best feature is that if you want to continue and mention quantum algorithms, you can do so to recover an error-less algorithm.

Answer by Suresh Venkat for What is the easiest randomized algorithm to motivate to the layperson?

2010-09-10T05:30:14Z

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 constant number of people to hit all groups. Judging by how the general population gets confused by polls, this seems like a good example.

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 constant time by sampling (in fact, the median of THREE random elements suffices), and the more you sample, the better the approximation.

Probably the most spectacular demonstration of the power of randomness, but one alas that isn't easy to prove to a layman, is the power of two choices. It seems almost impossible that it's true, but it is.

Answer by Alon Amit for What is the easiest randomized algorithm to motivate to the layperson?

2010-09-10T05:54:48Z

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.

(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).

This is an algorithm-to-generate, not an algorithm-to-decide, but this shouldn't cause too much trouble with most layfolks.

Answer by Roland Bacher for What is the easiest randomized algorithm to motivate to the layperson?

2010-09-10T07:33:16Z

Why not mention evolution? It looks very similar to a (still running) random algorithm and its current output does not seem without interest.

Answer by Henry Yuen for What is the easiest randomized algorithm to motivate to the layperson?

2010-09-10T08:12:07Z

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.

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).

You can then approximate pi with $\pi r^2 /4r^2 \approx A/T$, but $r=1$, so $\pi \approx 4A/T$.

Answer by Grönwall for What is the easiest randomized algorithm to motivate to the layperson?

2010-09-10T08:37:35Z

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.

Answer by Ricky Demer for What is the easiest randomized algorithm to motivate to the layperson?

2010-09-10T08:41:51Z

Input: n

Output:

a quadratic nonresidue mod n, if n is an odd prime

0, otherwise

According to this article, 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.

Answer by Scott Aaronson for What is the easiest randomized algorithm to motivate to the layperson?

2010-09-10T12:35:43Z

Michael, how about approximating the volume of some shape in $\Re^n$ by sampling random points?

This example has the following advantages:

It seems easy enough to explain at a cocktail party (depending, of course, on the guests).
It's used constantly in "real life" (indeed, pretty much any Monte Carlo simulation in physics, etc. could be interpreted as solving this problem).
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).

Answer by avr-white for What is the easiest randomized algorithm to motivate to the layperson?

2010-09-11T01:07:06Z

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.

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.

Answer by none for What is the easiest randomized algorithm to motivate to the layperson?

2011-03-04T11:14:45Z

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.

Answer by Alex R. for What is the easiest randomized algorithm to motivate to the layperson?

2011-05-03T20:32:20Z

How about using Monte Carlo for deciphering encrypted messages? This 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?

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.

Answer by Zen Harper for What is the easiest randomized algorithm to motivate to the layperson?

2011-05-04T03:50:05Z

[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!]

[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:

Matching nuts and bolts by Noga Alon, Manuel Blum, Amos Fiat, Sampath Kannan, Moni Naor, Rafail Ostrovsky;

citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.103 ]

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]:

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.

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 you can't compare two nuts, or two bolts, with each other directly.

Abstractly: we have 2 real unknown sequences $(x_1, x_2, \ldots, x_n)$ and $(y_1, y_2, \ldots, y_n)$.

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$.

The obvious algorithm of trying all of them one-by-one takes $O(n^2)$ time.

However, a variant of randomised quicksort takes $O(n \log n)$ time on average. The randomness just comes from picking each nut/bolt at random.

Details: pick a nut, use that as the pivot element for the bolts; then use the matching bolt as the pivot element for the nuts, etc. - like quicksort, but going back-and-forth between $x$ and $y$ elements.

Answer by Per Alexandersson for What is the easiest randomized algorithm to motivate to the layperson?

2011-05-04T06:20:50Z

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.

Answer by Manfred Sauter for What is the easiest randomized algorithm to motivate to the layperson?

2011-05-09T07:12:13Z

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.

Problem: 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.

Algorithm: The algorithm itself was introduced in the following article:

Emo Welzl, Smallest enclosing disks (balls and ellipsoids). New results and new trends in computer science (Graz, 1991), 359–370, Lecture Notes in Comput. Sci., 555, Springer, Berlin, 1991.

The document is accessible via CiteSeer.

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\}$.

Definition of $MD(P,R)$:

If $P=\emptyset$ or $\operatorname{card}(R)=3$, then directly calculate and return $MD(\emptyset,R)$.
Otherwise, take a random point $p\in P$ and recursively calculate $D:=MD(P\setminus\{p\},R)$.
If $p$ is enclosed by $D$, return $D$.
Otherwise, return the recursively calculated $MD(P\setminus\{p\},R\cup\{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.

Deterministic algorithms: 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 Wikipedia or this webpage by Rashid Bin Muhammad.

Reasonably simple analysis: 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.

Answer by Pait for What is the easiest randomized algorithm to motivate to the layperson?

2011-05-09T11:03:34Z

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.

Answer by Zsbán Ambrus for What is the easiest randomized algorithm to motivate to the layperson?

2011-05-09T12:22:09Z

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.

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.)

Answer by maldini.ua for What is the easiest randomized algorithm to motivate to the layperson?

2012-01-07T14:57:07Z

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.