<jupyter_start><jupyter_text>Nous allons voir dans ce notebook un exemple très basique d’une chaîne de Markov. Il s’agit de la **marche aléatoire**. Cet exemple est décrit plus en détail [ici](https://fr.wikipedia.org/wiki/Marche_al%C3%A9atoireMarche_al%C3%A9atoire_discr%C3%A8te_%C3%A0_une_dimension). Pour plus d’information sur les marches aléatoires, vous pouvez lire la [page Wikipédia](https://fr.wikipedia.org/wiki/Marche_al%C3%A9atoire) dédiée à ce sujet.  Marche aléatoire discrète à une dimensionImaginons un bonhomme qui marche sur une linge droite. À chaque pas il a deux choix possibles :* Faire un pas en avant* Faire un pas en arrière Pour choisir où aller il tire à pile ou face avec une pièce dont la probabilité de sortir pile est égale à $p$.**Exercice 1:**  Écrire une fonction en python permettant de simuler le chemin parcouru par le bonhomme. La fonction prendra en entrée la probabilité d’aller en avant (*p*) et le nombre de pas (*n*). La fonction donnera comme résultat une liste de taille n avec les endroits visités.<jupyter_code>import random
import numpy as np
import matplotlib.pyplot as plt

% matplotlib inline

# Solution
def random_walk(p, n):
    visited_positions = [0]
    # Completer la fonction
    
    return visited_positions<jupyter_output><empty_output><jupyter_text>**Exercice 2 :**  Tracer le chemin parcouru par le bonhomme<jupyter_code>p = 0.5
n = 1000
visited_pos = random_walk(p, n)<jupyter_output><empty_output><jupyter_text>**Exercice 3 :**  Compter le nombre de fois où le bonhomme est passé par une position donnée.<jupyter_code>position = 0
nb_visit_position = 0 # Completer ici
print("La position {} a été visitée {} fois".format(position, nb_visit_position))<jupyter_output>La position 0 a été visitée 22 fois<jupyter_text>Modèle des urnes. Urnes d'EhrenfestUn autre exemple très populaire de chaîne de Markov est le [modèle des urnes d'Ehrenfest](https://fr.wikipedia.org/wiki/Mod%C3%A8le_des_urnes_d%27Ehrenfest). L’exemple est décrit comme ceci : On considère deux urnes *A* et *B*, ainsi que *N* boules, numérotées de *1* à *N*. Initialement, toutes les boules se trouvent dans l'urne *A*. Le processus stochastique associé consiste à répéter l'opération suivante :Tirer au hasard un numéro *i* compris entre *1* et *N*, prendre la boule numéro *i*, la transférer dans l'urne où elle n'était pas.   Par convention, le premier instant est $\displaystyle t_{0}=0$.  Dans ce modèle, on suit au cours du temps $t$ (discret) le nombre total de boules $n(t)$ présentes dans l'urne *A*. **Exercice 4 :**  Pour $N=4$ boules, faire le *diagramme* et la *matrice de transition* de la chaîne de Markov du modèle décrit.*Solution*Le diagramme de la chaîne est :![diagramme](./images/urnes_diagram.jpg)Si on prend l'ordre suivant pour les états : $\{4, 3, 2, 1, 0\}$, la matrice de transition est :$$\begin{bmatrix}0 & 1 & 0 & 0 & 0 \\ 1/4 & 0 & 3/4 & 0 & 0 \\0 & 0 & 1/2 & 1/2 & 0 \\0 & 0 & 3/4 & 0 & 1/4 \\0 & 0 & 0 & 1 & 0\end{bmatrix}$$**Exercice 5 :**   Écrire une fonction en python permettant de suivre le nombre de boules dans l’urne A. La fonction prendra comme entrée le nombre total de boules *n_balls* et le nombre de répétitions *n_rep*.<jupyter_code># Solution
def urnes(n_balls, n_rep):
    n_balls_inA = [n_balls]
    
    # Completer ici
    
    return n_balls_inA

urnes(4, 10)<jupyter_output><empty_output><jupyter_text>**Exercice 6:**  Tracer l'évolution du processus<jupyter_code>n_balls = 4
n_rep = 100
balls_inA = urnes(n_balls, n_rep)<jupyter_output><empty_output><jupyter_text>Comportement en temps long<jupyter_code>n_balls = 4
n_rep = 1000000
balls_inA = urnes(n_balls, n_rep)

n_visits = [balls_inA.count(i) for i in range(n_balls+1)]
freq = [float(n)/n_rep for n in n_visits]
freq
transition_matrix = np.matrix([[0, 1, 0, 0, 0], 
                               [1./4, 0, 3./4, 0, 0],
                               [0, 1./2, 0, 1./2, 0],
                               [0, 0, 3./4, 0, 1./4],
                               [0, 0, 0, 1, 0]])
initial_state = np.array([1, 0, 0, 0, 0])
nb_step = 1000000
prob = [np.dot(initial_state, transition_matrix)]
for i in range(nb_step):
    prob.append(np.dot(prob[-1], transition_matrix))
inv_prob = np.true_divide(sum(prob), nb_step)
inv_prob
v, M = np.linalg.eig(transition_matrix.transpose())
v
M[:, 0] / sum(M[:, 0])<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.11100938429846646, 'fraction_numerical': 0.030899519340810255, 'mean_word_length': 4.099183197199533, 'pattern_counts': {'":': 0, '<': 24, '<?xml version=': 0, '>': 24, 'https://': 3, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '6', 'dir': 'jupyter-structured-clean-dedup', 'id': '605205', 'license': 'Unlicense', 'n_tokens_mistral': 1718, 'n_tokens_neox': 1624, 'n_words': 528, 'path': 'Notebooks/03-ChainesDeMarkov_Exemples.ipynb', 'repo_name': 'willyrv/projet2MIC', 'size': '4369'}