A poor man's fractal

Self-similarity is more common than one could think. Below is a succession of four x5 zooms in the middle part of a symmetric 1 dimensional random walk with a million steps. This extensively studied stochastic process is defined by the following simple iteration:

$$X_{t+1}=X_t + B_t$$

where the $B_t$ are independent random variables taking +1, -1 values with probability $\frac{1}{2}$. Basically you flip a coin at each time $t$ and go up or down accordingly.

Each shaded green region is reproduced in the graph immediately below it. The interesting thing to notice is how similar does the $X$ curve behaves at any zoom level. Of course, there are some artifacts due to the anti-aliasing algorithm - most notably in the variation of the perceived thickness of the curve - but overall, the eye notices the same general uneveness at any level. Put in other words, if you ignore the labels on the $x$ and $y$ axis, looking at any such graph of a region of $X$ is not sufficient for you to determine at what scale you are observing $X$. It could be on a thousand time steps as it could be on billions of billions! Benoît Mandelbrot already gave this example quite a long time ago but I thought it would be nice (and easy) to get a better looking picture than in the early publications.

By the way, if you have ever glanced at charts of stock market prices, you'll probably have noticed that they too look the same on many scales - and between different stocks. There are some elegant and appealing (but far from mainstream) mathematical developements in fractal methods applied to finance - developements that are rooted in this observation of self-similarity. The big buzzword here is stable distributions: probability distributions that do not necessarily have means or standard deviations, but still possess the wonderful property of being stable by addition, namely the addition of two random variables that follow a stable distribution will follow a stable distribution itself. But I am already off-topic.

A last word about the symmetric 1 dimensional walk. No matter where you start ($X_0$), you'll get back to this value with probability 1 some time in the future. The little surprise is that you may have to wait an infinite amount of time before getting back: the expectation of the return time is infinite. You mileage may vary, infinitely in this case. Actually, it is possible to prove that the time to return $T$ follows asymptotically a scaling distribution:

$$\mathbb{P}(T \geq t) = O(\frac{1}{\sqrt{t}})$$

$T$ is heavy tailed: its tail probablity decreases very slowly. If stock prices follow symmetric 1 dimensional random walks (it does not appear to be so), then no matter what happens, you could always get your money back, for some infinitely remote time in the future, provided the stock still exists...

Les chaussettes du panier à linge propre

Voici un autre petit calcul orienté vie pratique que les amateurs du genre devraient apprécier. La motivation de celui-ci réside dans le constat de la difficulté à appareiller mes chaussettes à la sortie du sèche-linge. 

La plupart de mes paires chaussettes sont d'une couleur unie blanche ou noire. Elles se distinguent cependant par quelques motifs subtils pour les paires noires et par des traits de couleur au niveau du mollet pour les paires de sport. Ne pouvant pas distinguer clairement les motifs et les traits de couleur des chaussettes pliées avec les autres vêtements, je dois effectuer une sorte de tirage sans remise de mes chaussettes et les appareiller au fur et à mesure. Généralement, je dois en tirer au moins 5 ou 6 avant d'avoir une paire complète, en sachant que j'ai grosso-modo une quizaine de paires dans mon panier.

Intuitivement, 6 chaussettes avant de trouver une paire c'est vraiment beaucoup. Y a-t-il une explication mathématique à mon manque de bol ? Il s'avère qu'il y en a une, bien que la formule finale soit particulièrement laide. Après calcul, l'espérance du nombre de chaussettes qu'il faut tirer sans remise hors du panier à linge propre contenant $n$ paires avant d'avoir une première paire est:

$$e_n=\sum_{k=0}^{n-1} (k+1) \frac{k}{2n-k} 2^{k-1} \frac{(2n-k)!}{(2n-1)!} \frac{(n-1)!}{(n-k)!}$$

L'application numérique donne $e_{15} \approx 6.9$, ce qui est a peu près conforme à l'expérience, modulo mon discernement. Il est a noter qu'asymptotiquement, on a un comportement du type birthday paradox où $e_n \sim \sqrt{n}$. Je joins à la formule les deux récurrences que j'ai utilisées pour son établissement - for debugging purposes.

$$a_{k+1}=2 \frac{n-k}{2n-k}a_k, a_1=1$$

$$b_{k+1}=\frac{k}{2n-k}a_k$$

Où $a_k$ est la probabilité qu'il n'y ait aucune paire parmi $k$ chaussettes tirées sans remise, et $b_k$ est la probabilité qu'on trouve une paire au bout du $k$-ième tirage. Que les bonnes âmes se dévouent et vérifient la formule et/ou trouvent une simplification esthétique :)