Random versions of deterministic problems

Question

What are the examples of situations where "randomizing" a problem (or some part of it) and analyzing it using probabilistic techniques yields some insight into its deterministic version?

An example of what I have in mind: it is a well-known conjecture that the Hausdorff dimension of the graph of Weierstrass function (everywhere continuous, nowhere differentiable) is given by a certain simple formula, depending on the amplitudes and phases of the cosines in the series. This is still open; however, in the paper "The Hausdorff Dimension of Graphs of Weierstrass Functions" Hunt proved that if you add a uniformly distributed independent random "noise" to each phase, the conjectured formula holds with probability 1. So while the "randomized" approach does not solve the original problem, it somehow lends credibility to the original conjecture and thus gives us some insight about the problem.

Answer 1

There are several applications of probability to attack deterministic problems. Generally, this approach is called the 'probabilistic method' or the probabilistic method of Erdos, who first applied it to solve a wide class of problems. For a survey of the technique, check out Noga Alon and Joel Spencer's book "The Probabilistic Method".

A specific example, due to Erdos, is an answer to Sidon's problem. Sidon asked whether or not one can find a set $B \subset \mathbb{N}$ such that $|B \cap [1, N]| = N^{1/2 + o(1)}$ for all $N$, and such that $2B = $ {$b_1 + b_2 : b_1, b_2 \in B$ is equal to $\mathbb{N}$. Erdos answered this question in the positive by using probabilistic arguments to show that such $B$'s exist. In particular, if one considers the random set $B$ defined by $\displaystyle p(x \in B) = \min\left(1, 10 \sqrt{\frac{\log x}{x}}\right)$, then $B$ satisfies Sidon's condition with probability 1. To date, no explicit example of such a $B$ is known to exist.

Answer 2

Neudecker and Williams proved that an analogue of the Riemann hypothesis holds with probability one for numbers drawn from a randomised version of the sieve of Eratosthenes.

Answer 3

There are many examples in fractal geometry/dynamical systems (including of course the one in the OP).

For example, in general it is very hard to compute the dimension (any kind of fractal dimension) of a set invariant under a nonconformal dynamical system. However adding randomness makes the situation much easier. See for example the paper "Hausdorff dimension for randomly perturbed self-affine attractors" by Jordan, Pollicott and Simon.

A related example concerns Bernoulli convolutions and more general self-similar measures with overlaps. Very little is known for specific cases, but the more randomness one adds the easier the situation becomes. See for example the paper "Absolute continuity for random iterated function systems with overlaps" by Peres, Simon and Solomyak, in which they establish absolute continuity of a family of random measures, whose deterministic counterpart includes a measure whose absolute continuity was asked by Sinai motivated by connections with the Collatz conjecture. Namely, Sinai asked about the absolute continuity of the distribution $\mu_a$ of the random series $$ 1+Z_1+Z_1 Z_2+Z_1 Z_2 Z_3+\ldots, $$ where $P(Z_i=1+a)=P(Z_i=1-a)=1/2$ for some $a\in (0,1)$. (The authors of the cited paper show that if $a>\sqrt{3}/2$ then $\mu_a$ is singular, while if $a<\sqrt{3}/2$, then a variant of $\mu_a$ in which $Z_i$ has a multiplicative random error, is absolutely continuous.)

Answer 4

I'm sure you're looking for something deeper, but one example I like where using a rough probabilistic argument actually gives the right answer is when considering the number of derangements (fixed-point free permutations) of $\{1,2,\ldots, n\}.$ Putting the uniform probablity distribution on $S_n$, the probablity that a given symbol $i$ is fixed by a random permutation $\tau$ is $1 - \frac{1}{n}$. Therefore, you might expect the probability that a given permutation should fix no symbol would be around $(1 - \frac{1}{n})^{n}$, so around $e^{-1}$. But all sorts of unjustified independence assumptions have been made here. However, if we do a more precise analysis, an inclusion-exclusion argument shows that the number of permutations in $S_n$ fixing no symbol is exactly $\sum_{j=0}^{n-1} (-1)^{j}$ " n choose j" ` $|S_{n-j}|$. Dividing by $n!$, we are left with the $n-1$-th degree Taylor polynomial for $e^{-x}$ at $x =1$, which soon gets very close to $e^{-1}$. The unjustified independence assumptions seem to be compensated for by the fact that $(1- \frac{1}{n})^{n}$ is only an approximation to $e^{-1}$. In fact, the proportion of derangments clearly approaches $e^{-1}$ much faster than $(1- \frac{1}{n})^{n}$ does.

In another direction, there are situations in finite group theory where it is possible to show that the probability that a given pair of elements with given properties generate the group is close to $1$, yet it may be very difficult to exhibit an explicit pair of such generators. See for example the work of Martin Liebeck and various co-authors on this topic.

Answer 5

This is heuristic so it may not be what you are asking for. There is a probabilistic argument for the hook length formula. Let $\lambda$ be a partition: then the number of standard tableaux of shape $\lambda$ is $$ \frac{n!}{\prod_{(i,j)\in\lambda}h(i,j)} $$ Here $(i,j)$ runs over the coordinates of the boxes of the Ferrers diagram and $h(i,j)$ is the hook length of the box $(i,j)$.

Then the usual definition of a standard tableau is that it is a filling of the boxes by $1,2,\ldots ,n$ such that the entries increase along each row and down each column. However this is equivalent to saying that for all boxes the entry in $(i,j)$ is the smallest entry in the hook for $(i,j)$.

Now there are $n!$ ways to fill the boxes and the probability of the condition holding for box $(i,j)$ is $\frac1{h(i,j)}$. If these probabilities were independent (which they are not!) this would prove the hook length formula.

Answer 6

One problem that I am aware of is the problem of finding the Poisson boundary of a manifold, that is, the bounded harmonic functions. There is a probabilistic way of approaching this problem using Brownian motion (c.f. here) which has evolved out of the probabilistic proof of Liouville's theorem.

If we let $B=(B_t:t \geq 0)$ be a Brownian motion and $Inv(B)$ be the sigma-algebra of events of the form $\{B_t \in A\}$ iff $\{B_{t+s}\in A\}$ for all $s \geq 0$, then there is a one-to-one correspondence between $Inv(B)$ measurable random variables and bounded harmonic functions.

Liouville's theorem holds on $\mathbb{R}^d$ because if we can start two Brownian motions at $x,y \in \mathbb{R}^d$ and couple them in a finite time, so the invariant sigma algebra is trivial. On manifolds where Liouville's theorem does not hold, then by looking at the invariant algebra, one can work out all of the bounded harmonic functions.

Answer 7

See The Probabilistic Method by Noga Alon and Joel H. Spencer.

Answer 8

This surely isn't what you had in mind either, but just one word: Collatz. (OK, more than one word: Assume that the 3n+1|n/2 process is completely random. Odd->even, even->1/2*even+1/2*odd. Now it is obvious the random process should converge, since the Markov chain equilibrium is 2/3:1/3 and 3^(1/3)<2^(2/3). Not much of an insight, I admit...)

Answer 9

While it is not known that $P \neq NP$, it is known that for most oracles $A \subseteq \omega$ we have $P^A \neq NP^A$. This might be interpreted as "evidence" for the conjecture when $A = \emptyset$.

Answer 10

This may not be quite what you had in mind, but: suppose you were trying to compute the absolute value of a Gauss sum $\sum_{a=0}^{p-1} \zeta^{a^2}$ where $\zeta = e^{ \frac{2 \pi i}{p} }, p$ an odd prime. Intuitively you might guess that quadratic residues are uniformly distributed and thus this sum should behave like a sum of $p$ random unit vectors. The expected value of the square root of the length of such a sum is just $p$, so one might expect that the absolute value of a Gauss sum should be about $\sqrt{p}$. In fact it is exactly $\sqrt{p}$!

Answer 11

Lets say you want to know if $\sum_n^\infty sin(a_n)$ converges for some set of values $a_n$. In many cases it might be really hard to prove (if not impossible) that $a_n\mod \pi$ eventually is not really close to integers. Even though a_n has no obvious relation to Pi. Then we might want to assume a_n mod Pi behaves somewhat randomly (but perfectly normal with regards to this property) and the divergence is trivial.

For instance $a_n=2^{1/3}*\zeta(2n+1)*e^{1/e}$
Or $a_n=2^{1/2}*(the-n'th-prime-number)$