Probabilité d'être enfermé dans une prison

Quentino37 · April 2021

Bonjour,
Je me suis intéressé au Raycasting (technique de programmation qui permet de faire de la 3D grâce à une map 2D).
Par la suite je me suis posé la question suivante : si l'on prend un quadrillage infini, et que l'on met sur l'une des case le "Joueur", et que pour chaque autres case, un mur apparaisse avec une probabilité de 1/a, Quel est la probabilité que je joueur soit enfermé par les mur (le "joueur" ne peut pas passer en diagonal).
En cherchant, on arrive à des sommes infinies qui contiennent des termes que l'on ne connaît même pas, ou que je ne saurais exprimer grâce à des fonctions usuelles (nombre de prisons "minimal" (où l'on ne peut pas enlever un mur car sinon le joueur ne serait plus enfermé qui contienne exactement n murs...)

Les questions sont les suivantes.
Quel est la probabilité en fonction de a(ou 1/a) que le joueur soit enfermé(question principale),
À partir de quel "a" est-ont sûr que l'ont soit enfermé ?
...(on peut en faire plein [de] questions intéressantes comme : même question mais avec 2 joueurs, 3 joueurs..., n joueurs, et bien d'autres questions encore).

Ce n'est peut-être pas très clair... alors dite moi si ça ne l'est pas !
Peut-être que la question est simple ? Ou peut-être triviale ? ... (si ça l'est, dites le moi).
Merci d'avance (tu) (:P). 119934

Calli · April 2021

Bonjour,
Si j'ai bien compris, tu dis que le joueur est enfermé lorsque la région qu'il peut atteindre par des déplacements d'une case horizontaux ou verticaux est bornée (autrement dit ne contient qu'on nombre fini de cases). Et, tu ne l'as pas précisé, mais je présume que les présences de murs sur les différentes cases sont aléatoirement indépendantes. Je trouve que c'est intéressant comme problème.

Quentino37 · April 2021

Oui, la présence des murs sur des cases sont aléatoirement indépendante.

[Qu'est-ce qui "[u]sont[/u] aléatoirement indépendant[u]e[/u]" ? "[u]la[/u] présence" ? "[u]les[/u] murs" ? :-S AD]

Dreamer · April 2021

Bonsoir.

Comme théorie duale, il y a ceci.

Après, il faut sans doute faire quelques adaptations.

À bientôt.

Quentino37 · April 2021

@Dreamer: je ne sais pas me servir de la théorie de la percolation!B-)-

Dreamer · April 2021

Pourtant, c'est simple si tu restes au niveau du plan : la probabilité qu'il soit enfermé est complémentaire à la probabilité qu'il y ait un chemin (percolation).

Ta probabilité critique étant $\frac{1}{2}$. Au dessus, il est enfermé, strictement en dessous il y a un chemin.

Les choses se corsent pour la 3D, ta seule solution est donc d'inventer un labyrinthe en dimension supérieure à 18 car des résultats existent aussi pour ces cas de figure.

Cordialement.

Quentino37 · April 2021

merci! :-D
Mais ducoup, quel est la probabilité que il soit enfermé en fonction de de 1/a(ou a) ?

Dreamer · April 2021

J'avais parlé de quelques adaptations à faire, elles sont de cet ordre.

La probabilité critique qui est évoquée est ton fameux $\frac{1}{a}$, je ne comprends pas si le $a$ qui se cache derrière est un naturel non nul ou si tu envisages des probabilités moins rigides.

Une probabilité d'apparition égale à 1 signifie que ton personnage est littéralement emmuré.

Pour $a \geq 2$, il y a un chemin.
Le fait qu'il soit plus ou moins tortueux n'est pas déterminable a priori.
Cordialement.

lourrran · April 2021

Je crois que Quentino37 est en terminale. Donc ça va être difficile de répondre à tout ça, avec des outils à sa portée.

Dans la théorie de la percolation, telle qu'elle est décrite ici, on considère des cases, et on considère que les portes qui relient 2 cases voisines ont une probabilité $p$ d'être ouvertes.

Ici, ce ne sont pas les portes qui sont soit ouvertes, soit fermées, mais des cases 'tout entières'.
Je me souviens vaguement d'un exercice, où en fait, on montrait que les 2 problèmes sont équivalents (la dualité), mais c'est tellement contre-intuitif, que je doute.
Et si $a \ge 2$, tu dis qu'il y a un chemin ... il y a un chemin de longueur infinie ; Mais ici, la question était un peu différente.
On a une case privilégiée, et on s'intéresse à la question : y a-t-il un chemin de longueur infinie passant par cette case précise.
Et là, aucune certitude.
Meme si chaque case a une probabilité très faible d'être interdite, il se peut que notre case de départ soit enfermée dans un territoire fini.

Dreamer · April 2021

Désolé, je ne savais pas que Quentino37 est en Terminale.

C'est bien de se lancer des défis, mais il faut savoir être patient et tenace pour les mener à bien (Andrew Wiles est le parfait exemple de cette patience et ténacité).

Pour ma part, je suis incapable d'aller plus avant dans une explication adaptée.

À bientôt.

Quentino37 · April 2021

@lourran, je suis en 4ème, pas en terminale ! :-D (j'ai 13 ans)

Quentino37 · April 2021

"Dans la théorie de la percolation, telle qu'elle est décrite ici, on considère des cases, et on considère que les portes qui relient 2 cases voisines ont une probabilité p d'être ouvertes." Maintenant, j'ai mieux compris le rapport entre mon problème et la percolation(ça me dit toujours pas la réponse à la question principale!)

lourrran · April 2021

L'exercice est très compliqué. Même en pensant que tu étais en Terminale, c'était un exercice trop compliqué.

Le premier challenge, pour toi, ce serait de formuler une question 'sensée'. En terme de probabilités, formuler un problème correctement est déjà un 1er challenge.

A partir de quelle probabilité est-on sur que le pion sera enfermé ? A partir d'une proba a=1.
Si 100% des cases sont noircies, alors on est certain que le pion sera enfermé.
Mais si chaque case a une probabilité p d'être noircie (p éventuellement très proche de 1, mais p différent de 1) alors tout peut arriver. On peut tout à fait avoir un chemin infini, même si p est très proche de 1.

Georges Abitbol · April 2021

Cette version du problème s'appelle la "percolation par sites". Il me semble que dans ce cas, c'est comme pour la percolation "par liens" et donc, que si $a<2$, le joueur est sûr d'être emprisonné (et en fait sur la "carte", il n'y a que des prisons), si $a>2$, il a probabilité non nulle de ne pas être emprisonné.

Lourrran, ça m'étonne, ce que tu dis : il me semble que la probabilité qu'il y ait un chemin infini avec une probabilité de noircissement des cases proches de $1$ est nulle. Pour le voir : on compte le nombre de chemins partant d'un point fixe de longueur $n$ (on compte tous les chemins possibles, avant noircissement des cases), et on le note $c(n)$ ; pour chaque chemin de longueur $n$, la probabilité qu'il soit ouvert (aucune case noire dessus) est $(1-p)^n$ ; on majore la probabilité qu'il existe un chemin de longueur $n$ ouvert par $c(n)(1-p)^n$. Maintenant, du fait qu'on est dans $\mathbb{Z}^2$, $c(n)$ est lui-même majoré par $4*3^{n-1}$ (quatre choix pour le premier chemin, puis trois, etc.). Et donc, pour $p$ assez proche de $1$, $c(n)(1-p)^n$ tend vers $0$.
Donc la probabilité qu'il y ait un chemin infini est nulle, si la probabilité de noircissement est suffisamment grande.

lourrran · April 2021

Oui, tu dois avoir raison.
J'ai écrit un peu vite, sans bien réfléchir aux problèmes liés à l'infini.

Quentino37 · April 2021

merci Georges Abitbol pour la démonstration que à partir d'un certain a proche de 1, on est sur d'être enfermé!
"il a probabilité non nulle de ne pas être emprisonné." C'est cette probabilité non nul qui m'intéresse! (tu) (dans la question principale)
Si j'ai bien compris ceci, avec a=1/2, on à une probabilité de 0 d'être enfermé. (:D

marsup · April 2021

Si j'ai bien compris ceci, avec a=1/2, on à une probabilité de 0 d'être enfermé.

Non, pour $p>0$, la probabilité d'être enfermé n'est jamais nulle.
Je crois qu'il faut comprendre que pour $p>\frac12$, la probabilité d'être enfermé est de 1.
Je ne crois pas qu'il faille comprendre que pour $p=\frac12$, c'est déjà le cas, mais je n'en sais rien.

En tous cas, l'argument de Georges Abitbol est très simple et très joli : pour $p>\frac{2}{3}$, la probabilité d'être enfermé est de 1. (tu)

Quentino37 · April 2021

je voulait dire 1 pas 0... pour 1/2(on peut toujours imaginer des cas ou l'on est enfermé...)

marsup · April 2021

Oui, la probabilité d'être enfermé est minorée par $p^4$.

Quentino37 · April 2021

Il n'y a pas de réponse exacte à la question que j'avais posée ?
Quel est la probabilité en fonction de a (ou 1/a) que le joueur soit enfermé (question principale).
On a pour l'instant la réponse à la seconde question (1/2) (tu) B-)-

Georges Abitbol · April 2021

@marsup : Il n'est pas de moi, hein ! On le trouve dans beaucoup de références sur la percolation.
@Quentino37 : Ben, réponse exacte, réponse exacte... Que veux-tu dire ? Si ta question est "a-t-on une jolie formule toute simple qui donne cette probabilité ?" la réponse est non (enfin, pas à ma connaissance). D'ailleurs, il est possible qu'il n'existe pas de "jolie formule toute simple" (mais là j'en sais rien). En fait, l'étude de la fonction qui, à $p$ (je préfère $p$ à ton $1/a$, désolé

) associe la probabilité qu'on soit enfermé est un sujet de recherche actuel, et je crois qu'il y a plein de choses qu'on voudrait savoir dessus. La question a plein de variantes (au lieu d'un quadrillage infini 2D, on peut prendre un quadrillage infini 3D, par exemple) et c'est pas des mathématiques faciles.

Probabilité d'être enfermé dans une prison

Réponses

Bonjour!

Catégories

In this Discussion

Qui est en ligne 19