Let (Y (t))t∈ℕ be a sequence of i.i.d. random variables having values in {−1, +1} as
follows:
(1)
We define a stochastic process (X(t))t∈ℕ on ℤ called random walk by
(2)
Question 1Simulate one single trajectory for p = 0.5.
T= 100;
time=1:(T+1);
p=0.5;
trajectory=zeros(time) ;
// vector will contain the trajectory X(0),...,X(T)
for t=1:T
trajectory(t+1)=trajectory(t) + ( 2*grand(1,1,'bin',1,p)-1 ) ;
end ;
xset("window",1); xbasc(1); plot2d2(time,trajectory);
xtitle('Random walk (p='+string(p)+')', 'time (t)','X(t)')
Question 2Draw four trajectories for p = 0.5 on the same picture.
S=4;
trajectory=zeros(S,sum(prod(ones(time))));
// vector will contain the S trajectories X(0),...,X(T)
for s=1:S,
for t=1:T
trajectory(s,t+1)=trajectory(s,t) + ( 2*grand(1,1,'bin',1,p)-1 ) ;
end ;
end
xset("window",2); xbasc(2); plot2d2(time',trajectory(1:S,:)' );
xtitle('Random walk (p='+string(p)+')', 'time (t)','X(t)')
Figure 1: Four trajectories of the symmetric random walk on ℤ
Question 3Take p ⁄= 0.5 and redo simulations.
2 Random walk on ℤ2
Let (Y (t))t∈ℕ be a sequence of i.i.d. random variables having values in {−1, +1}2 as
follows:
(3)
We define a stochastic process (X(t))t∈ℕ on ℤ2 called 2-dimensional random walk by
(4)
Question 4Simulate trajectories for p𝜖,𝜖′ = 0.25.
T= 100;
time=1:(T+1);
p=0.5;
trajectory=zeros(2,T+1) ;
// vector will contain the trajectory X(0),...,X(T)
for t=1:T
trajectory(:,t+1)=trajectory(:,t) + ( 2*grand(2,1,'bin',1,p)-1 ) ;
end ;
xset("window",1);xbasc(1); plot2d(trajectory(1,:),trajectory(2,:),...
style=3,...
rect=[-maxi(abs(trajectory(1,:))),-maxi(abs(trajectory(2,:))),...
maxi(abs(trajectory(1,:))),maxi(abs(trajectory(2,:)))] );
xtitle('Symmetric random walk', 'time (t)','X(t)')
3 Transmitting 0 and 1
(5)
may be simulated by
(6)
where (Y (t))t∈ℕ is a sequence of i.i.d. random variables with Bernoulli law ℬ(p; 1).
T= 100;
time=1:(T+1);
p=0.9;
trajectory=zeros(time) ;
// vector will contain the trajectory X(0),...,X(T)
for t=1:T
trajectory(t+1)= (2*trajectory(t)-1)*grand(1,1,'bin',1,p) + ...
1- trajectory(t)
end ;
xset("window",1); xbasc(1); plot2d2(time,trajectory, rect=[0,-0.1,T,1.1]);
xtitle('0 or 1 (p='+string(p)+')', 'time (t)','X(t)')
4 Testing the irreductibility of a Markov chain
On utilise Scilab pour visualiser le graphe associé à une chaîne de Markov :
La marche aléatoire de Cox Ross est définie de la façon suivante : soient a et b deux
nombres réels et soit (Un)n≥0 une suite de variables aléatoires indépendantes de loi
commune :
avec 0 < p < 1. On défini alors une suite de variables aléatoires (Sn)n∈ℕ par :
On a vu en cours que la suite Sn est une chaîne de Markov : Supposons que l’on s’intéresse au
temps n ∈ [0,N], comme Sn = s1∏i=1nUi, l’espace d’état de la chaîne (Sn)n∈ℕ est alors fini,
ℰ = {γi,j≡ s1(1 + a)i(1 + b)j, 0 ≤ i + j < N}. On vérifie que Sn est une chaîne de Markov
homogène de matrice de transition:
(7)
La suite Sn précédemment définie peut servir à modéliser le cours d’un actif. On cherche à
calculer pour s1 fixé la valeur :
(8)
On a vu en cours que cette quantité peut se calculer de façon récursive en calculant pour n
allant de N à 0 les quantités :
(9)
On se propose dans cet exercice de calculer vn(x) récursivement pour obtenir v1(s1). On
utilisera les données suivantes :
Les états possibles de la chaîne sont indicés par un couple (i,j) avec i ∈ [0,N] et j ∈ [0,N] et
on veut dans Scilab utiliser une matrice V pour stocker la fonction v(x,n). Il faut donc pouvoir
coder les états avec un unique indice et on retiendra i + N ∗ j + 1. La matrice utilisée dans Scilab
sera de taille V (N2,N) (on ne cherche pas dans un premier temps à économiser de la place mais
on privilégie du calcul matriciel).
Question 6
Construire une matrice s(N,N)qui contient les états possibles de la chaîne. Utiliser lafonction matrixpour transformer sen un vecteur colonne de taille NxN.
Initialiser une matrice Vde taille (NxN,N).
On suppose que f(x) = (x − 1)+. Initialiser la dernière colonne de V(V(:,N)) avec lafonction f et en utilisant le vecteur colonne contenant les états possibles.
calculer récursivement V(:,n)en utilisant les résultats du cours. On notera que pourcertains états à l’instant n les états possibles à l’instant n + 1 sont hors de l’ensemble[1,N]mais ce n’est pas grave car la valeurs de V(:,n+1)en ces points n’interviennentpas dans le calcul de v1(s1). On pourra donc utiliser zéro comme valeurs de V en cespoints.
Pour les points atteignables à partir de s1tracer les courbes V (:,n).
6 Le problème de la secrétaire
On rappelle ici la formulation vue en cours. On dispose de N objets de valeurs vk (
v1< v2<…< vN ) inconnues que l’on tire au hasard (de façon équiprobable) les uns après les
autres. Quand on tire le k-ième objet on peut soit le choisir et s’arrêter soit continuer. Les objets
que l’on va tirer successivement auront pour valeur vσ(k) où σ est une permutation de [1,N] et
toutes les suites (vσ(k))k=1,N sont équiprobables.
Introduisons les notations suivantes :
On a vu que la suite Sn est une chaîne de Markov. L’espace d’état de Sk est {0, 1} et les
Matrices de transition M(k) vérifient : Mi,1(k) = 1∕(k + 1) et Mi,0(k) = k∕(k + 1) (les Sk sont en
fait indépendants).
Le problème du décideur est un problème d’arrêt optimal. Il cherche à calculer u1(1) et obtenir
la stratégie optimale associée (noter que S1≡ 1), où un(x) est donné par la formule
générale :
avec gk(1) = k∕N et gk(0) ≡ 0.
On rappelle que un(x) est solution de l’équation suivante :
(10)
Question 7
Écrire un programme qui calcule la fonction un(x) pour n ∈ [1,N] et tracer les courbesun(1) et un(0) ainsi que les fonctions gn(1) et gn(0).
On suppose que les valeurs des secrétaires sont [1,N]. Utiliser grandpour en tirer unepermutation aléatoire.
Calculer le long de cette trajectoire la valeur de unet trouver le temps d’arrêt i.e l’indicede la secrétaire choisie.
![[ ]
----1----
v1(s1) = 𝔼 (1 + r)N f(SN )|S1 = s1 .](Modali10x.png)
![[ ]
vn(x) = 𝔼 -----1-----f(SN )|Sn = x .
(1 + r)N− n](Modali11x.png)
![{ 1 si W = k avec W = arg max v
Sk = k k j∈ [1,k] σ(j)
0 sinon](Modali12x.png)
![un (x) ≡ sup 𝔼 [g τ(S τ)|Sn = x].
τℱnt.a.,n≤τ≤N](Modali13x.png)
