Nombre de sommets d'un polyèdre aléatoire
Bonjour,
je me retrouve à errer dans la jungle polyèdrale. Quelqu'un aurait-il déjà croisé des résultats sur le nombre de sommets / faces d'un polyèdre aléatoire ? Typiquement je prends N points tirés uniforméments dans [0,1]^n, quelle est la loi du nombre de sommet de l'enveloppe convexe de ces N points ?
je me retrouve à errer dans la jungle polyèdrale. Quelqu'un aurait-il déjà croisé des résultats sur le nombre de sommets / faces d'un polyèdre aléatoire ? Typiquement je prends N points tirés uniforméments dans [0,1]^n, quelle est la loi du nombre de sommet de l'enveloppe convexe de ces N points ?
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Reste donc à calculer l'aire moyenne d'un triangle, ce qui est assez coton.
Ça serait un peu plus simple avec une distribution uniforme dans le disque.
On prend N points tirés uniformément dans [0,1]^n.
On a N (majuscule) et n (minuscule).
C'est 2 fois le même nombre, ou 2 nombres différents ?
Si on parle de N points tirés uniformément dans [0,1]^N (et donc la même valeur N) ... sauf coup de chance vraiment extrême, l'enveloppe convexe aura toujours N points.
Par contre, si n < N ... c'est une autre histoire.
Dans le cas N=4 et n=2, les 4 événements sont effectivements disjoints, mais ils ne sont pas indépendants. Si on connaît l'aire moyenne d'un triangle, ça ne suffit pas, car on ne peut pas conclure : Proba = 4*AireMoyenne.
Car, pour $n$ points, l'enveloppe convexe est de dimension $n-1$, donc d'intérieur vide.
On peut rajouter un point presque sûrement sans qu'aucun ne devienne intérieur.
C'est seulement à partir de $N=n+2$ que le nombre de sommets n'est plus déterministe.
Tu fatigues grave, là, lourrran ! C'est sûr qu'il y a peu de chances pour que des événements disjoints soient indépendants. Je te laisse corriger la grosse bêtise qui vient après.
On sait calculer l'aire moyenne de ce triangle : $A$ (je n'ai pas la formule, mais ça se trouve, ça s'estime... Admettons qu'on ait cette aire moyenne)
A partir de cette aire moyenne $A$, comment obtient-on la probabilité que le 4ème point soit à l'intérieur du carré... c'est facile.
Mais ça ne répond pas à la question : quelle est la probabilité que 4 points forment un quadrilatère convexe. Le point "intérieur" peut-être le 4ème, mais pas forcément.
Il y a peut-être un truc qui m'échappe, et je sais que GBZM se trompe très rarement... mais je ne vois vraiment pas. Et ça risque fort de m'empécher de dormir si je n'ai pas d'éclaircissement, or, j'ai absolument besoin d'être en pleine forme demain.
2°) On tire quatre points uniformément et indépendamment dans le carré unité. Quelle est la probabilité que le quatrième soit dans le triangle formé par les trois premiers ?
C'est l'aire du triangle formé par les 3 premiers.
La question suivante risque d'être plus difficile.
Es-tu d'accord que ça montre que la probabilité que l'enveloppe convexe des quatre points dans le carré unité ait trois sommets est quatre fois l'aire moyenne du triangle formé par trois points ?
Si par "question suivante" tu entends "et que se passe-t-il pour 5 points ?", alors là oui, ça se complique.
PS. On peut descendre d'un cran et se demander quelle est la probabilité que l'enveloppe convexe de trois points dans l'intervalle unité ait deux sommets. Et on trouve bien que c'est trois fois la longueur moyenne d'un segment d'extrémités prises au hasard dans l'intervalle unité.
PPS. En y repensant, ça fait un joli moyen de démontrer que cette longueur moyenne est 1/3.
@lourrran : soit $E_i$ l'événement "le point n° $i$ est dans le triangle de sommets les trois autres, pour $i=1,\ldots,4$.
1°) Les $E_i$ ont tous même probabilité : l'aire moyenne $A$ du triangle de sommets trois points au hasard dans le carré unité. Oui ou non ?
2°) L'événement "l'enveloppe convexe des quatre points est un triangle" est la réunion disjointe des $E_i$ (à un événement de probabilité nulle près). Oui ou non ?
Moi ça me semble parfaitement évident, et je ne comprends vraiment pas pourquoi ça ne passe pas chez toi. Peut-être faudrait-il que quelqu'un d'autre te l'explique à sa façon ?
Petit complément : $N$ points au hasard dans le carré unité ($N\geq 4$ - "au hasard" sous-entend l'uniformité et l'indépendance). La probabilité que l'enveloppe convexe soit un triangle est
$$ \binom{N}{3} A^{N-3}\;.$$
Oups, ne pas confondre la puissance de la moyenne et la moyenne de la puissance !
Avec une certaine opiniâtreté, on peut mener à son terme le calcul de $\Pr(\mathcal E)$ où $ \mathcal E$ est l'évènement:
$\boxed{\mathcal E:\quad \text{L'enveloppe convexe de}\:\: 4 \:\text{ points choisis uniformément et de manière indépendante dans}\: [0;1]^2 \:\text{ est un triangle.}}$
Gabuzomeu a déjà dit que $\Pr (\mathcal E) = 4\:\mathbb E (A),\:\:$ où $A$ est l'aire du triangle formé par $3$ points uniformémént et indépendamment répartis dans $[0;1]^2.$
$\forall x_1,x_2,x_3,y_1,y_2,y_3 \in [0;1],\quad$ je note: $\:\:F(x_1,x_2,x_3,y_1,y_2,y_3)= \Big| y_1(x_3-x_2)+y_2(x_1-x_3)+y_3(x_2-x_1)\Big|.$
$$\mathbb E (A)=\dfrac 12\displaystyle \int_{[0;1]^6} F ( x_1,x_2,x_3,y_1,y_2,y_3) \mathrm d x_1 \mathrm d x_2 \mathrm d x_3 \mathrm d y_1 \mathrm d y_2 \mathrm d y_3.$$
La difficulté de ce calcul réside bien entendu dans la gestion de la valeur absolue.
La symétrie entre les variables $x_i$ permet d'écrire $\mathbb E(A) = 3 \displaystyle \int _{0< x_1< x_2< x_3 < 1}\mathrm dx \int _{[0;1]^3}F(x_1,x_2,x_3,y_1,y_2,y_3) \mathrm dy.$
Notons $G(x_1,x_2,x_3) =\displaystyle\int _{[0;1]^3} F(x_1,x_2,x_3,y_1,y_2,y_3) \mathrm d y.$
Alors $\:\:\displaystyle \dfrac {G(x_1,x_2,x_3)}{ (x_3-x_1)}=\int_{[0;1]^2 } H(x_1,x_2,x_3,y_1,y_3)\mathrm d y_1\mathrm dy_3 \quad$ où $\quad H(x_1,x_2,x_3,y_1,y_3) \displaystyle =\int_0^1\left|y_2 - y_1\dfrac{x_3-x_2}{x_3-x_1} -y_3\dfrac {x_2-x_1}{x_3-x_1}\right | \mathrm dy_2.$
Or cette dernière intégrale se calcule aisément car le choix de l'ordre des $x_i$ fait qu'elle est de la forme
$$ \displaystyle \int _0 ^1 |t-m| \mathrm dt\ = \dfrac12 +m^2 -m\quad\:\:\text{ avec}\:\:\:0\leqslant m \leqslant 1.$$
On parvient ainsi après quelques efforts à: $\:\displaystyle 3 G(x_1,x_2,x_3) = \dfrac{2(x_3-x_2)^2 +3(x_3-x_2)(x_2-x_1)+2(x_2-x_1)^2}{2(x_3-x_1)}\:\:$ puis à:
$\mathbb E (A)= \displaystyle \int_{0<x_1 < x_3< 1} \Big[ \dfrac { \frac 23 (t-x_3)^3- t^3 +\frac 32 t^2(x_1 + x_3) -3x_1x_3t + \frac23 (t-x_1)^3} {2(x_3-x_1)}\Big] _{t=x_1}^{t=x_3} \mathrm d x_1 \mathrm dx_3.$
$\mathbb E(A) = \displaystyle \int_ {0< x_1 <x_3 <1}\left( \frac 13 (x_3-x_1)^2 -\frac 12 (x_1^2+x_1x_3+x_3^2) + \frac 34 (x_1+x_3)^2 - \frac 32 x_1x_3 +\frac 13 (x_3-x_1)^2\right) \mathrm dx_1 \mathrm d x_3$
$\mathbb E(A)= \displaystyle \frac {11}{12}\int_{0< x_1< x_3 < 1 }( x_1-x_3)^2 \mathrm dx_1 \mathrm dx_3= \dfrac {11}{144}.\quad $ La probabilité d'une erreur dans le calcul précédent n'est certes pas mince, mais je propose néanmoins:
$$\boxed{\Pr(\mathcal E) = \dfrac {11}{36}.}$$
LOU16, quel courage ! J'avoue que je suis un peu surpris par la forme raisonnable du résultat final (un rationnel avec numérateur et dénominateur assez petits). Je me souviens avoir calculé sur ce forum, il y a longtemps, la longueur moyenne du segment joignant deux points tirés au hasard dans le carré,et le résultat était nettement plus torturé.
Je vais avoir l'étincelle un jour... Oublions.
C'est un raisonnement simple, il n'y a aucune raison que tu t'y dérobes.
Rappel : l'événement $E_i$ est "le $i$-ème point appartient à l'enveloppe convexe des trois autres".
1°) Plaçons nous en dehors de l'événement $A$ : "trois des points sont alignés". C'est un événement de probabilité nulle (d'accord ?)
2°) Une configuration de quatre points qui est dans un des $E_i$ est aussi dans l'événement $T$ : "l'enveloppe convexe des quatre points est un triangle" : $\bigcup_{i=1}^4 E_i \setminus A \subset T$ (d'accord ?)
3°) Si l'enveloppe convexe des quatre points est un triangle, alors il existe un unique point qui n'est pas un sommet de ce triangle et qui appartient donc à l'enveloppe convexe des trois autres points : $\forall c\in T\setminus A\ \ \exists! i\in \{1,2,3,4\}\ \ c\in E_i$ (d'accord ?)
4°) de 2° et 3° on déduit que $T\setminus A$ est la réunion disjointe des $E_i\setminus A$ : $T\setminus A=\bigsqcup_{i=1}^4 E_i\setminus A$. (d'accord ?)
5°) de 1° et 4° on déduit $P(T)=\sum_{i=1}^4 P(E_i)$ (d'accord ?)
Lourrran, ou bien tu dis sur lequel des points ci-dessus tu as des doutes, ou bien tu es forcé de reconnaître que tu es convaincu.
Ce qui me semble bizarre, c'est que tu avais pourtant écrit dès ton premier message et que tu n'es pas sans savoir que la probabilité d'une réunion disjointe d'événements est la somme de leurs probabilités.
Pourquoi je disais que les événements ne sont pas indépendants ? J'avais commencé à réfléchir en disant : on prend 3 points ABC au hasard, ils définissent un triangle, on prend un 4ème point D, quelle est la probabilité que ce 4ème point soit dans le triangle ABC. ... C'est facile.
Ensuite, si D n'est pas dans ABC, quelle est la probabilité que A ne soit pas dans BCD puis si ni A, ni D ne sont des points intérieurs, on regarde B, et enfin, on regarde C...
En posant le problème comme ça, on ne peut pas raisonner en faisant des sommes ... on a des probas conditionnelles... c'est compliqué.
En posant le problème de façon un peu différente : "on prend au hasard 4 points, etc etc," les 4 points jouent le même rôle, je vois bien que le raisonnement va être plus simple. Mais ce raisonnement, je veux le faire par moi-même.
Pour l'instant, j'accepte le résultat... devant l'évidence. Mais pour m'approprier le résultat, pour pouvoir dire 'j'ai montré que bla bla bla ...' et non pas 'on m'a expliqué que bla bla bla ...', j'ai besoin de me concentrer sur la question. Et j'ai d'autres préoccupations qui font que je ne peux absolument pas me concentrer sur cette question en ce moment.
Rendez-vous dans 10 jours, j'aurai certainement l'occasion de faire mon petit footing, et ce sera l'occasion de réfléchir à ce problème.
Des événements disjoints de probabilités non nulles ne sont jamais indépendants. Mais la probabilité de leur réunion est toujours la somme de leurs probabilités.
J'ai donc relu tout ça avant d'aller faire mon petit footing ce matin, et j'y vois clair. Enfin je pense.
Si on a 5 points dans un cube ( ou une sphère ou ...) en dimension 3, le même raisonnement est applicable, on calcule le volume moyen V d'un tetraedre dans un cube de coté 1, et la probabilité que l'enveloppe convexe soit un tétraedre, c'est 5 V.
C'est bon, c'est acquis.
J'ai voulu voir aussi si on pouvait trouver 'facilement' les résultats pour 5 points en dimension 2. Avec 5 points en dimension 2, l'enveloppe convexe est un pentagone, un quadrilatère ou un triangle.
On pourrait être tenté de reproduire le même raisonnement : l'enveloppe convexe est un quadrilatère ssi il y a un unique point intérieur. etc etc... mais le raisonnement ne tient pas parce que le point 4 de la démonstration parlait de réunion disjointe ... et là, on a une réunion, mais non disjointe. Plus précisément dans le cas où l'enveloppe convexe est un quadrilatère, le point intérieur est dans exactement 2 triangles.
Selon moi, le calcul bloque ici. Si A est l'aire moyenne d'un triangle dans un carré de côté 1, on ne peut pas aller plus loin, on ne peut pas reproduire le même raisonnement , et dire : la probabilité d'obtenir un quadrilatère est donc f(A) avec f un polynome de degré 2.
GBZM s'était posé la question, puisqu'il avait proposé une formule. On est bien d'accord que la formule, si formule il y a, va être très compliquée ?