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.
Dans tout le sujet on considère un espace probabilisé ( ), toutes les variables aléatoires qui interviennent dans la suite sont définies sur cet espace.
Soit un entier supérieur ou égal à 3 et un réel appartenant à .
Pour génèrer des graphes non orientés de manière aléatoire, on se donne :
, les sommets du graphe;
pour toute paire de sommets avec une variable de Bernoulli de paramètre .
Les variables , pour décrivant les paires de sommets avec , sont supposées indépendantes ;
les arêtes d'un graphe ainsi généré sont les paires telles que si ou si .
Dans tout le problème, par convention, une somme portant sur un ensemble d'indices vide vaut 0 , un produit vaut 1 , une intersection vaut , une réunion vaut .
Partie 1 - Nombre aléatoire de triangles
On note l'ensemble des parties à trois éléments de l'ensemble des sommets, le nombre de ses éléments et on pose
Étant donné , un élément de , on dit que est un triangle dans un graphe généré aléatoirement si et sont des arêtes de .
Pour tout , on note la variable aléatoire de Bernoulli associée à l'événement est un triangle de et est la variable aléatoire égale au nombre de triangles de .
Par exemple si et le graphe est représenté ainsi,
alors .
Quelle est la valeur de en fonction de ?
a) Soit . Posons avec . Montrer que .
b) En déduire que, pour tout suit la loi de Bernoulli de paramètre .
c) Justifier que . En déduire que .
On s'intéresse à la variance de .
Si et appartiennent à et sont différents, on note lorsque et ont exactement deux éléments en commun et dans le cas contraire.
On note l'ensemble des couples ( ) tels que , et l'ensemble des couples ( ) tels que et .
On désigne par le nombre d'éléments de .
3. a) Montrer que :
b) Montrer que si et sont indépendantes. En déduire que :
c) En conclure que :
On note .
Montrer que si et en déduire que .
En conclure que : .
5. Calcul de .
a) Déterminer le nombre de triplets ( ) où sont quatre éléments distincts de l'ensemble .
b) En déduire que .
Partie 2 - Étude informatique
On se donne un graphe généré par le procédé décrit dans le préambule.
On définit la fonction supprimeDer(L) qui si L est la liste des listes d'adjacence du graphe dont les sommets sont , modifie L afin quelle devienne la liste des listes d'adjacence du graphe , dont les sommets sont , obtenu en supprimant dans le sommet et les arêtes contenant ce sommet.
def supprimeDer(L):
s = len(L)-1
L.pop() # supprime le dernier élément de la liste L
for a in L:
if s in a:
a.remove(s) # supprime s dans la liste a
Compléter la fonction suivante pour qu'elle retourne le nombre de triangles dont un des sommets est le sommet dans le graphe dont la liste des listes d'adjacence est L :
def triangle2s(s, L):
cpt = 0
adj = L[s]
for i in range(len(adj)):
for j in range(..., len(adj)):
if ... in L[...]:
cpt += 1
return cpt
Écrire une fonction nbTriangles(L), utilisant les deux fonctions précédentes, qui retourne le nombre de triangles du graphe dont la liste des listes d'adjacence est représentée par L.
On suppose que la fonction graphe(n,p) génère un graphe aléatoire suivant les hypothèses décrites dans le préambule.
Expliquer ce que retourne la fonction suivante :
def fonctionMystere(n):
cpt = 0
for i in range(1000):
L = graphe(n,1/n)
if nbTriangles(L) == 0:
cpt += 1
return cpt / 1000
Partie 3 - Inégalité de Harris
désigne un entier naturel non nul.
Soit une fonction définie sur une partie de à valeurs dans .
Si , on dit que est -croissante sur si, pour tout élément de et est croissante sur son ensemble de définition.
Si , une fonction 1 -croissante sur est simplement une fonction croissante sur .
On définit de même la notion de fonction -décroissante.
On considère des variables aléatoires finies.
On admet le résultat suivant (théorème de transfert d'ordre ):
Si une fonction définie sur et alors
On note la propriété suivante :
Si sont des variables aléatoires finies indépendantes, et deux fonctions définies sur et -croissantes sur cet ensemble, et si l'on pose et , alors :
Dans cette question , on pose une variable aléatoire finie, et sont deux fonctions croissantes sur .
a) Montrer que pour tout .
b) Montrer que pour tout ,
c) En déduire que ( ) est vraie.
10. On suppose que ( ) est vraie pour un certain et on considère des variables aléatoires finies indépendantes, et deux fonctions définies sur et -croissantes.
On pose et .
a) A l'aide des théorèmes de transfert d'ordre et , montrer que:
b) Justifier que pour tout :
c) On pose pour tout et .
Montrer que et sont croissantes sur et .
d) En conclure que ( ) est vraie. Conclure.
e) La propriété ( ) reste-t-elle vraie si et sont -décroissantes? Justifier votre réponse.
Que se passe-t-il si l'une est -croissante et l'autre -décroissante?
Partie 4 - Inégalité de Janson et application
On reprend les notations de la partie 1 .
De plus, pour tout , on pose . On remarquera que .
Dans cette partie on établit un encadrement de .
11. Justifier que . En déduire que .
12. Montrer que pour tout et .
13. a) On pose . Justifier brièvement que, pour tout s'exprime comme une fonction -croissante sur des variables aléatoires pour éléments de .
En déduire que, pour tout puis s'expriment comme des fonctions -décroissantes des variables aléatoires pour éléments de .
b) En conclure que, pour tout puis que :
Inégalité de Boole. Montrer par récurrence sur que si sont des événements, on a :
Si est un événement de probabilité non nulle, on rappelle que la probabilité conditionnelle sachant est notée . On admet qu'elle possède les mêmes propriétés que la probabilité .
En particulier l'inégalité de Boole est vérifiée par .
De plus si est une variable finie, on note l'espérance de pour la probabilité ce qui signifie que :
Cette espérance conditionnelle possède les mêmes propriétés que l'espérance en particulier l'inégalité de Harris vue dans la partie 3.
15. Soit et trois événements tels que et .
Montrer que .
On admet que les probabilités conditionnelles qui interviennent dans la suite sont bien définies.
Pour tout , on pose .
On note aussi et
Soit , on définit et , ainsi on a : .
a) Justifier que et sont indépendants. En déduire que .
b) Établir que .
c) On admet provisoirement que pour :
En déduire que, .
d) Justifier que pour tout et en déduire que :
On rappelle que où a été défini dans la partie 1 à la suite de la question 2.
a) Montrer que .
b) En conclure que :
c) En déduire l'encadrement :
Soit un réel strictement positif.
a) Montrer que .
b) Établir que .
c) On suppose que et . En déduire la limite de quand .
On reprend les notations de la partie 2. L'exécution de l'instruction fonctionMystere (100) affiche dans la console Python 0.849. Est-ce cohérent avec le résultat de la question précédente si on considère que pour assez petit, est proche de ?
Démonstration de (1) - Soit un entier plus grand que 2. On considère des variables de Bernoulli indépendantes et un sous ensemble de . On note le complémentaire de dans . On note l'événement .
a) Montrer que, pour tout ,
b) En déduire que les variables aléatoires sont indépendantes pour la probabilité conditionnelle .
Soit , on reprend les notations de la question 16.
c) Montrer que pour .
d) En utilisant l'inégalité de Harris, montrer que pour :
