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.

Aucun commentaire:

Enregistrer un commentaire

Cheval de fer, acte II

La première partie est ici. Quand John Kennedy s’y était installé au tout début des années 1790, Manchester n’était encore qu’un gros bour...