Alignements de k points

Dans le graphique ci-dessous, j’ai placé 30 points de façon (pseudo-)aléatoire — en l’occurrence, les coordonnées ($x$ et $y$) suivent une loi uniforme. Question : à votre avis, combien d'alignements de 3 points peut-on trouver là-dedans ?

Celles et ceux qui me font l’honneur de me lire le savent sans doute : il y en a beaucoup plus que ce que notre intuition nous suggère. C’est une forme d’illusion des séries (clustering illusion), ce biais cognitif qui nous porte à voir des phénomènes déterministes là où il n’y rien d’autre que de l’aléa. En l’espèce, nous aurons tendance à penser qu’un alignement de 3, 4 ou 5 points ne peut pas être dû au hasard : quelqu’un l’a sans doute voulu comme ça.

Le problème

Commençons par poser les bases : qu’est-ce qu’on entend par des points alignés, précisément. Par exemple, considérez le graphique suivant :

Au premier abord, ces trois points semblent bien alignés. Sauf qu’en traçant la droite de régression :

Ils sont raisonnablement alignés… mais pas parfaitement. Juger de l’alignement de $n$ points, c’est donc une affaire de précision. Par points alignés, on entend habituellement qu’ils se trouvent tous sur une bande, un chemin rectiligne, d’une largeur donnée. Sur le graphique ci-dessus, vous pouvez facilement imaginer deux droites parallèles à ma droite de régression — une un peu au-dessus, l’autre légèrement en dessous — de telle sorte que les trois points se trouvent dans cette zone du plan. Si cette bande a une largeur $w$ et si vous pensez que ce degré de précision est suffisant, vous considérerez que ces points sont alignés.

Partant de là, on peut tenter d'estimer grossièrement la probabilité de trouver $k$ points alignés dans un ensemble de $n$ points situés dans un carré de côtés $L$ avec une largeur de bande $w$. Elle dépend du nombre de paquets de $k$ points qu'il est possible de former parmi $n$ points (ce qui, dans un ensemble de 30 points ($n=30$) donne tout de même 4 060 triplets ($k=3$) possibles !) :

$$\binom{n}{k} = \frac{n!}{(n-k)!k!}$$

Et elle dépend du rapport entre la surface occupée par la bande ($L \times w$) et la surface totale du carré ($L^2$). Si vous considérez toutes les bandes contenant 2 points, le nombre de troisièmes points situés dans l'une de ces bande devrait très approximativement être :

$$\frac{n!}{(n-k)!k!} \left(\frac{w}{L}\right)^{k-2}$$

Dans mon exemple, avec $n=30$, $k=3$, $L=1$ et $w=0.01$, ça devrait nous faire une quarantaine d'alignements de 3 points.

Simulation

Évidemment, j’ai eu envie de simuler ça sous R pour vérifier. Pour ce faire, j’ai donc concocté un petit algorithme que je soumets à votre sagacité. L'idée consiste, pour chaque $k$-uplet possible, déterminer les coefficients de la droite de régression — la pente ($\beta$) et l'ordonnée à l'origine ($\alpha$) — puis, vérifier que les $k$ points se situent bien dans une bande de plus ou moins $w/2$ autour de cette droite.

Dans le graphique ci-dessus, par exemple, nous souhaitons savoir si les $k$ points sont situés à l’intérieur de la bande délimitée par les deux droites en pointillés rouges. Pour ce faire, il nous faut transformer les résidus de la régression en distances perpendiculaires à la droite de régression (trait continu rouge) et vérifier que la valeur obtenue est bien inférieure à $w/2$ (les segments $[ob]$ et $[od]$, en bleue). En d’autres termes, nous voulons vérifier que, pour chaque point, étant données les résidus ($\varepsilon$, les segments [oc] et [oa]) et les coefficients de la régression, la valeur des segments $[ob]$ ou $[od]$ sont bien inférieurs ou égaux à $w/2$ ?

En principe l'angle $[cob]$ (appelons-le$\theta$) doit être le même que celui de la pente de notre droite de régression. Puisque la valeur d'un angle, en radians, est égale à l'arctangente de sa pente :

$$\theta = \arctan{\beta}$$

Et que, par ailleurs :

$$\cos(\theta) = \frac{[ob]}{[oc]} = \frac{w/2}{\epsilon}$$

Avec un peu d'algèbre, nous cherchons donc à vérifier que :

$$\frac{\epsilon}{\cos(\theta)} \leq \frac{w}{2}$$

En faisant tourner cet algorithme sur tous les triplets possibles de mon set de $n$ points avec $w = 0.01$, on vérifie qu'il y a pas moins de 47 alignements de 3 points :

Et, si vous vous posiez la question, il y a aussi 4 alignements de 4 points :

Voilà le code :

Shortcoming : c’est un peu long. Vos suggestions sont les bienvenues.