Can someone give a (most simple) example for an algorithm on a machine, which has access to random numbers, and which is faster than any other known algorithm for the same task?
My actual motivation is that I'm learning stochastic processes at the moment, and this should help me understand the bridge to why quantum computers are more effective than the ones we have.
On
Except Monte Carlo,we have Las Vegas as well.
An example is the random Quicksort.
The classic Quicksort is $O(n^2)$ in the worst case but $O(n\log n)$ averagely.
So we pick the reference position randomly to avoid the bad data.
On
"Concentration inequalities" provide a huge supply of examples of the phenomenon that you seek, with some beautiful applications to machine learning. Say you have a set of data $x_1, \ldots, x_n$ in $\mathbb{R}^d$ where $d$ is very large, and you hope to linearly map your data set into some smaller $\mathbb{R}^k$ without distorting distances too much.
Theorem (Johnson-Lindenstrauss): for every $\epsilon > 0$ and any $k \geq \frac{C \log n}{\epsilon}$ (where $C$ is a universal constant) there is a $k \times d$ matrix $A$ such that $$(1-\epsilon)||x_i - x_j||^2 \leq ||Ax_i - Ax_j||^2 \leq (1 + \epsilon)||x_i - x_j||^2$$
The proof is to show that a randomly chosen matrix $A$ (from a suitable distribution) has the desired property with high probability - in other words, the space of all matrices is highly "concentrated" near the set of all desired matrices. With some care it is possible to show that matrices with entries $\pm 1$ (up to rescaling) are good enough (with high probability), so you can solve the problem using any computer that can randomly generate binary digits. This algorithm is very fast.
Another example involves matrix multiplication. Say you have a matrix $A$ with an enormous number of columns and you want to calculate $A A^t$. One strategy is to try to "prune" $A$ by picking out only the columns which matter the most and hoping that the product using only those columns well-approximates the actual product. A natural strategy for pruning is to simply pick columns at random, and indeed this actually works reasonably well.
However, you run into trouble if a few of the columns are much larger than the rest since the entries of these columns will tend to dominate the product but your random process may not pick them. One way around this problem is to first multiply $A$ by a random orthogonal matrix (from a suitable distribution) to try to put all columns on a level playing field and then pick columns at random. If one chooses the random orthogonal matrix carefully then multiplying by it can be sped up dramatically using FFT algorithms, so this approach ends up being much faster than ordinary matrix multiplication (depending on the desired error).
On
Although primality testing can now be done deterministically in polynomial time, for practical purposes where you only need a certain degree of confidence that a certain number is prime, probabilistic approaches like the Miller-Rabin test are still state-of-the-art as they are much more efficient and simpler to implement.
Multi dimensional Monte Carlo integration is provably faster than traditional quadrature algorithms.
Consider the following integral over the volume $d$ dimensional $V$: \begin{equation} I=\int_{V} f(\mathbf{x}) d\mathbf{x} \end{equation} You might also think of $I$ as the average of $f$ over the volume, i.e. \begin{equation} I\simeq \sum_{i=1}^N f(\mathbf{x}_i) /N \end{equation} where the $\{\mathbf{x}_i\}$ are drawn uniformly over the volume $V$ (this can be tricky if $V$ is not regular). Now, the central limit theorem applies here, which means that the variance on the result of $I$ decreases as $\sigma_I\propto N^{-1/2}$. In contrast, multi-dimensional trapezoidal rule of $N$ points in $d$ dimension have a global error that scale as $\mathcal{O}(N^{-2/d})$, i.e. the MC method converges faster in $d>4$.