La présentation, la lisibilité, l'orthographe, la qualité de la rédaction, la clarté et la précision des raisonnements entreront pour une part importante dans l'appréciation des copies.
Les candidats sont invités à encadrer dans la mesure du possible les résultats de leurs calculs.
Aucun document n'est autorisé. L'utilisation de toute calculatrice et de tout matériel électronique est interdite. Seule l'utilisation d'une règle graduée est autorisée.
Si au cours de l'épreuve, un candidat repère ce qui lui semble être une erreur d'énoncé, il la signalera sur sa copie et poursuivra sa composition en expliquant les raisons des initiatives qu'il sera amené à prendre.
On s'intéresse dans ce sujet au problème de la double dépense de bitcoins par un groupe d'individus mal intentionnés.
On rappelle que le bitcoin est une monnaie virtuelle dont l'utilisation pour des transactions est associée à une structure unique appelée blockchain, partagée sur le réseau des usagers de cette monnaie et ayant pour but de sécuriser ces transactions.
La modélisation étudiée ne nécessite pas de connaissances particulières sur le bitcoin et la blockchain.
Partie I - Deux résultats généraux
On démontre dans cette partie deux résultats préliminaires, aux questions 5 et 6 . Ces résultats seront utilisés dans la suite du sujet et pourront être admis.
Calcul d'une probabilité
Soit X et Y deux variables aléatoires sur un espace probabilisé, à densité et indépendantes.
On note F_X et F_Y les fonctions de répartition de X et Y.
On suppose que Y est à valeurs positives et possède une densité f_Y dont la restriction à [0, + ∞[ est continue sur cet intervalle.
Pour tout x ∈ ℝ^+, on pose H(x) = ℙ([X ⩽ Y] ∩ [Y ⩽ x]).
a) Montrer que H est une fonction croissante sur ℝ^+qui admet une limite finie en + ∞.
b) En utilisant la suite (H(n))_(n ∈ ℕ), montrer que lim_(x → + ∞)H(x) = ℙ([X ⩽ Y]).
Que vaut H(0) ?
2. Soit ( u, v ) un couple de réels positifs tels que u < v.
a) Montrer que H(v) − H(u) = ℙ([X ⩽ Y] ∩ [u < Y ⩽ v]) puis que :
b) En déduire que pour tout x ∈ ℝ^+, H est dérivable en x et H^′(x) = F_X(x)f_Y(x).
c) En conclure que pour tout x réel positif, H(x) = ∫_0^x F_X(t)f_Y(t)dt.
3. Montrer que ℙ([X ⩽ Y]) = ∫_0^(+ ∞)F_X(t)f_Y(t)dt.
4. En utilisant la fonction K : x ↦ ℙ([X < Y] ∩ [Y ⩽ x]), on montrerait de même et nous l'admettrons que :
ℙ([X < Y]) = ∫_0^(+ ∞)F_X(t)f_Y(t)dt = ℙ([X ⩽ Y])
Que peut-on en déduire pour ℙ([X = Y]) ?
5. Application aux lois exponentielles
On suppose que U et V sont deux variables aléatoires indépendantes suivant des lois exponentielles de paramètres respectifs λ et μ, réels strictement positifs.
Soit θ un réel positif ou nul.
a) Déterminer la fonction de répartition de la variable aléatoire X = U − θ.
b) En déduire que pour tout θ ⩾ 0,
ℙ([U − θ ⩽ V]) = 1 − μ/(λ + μ)e^(− λθ)
Inégalité de Boole
On considère (B_k)_(k ∈ ℕ^∗) une famille d'événements d'un espace probabilisé.
a) Montrer par récurrence sur n ∈ ℕ^∗ que ℙ(⋃_(k = 1)^n B_k) ⩽ ∑_(k = 1)^n ℙ(B_k).
b) On suppose que la série ∑_(k ⩾ 1)ℙ(B_k) converge. Montrer que :
ℙ(⋃_(k ⩾ 1)B_k) ⩽ ∑_(k = 1)^(+ ∞)ℙ(B_k)
Partie II - Une compétition entre deux groupes
Dans toute la suite du sujet, on désigne par p un réel de l'intervalle ] 0,1 [ et on pose q = 1 − p.
On modélise une compétition entre deux groupes d'individus A et B avec les règles suivantes :
Le groupe A doit résoudre une suite de problèmes (P_k)_(k ⩾ 1) dans l'ordre des indices. Au temps t = 0, le groupe commence la résolution du problème P_1, ce qui lui prend un temps représenté par la variable aléatoire X_1. Une fois P_1 résolu, le groupe aborde immédiatement le problème P_2, et on note X_2 le temps consacré à la résolution de P_2 par le groupe A, et ainsi de suite.
Pour tout k ∈ ℕ^∗, on note X_k la variable aléatoire donnant le temps consacré à la résolution du problème P_k par le groupe A.
De même, le groupe B doit résoudre dans l'ordre une suite de problèmes (Q_k)_(k ⩾ 1); la résolution du premier problème Q_1 commence au temps t = 0 et on note, pour tout k ∈ ℕ^∗, Y_k la variable aléatoire donnant le temps consacré par le groupe B à la résolution du problème Q_k.
À ce jeu est associé un espace probabilisé ( Ω, A, ℙ ) sur lequel sont définies les suites de variables aléatoires (X_k)_(k ⩾ 1) et (Y_k)_(k ⩾ 1), et on fait les hypothèses suivantes :
pour tout k ∈ ℕ^∗, X_k suit la loi exponentielle de paramètre p, notée E(p), et Y_k suit la loi exponentielle E(q);
pour tout k ∈ ℕ^∗, les variables aléatoires X_1, …, X_k, Y_1, …, Y_k sont indépendantes.
On établit alors la liste de tous les problèmes résolus dans l'ordre où ils le sont par les deux groupes. En cas de simultanéité temporelle de la résolution par les deux groupes d'un de leurs problèmes, on placera d'abord le problème résolu par A dans la liste puis celui résolu par B.
Pour tout n ∈ ℕ^∗, on note U_n la variable aléatoire de Bernoulli associée à l'événement « le n-ème problème placé dans la liste est un problème résolu par le groupe A ».
Par exemple, si la liste des cinq premiers problèmes résolus est ( P_1, P_2, Q_1, P_3, Q_2 ) alors U_1 = 1, U_2 = 1, U_3 = 0, U_4 = 1 et U_5 = 0.
Pour tout n ⩾ 0, on note aussi S_n la variable aléatoire donnant le nombre de problèmes qui ont été résolus par A présents dans la liste des n premiers problèmes résolus. En particulier, S_0 vaut toujours 0 .
a) Que représente la variable aléatoire ∑_(k = 1)^n X_k ?
b) On suppose que X_1 = 5, X_2 = 2, X_3 = 3, X_4 = 2, Y_1 = 2, Y_2 = 2, Y_3 = 4, Y_4 = 2. Déterminer U_1, …, U_7.
Peut-on aussi en déduire la valeur de U_8 ?
c) Compléter le script Scilab suivant pour qu'il simule le jeu et, pour n, p donnés, affiche la liste des valeurs U_1, U_2, …, U_n :
p = input('p=')
n = input('n=')
q = 1-p
U = zeros(1, n)
sommeX = grand(1, 1, "exp", 1/p)
sommeY = grand(1, 1, "exp", 1/q)
mini = min(sommeX, sommeY)
for k = 1:n
if sommeX == ...
U(k) = ...
sommeX = sommeX + grand(1, 1, "exp", 1/p)
else
sommeY = ...
end
mini = min(sommeX, sommeY)
end
...
d) Quelle(s) instruction(s) faut-il ajouter pour afficher la valeur de S_n ?
8. Loi de U_n
Dans cette question, on démontre par récurrence sur n ⩾ 1 que ℙ([U_n = 1]) = p.
a) Montrer que ℙ([U_1 = 1]) = ℙ([X_1 ⩽ Y_1]) = p.
b) i. Montrer que pour tout réel x < 0, ℙ_([U_1 = 1])([Y_1 − X_1 ⩽ x]) = 0.
ii. Soit x un réel positif ou nul.
Établir : ℙ_([U_1 = 1])([Y_1 − X_1 ⩽ x]) = 1/pℙ([X_1 ⩽ Y_1 ⩽ X_1 + x]), puis calculer ℙ_([U_1 = 1])([Y_1 − X_1 ⩽ x]).
c) On peut interpréter ce résultat en disant que la loi conditionnelle de Y_1 − X_1 sachant [U_1 = 1] est une loi exponentielle. Quel est son paramètre?
Par analogie, quelle est la loi conditionnelle de X_1 − Y_1 sachant [U_1 = 0] ? (on n'attend pas une démonstration précise mais un argument de bon sens pour justifier le résultat proposé)
d) On suppose que n ∈ ℕ^∗ et ℙ([U_n = 1]) = p.
Déduire de cette hypothèse et de la question précédente que ℙ_([U_1 = 1])([U_(n + 1) = 1]) = p et ℙ_([U_1 = 0])([U_(n + 1) = 1]) = p.
e) Conclure.
9. On montrerait aussi par récurrence, et nous l'admettrons, que pour tout n ∈ ℕ^∗, les variables aléatoires U_1, …, U_n sont mutuellement indépendantes.
En déduire la loi de S_n.
Soit r ∈ ℕ, on s'intéresse, dans les questions qui suivent, à la probabilité a_r de l'événement, A_r : « il existe un n ⩾ r tel que, lorsque n problèmes en tout ont été résolus, le groupe A en a résolu r de plus que le groupe B≫.
10. a) Justifier que a_0 = 1.
b) Montrer que pour tout r ⩾ 1, ℙ_([U_1 = 1])(A_r) = ℙ(A_(r − 1)) et ℙ_([U_1 = 0])(A_r) = ℙ(A_(r + 1)).
c) En déduire que pour tout r ⩾ 1, a_(r + 1) = 1/qa_r − p/qa_(r − 1).
d) En remarquant que 1 − 4pq = (1 − 2p)^2, donner une expression de a_r en fonction de p, q, r et de deux constantes que l'on introduira.
11. Le cas p ⩾ 1/2.
Montrer que, dans les cas p = 1/2 et p > 1/2, la suite (a_r)_(r ∈ ℕ) est constante et égale à 1.
12. Le cas p < 1/2.
a) Soit k un entier naturel.
i. Établir : A_(2k) = ⋃_(i ⩾ k)[S_(2i) = i + k].
ii. Montrer que pour tout i ⩾ k, on a ℙ([S_(2i) = i + k]) = ((2i)/(i + k))p^(i + k)q^(i − k).
iii. Après avoir donné la valeur de la somme ∑_(j = 0)^(2i)((2i)/j), montrer que : pour tout entier i ⩾ k, ((2i)/(i + k)) ⩽ 4^i.
iv. En déduire l'inégalité :
b) Montrer en utilisant l'inégalité de Boole (voir question 6) que si p < 1/2, alors lim_(k → + ∞)a_(2k) = 0.
c) Conclure en utilisant la question 10.d. que si p < 1/2, alors: pour tout entier naturel r, a_r = (p/q)^r.
On a ainsi établi dans les questions 11 et 12 :
∀r ∈ ℕ, a_r = {(p/q)^r, si p < 1/2; 1, si p ⩾ 1/2.
Ce résultat pourra être admis et utilisé dans le suite du sujet.
Partie III - La blockchain et la stratégie de la double dépense
On utilise, dans cette partie, les notations et résultats de la partie II.
Soit n un entier supérieur ou égal 1 .
La blockchain est formée d'une suite de blocs, chacun associé à plusieurs transactions. Elle contient l'historique de toutes les transactions effectuées depuis la création du bitcoin.
Avant d'être placé dans la blockchain, un nouveau bloc doit être validé. Cette validation nécessite la mise en œuvre d'une grande puissance de calcul pour résoudre un problème dépendant fortement du contenu du bloc et des blocs qui le précèdent.
Les individus qui valident les blocs sont appelés mineurs.
Il est possible qu'à un instant donné, coexistent sur le réseau deux blockchains, valides et différentes. Dans ce cas, le réseau choisira celle qui comporte le plus de blocs et l'autre sera abandonnée.
Par prudence, lorsqu'un bloc est validé, il est recommandé d'attendre que n − 1 blocs le suivant soient aussi validés pour considérer que les transactions incluses dans le bloc soient honnêtes.
Un groupe de mineurs mal intentionnés, noté A, peut essayer de dépenser deux fois les mêmes bitcoins en procédant ainsi :
Le groupe A demande la validation de l'achat d'un bien d'un montant de s bitcoins qu'il a en sa possession.
Lorsque le bloc K incluant cette transaction est proposé à la validation sur le réseau, A modifie ce bloc en K^′, qu'il ne diffuse pas, en remplaçant l'achat par une vente des s bitcoins en euros à son profit par exemple. Il se met alors à la validation de ce nouveau bloc et crée ainsi une deuxième instance de la blockchain qu'il continue à développer sans la diffuser.
Lorsque le groupe B, représentant l'ensemble des autres mineurs du réseau, a validé K ainsi que les n − 1 blocs suivants, le vendeur du bien considère que la transaction est valide et fournit le bien.
Le groupe A attend alors d'avoir une blockchain plus longue que celle de B, qui est publique, pour la diffuser donc invalider la blockchain publique et l'achat du bien. Le crédit en bitcoins du vendeur du bien est alors annulé.
On reprend et on complète la modélisation de la partie précédente pour déterminer la probabilité que la stratégie de la double dépense réussisse et le choix de n pour que cette probabilité soit faible.
Une première phase du jeu, décrit dans la partie II, s'achève à l'instant aléatoire t où le problème Q_n est ajouté à la liste des problèmes résolus.
Le groupe de mineurs A est ensuite déclaré vainqueur s'il se trouve un instant t^′ ⩾ t où le nombre de problèmes résolus par A dans la liste des problèmes résolus depuis le début du jeu, est strictement supérieur au nombre de ceux résolus par B dans cette même liste. On note G_n cet événement.
On détermine, dans cette partie, la probabilité de G_n en fonction de n et de p.
13. On s'intéresse tout d'abord à la loi de la variable aléatoire T_n égale au nombre de problèmes résolus par le groupe A lorsque l'on place Q_n dans la liste des problèmes résolus.
a) Montrer que pour tout k ∈ ℕ, [T_n = k] = [S_(n + k − 1) = k] ∩ [U_(n + k) = 0].
b) En déduire que ℙ([T_n = k]) = ((n + k − 1)/k)p^k q^n.
14. a) En utilisant la formule des probabilités totales, établir :
c) En déduire que pour tout n ∈ ℕ^∗ : ℙ(G_(n + 1)) = ℙ(G_n) − (1 − p/q)(pq)^(n + 1)((2n + 1)/(n + 1)).
d) Montrer par récurrence, que pour tout n ∈ ℕ^∗ :
Connaissant p < 1/2, on cherche à limiter le risque que la stratégie mise en place par le groupe de mineurs A réussisse.
a) Après avoir établi la formule (n/k) = n/k((n − 1)/(k − 1)) lorsque k ∈ [ [1, n] ], écrire une fonction Scilab qui calcule les coefficients binomiaux.
b) Écrire un script Scilab qui détermine n_p, le plus petit entier n tel que ℙ(G_n) ⩽ ε pour p < 1/2 et ε > 0 saisis au clavier par l'utilisateur.
NB : Pour ε = 10^(− 4) = 0, 1% et p variant entre 10% et 32%, on obtient pour la représentation de n_p en fonction de p :
Même année, EcricomeEcricome Maths appliquées ECE 2020Ecricome · 2020Corrigé
Même sessionBCE Maths appliquées EDHEC ECE 2020BCE · 2020Corrigé
Même sessionBCE Maths appliquées emlyon ECE 2020BCE · 2020Corrigé
Même chapitre : Probabilités finies, discrètes et… (+2)BCE Maths appliquées ESSEC ECG 2023, épreuve 2BCE · 2023Corrigé