Delhaye Quentin Garcia Duarte Eduardo
Polytech BA2 MATH-H-204

Situation : un serpent du classique Snake s’allonge depuis sa position de départ. Toutes les directions son équiprobables et il ne peut pas revenir sur ses pas.

Problème : quelle est la probabilité qu’il fasse plus de 23 mouvements sans se rentrer dedans ? Le principe de résolution adopté est le suivant.

– Initialisation de la matrice devant contenir les coordonnées du parcours. Cette réinitialisation permet d’avoir des résultats indépendants.

– Détermination aléatoire d’une direction, rejet de la direction d’où vient le serpent.

– Avance du serpent dans la direction déterminée.

– Comparaison de la coordonnée actuelle avec le chemin déjà parcouru. Dans le cas d’une correspondance, la partie est interrompue et le compteur de touches est incrémenté.

La valeur exacte obtenue pour 2.10^{5} itération est 13, 684% On peut expliquer cette convergence avec le théorème de Bernoulli qui nous dit que que pour n tendant vers l’infini, la fréquence relative d’un évènement converge vers sa probabilité.

Pour cette probabilité p et ce nombre d’expériences n, on peut déterminer l’écart-type comme suit : σ = \sqrt{\frac{pq}{n}} où q est la probabilité complémentaire de p. On obtient alors σ = 7, 6849.10^{−4}.

On peut alors utiliser l’inégalité de Bienayme-Tchebycheff pour déterminer la proportion de résultats s’écartant d’un intervalle déterminé de cette valeur de convergence.

P (μ − kσ ≤ V ≤ μ + kσ) ≥ 1 − \frac{1}{k^{2}} Posons k = 4 et nous obtenons alors qu’au moins 93, 75% des résultats se trouveront dans l’intervalle

[0, 13377; 0, 13991]