# Synthèse de cours : AAGA
###### tags: `AAGA` `synthèse`
## Pense-bête
* $\lceil log(a)\rceil \leq log(a) + 1$
* Nombre de Stirling $\to n! \approx \sqrt{2\pi . n}\ \lgroup{\frac{n}{e}\rgroup^n}$
* $\sum_{i=1}^{n} 1\ + 2\ + 3\ + ...\ + n = \frac{n\ (n + 1)}{2} \to \frac{(dernier\ terme)\ \times\ (nombre\ de\ termes)}{2}$
## Génération d'entiers
Les deux types de générateurs d'entiers sont :
**True Random Number Generators :** Utilisés en crypto et assez complexe à réaliser. Il sont souvent basés sur des données physique extérieure.
**Pseudo random generators :**
Générateur qui vont se contenter de générer des nombre qui ont l'air aléatoire. Ils sont possible à coder.
### Exemple de PRNG
Il en existe une infinité, en voici quelques un
#### Générateur congruentiels linéaires
Méthode très utilisée.
**Principe :**
On a besoin de 4 entiers :
- $m$ : Le modulo ($m>0$)
- $a$ : Le multiplicateur ($0 \leq a < m$)
- $c$ : l'incrément ($0 \leq c < m$)
- $X_0$: la valeur initiale, appelée graine ($0 \leq X_0 < m$)
On construit une suite d'entier dans $[0, m-1]$ de la manière suivante :
$X_{n+1} = (aX_n+c) \ mod \ m$
La suite $(X_n)_{n \in N}$ est une suite congruentielle (ou modulaire) linéaire, toute suite extraite de cette dernière l'est aussi !
**Propriété :**
$$
X_{n+k} = (a^kX_n+ \frac{a^k-1}{a-1}*c) \ mod \ n
$$
##### Choix du module
La solution la plus simple est d'utiliser un module de type $m = 2^e$. En effet, les ordinateurs calculant naturellement en base binaire, un tel choix est tout à fait transparent pour eux, ce qui rend inutile une division euclidienne.
Toutefois, ce choix présente une limite importante : les bits dits de poids faible (les bits les plus à droite) sont beaucoup moins aléatoires que ceux de la partie de poids fort (les bits les plus à gauche).
En effet, si $d$ est un diviseur de $m$, alors la suite $Y_n$ telle que : $Y_n=X_n \ mod \ d$ satisfait à la suite congruentielle linéaire : $Y_{n+1}=(a*Y_n+c) \ mod \ d$.
##### Choix du multiplicateur et de l'incrément
Afin de pouvoir choisir une graine $X_0$ dans contraintes entre $0$ et $m-1$, il faut chercher à maximiser la période fu générateur. Or il se trouve que les valeurs de $a$ et $c$ sont connues, ce qui permet d'obtenir une période maximale (égale à $m$).
Si $c \neq 0$ la période d'un générateur est maximale ssi :
1. $c$ est premier avec $m \to pgcd(c,m)=1$
2. Pour chaque nombre premier $p$ divisant $m, (a-1)$ est un multiple de $p$.
3. $(a-1)$ est un multiple de 4 si $m$ en est un.
##### Preuve de l'existence de $\lambda$ quelque soit l'ensemble fini de nombres (Répétition de la suite à un moment)
$(X_n) = X_0,X_1, X_2...$ vérifiant : $\forall n \in \mathbf{N}, 0 \leq X_n$
Soit $E = \{0,...,n_1\}$
Soit $f : E \rightarrow E$ quelconque
$$
\left\{
\begin{array}{ll}
X_{n+1} = f(X_n) \\
X_0 \text{ quelconque fixé}
\end{array}
\right.
$$
Pour générer des entiers:
$$
X_0, X_1 = f(X_0) \\
X_2 = f(X_1) \\
X_3 = f(X_2) \\
X_n = f(X_{n-1})
$$
Il s'agit donc de démontrer qu'il existe un $\lambda$ et un $\mu$ tel que : $X_0, X_1, ..., X_\mu, ... X_{\mu+\lambda-1}$ avec $\forall n \geq \mu$ on a $X_{n+\lambda} = X_n$ en d'autre terme que la séquence se répétant s'étende de $\mu$ à $\lambda$.
$$
\overbrace{
\underbrace{X_0, X_1, ..., X_{m-2}, X_{m-1}}_
{\text{m premières valeurs}}, X_m}
^{\text{m+1 valeurs}}, X_{m+1}
$$
$|E|=m$, E est un ensemble fini
Il existe donc au moins une répétition :
Soit $i_0<j_0 | X_{i_0} = X_{j_0}$
Si $X_{i_0} = X_{j_0}$ et que $X_{i_0+1}=f(X_{i_0})$ et $X_{j_0+1}=f(X_{j_0})$
Alors $X_{i_0+1}=X_{j_0+1}$
Par **récurrence**, $\forall l \geq 0$, $X_{i_0+l}=X_{j_0+l}$
Soit $\lambda = min(j_0 \neq i_0 \ | \ X_{i_0} = X_{j_0} \text{ et } i_0 < j_0 \leq m)$
$\lambda$ existe et est appelé période du générateur pour $X$
Soit $i_0$, la plus petite valeur validant : $X_{i_0} = X_{i_0+\lambda}$
On appelle $\mu$ la valeur de $i_0$
#### Générateur Blum Blum Shub (BBS)
$$
x_{n+1} = (x_n)^2 \ mod \ M
$$
Soit $M$ un produit de deux entiers premiers $p,q$, chacun de la forme $4m + 3$.
Les deux nombres premiers, $p$ et $q$, devraient tous deux être congrus à *3 modulo 4* (cela garantit que chaque résidu quadratique possède une racine carrée qui soit également un résidu quadratique) et le PGCD de $\varphi ( p − 1 )$ et $\varphi ( q − 1 )$ doit être petit (ce qui fait que le cycle est long et donc peu utilisé en simulation).
#### Le Mesernne Twister
Générateur de qualité très utilisé (Par *randint* de python par exemple).
### Suite aléatoire - Qu'est ce que c'est ?
#### Complexité de Kolmogorov
#### Tests statistiques
##### Test spectral
##### Diehard tet and bigcrush test
#### Trois degrés de hasard
## Génération d'objets combinatoires
### Quelque généralités
#### Le rejet
Lors d'un tirage il est possible de récupérer des valeurs qui ne nous intéressent pas ou ne satisfont pas nos besoins.
Par exemple pour générer des entiers en 0 et 5 on va générer 3 bits aléatoires mais sur 3 bits on peut aller jusqu'à 7. Les valeurs 6 et 7 ne nous intéressent pas.
Dans ce cas, il faut les rejetter et relancer le générateur.
Le problème qui se pose c'est qu'on ne peux pas prouver que l'algo termine parce qu'il est possible qu'on génère toujours 6 ou 7 et que donc l'algo finisse jamais mais en pratique ça n'arrive pas.
Soit $n>1$ un entier et définissons $\ell = \lceil \log_2 n \rceil$ le nombre de bits nécessaires pour générer uniformément un entier entre $0$ et $n-1$. Alors:
1. On génère $\ell$ bits qui représentent l'écriture binaire de l'entier $r$ généré.
2. Si cet entier vérifie $0 \leq r \leq n-1$, on le renvoie. Sinon on oublie $r$ et ses $\ell$ bits, et on recommence à l'étape 1.
*Remarque :* Si $n$ est une puissance de $2$, il n'y a pas de rejet nécessaire.
**Probabilité k rejets :**
$R(k \ rejets)=(1-\frac{n}{2^l})^k*\frac{n}{2^l}$
**Probabilité que l'algo se termine :**
Elle tends vers 1. Donc "presque souvent".
**Valeur moyenne du nombre de rejets :**
$\sum^\infty_{k=0}* (1-\frac{n}{2^l})^k*\frac{n}{2^l}$
### Générer des permutations
- *cons\_liste(n)* : construit une liste chaînée dont le premier élément est $1$, le deuxième est $2$
et le dernier est $n$.
- *tableau(n)* : déclare un tableau de $n$ cases numérotées de $1$ à $n$.
- *rand\_int(a,b)* : renvoie uniformément un entier entre $a$ et $b$ inclus.
- *extract(L, i)* : renvoie le $i$-ème élément de $L$, et supprime cet élément de $L$.
```python
def gen_permutation_1(n):
""" int -> tableau[int]
Hypothese : n>0
renvoie une permutation de taille n."""
L = cons_liste(n)
P = tableau(n)
for i in [1,2,...,n]:
r = rand_int(1,n+1-i)
P[i] = extract(L,r)
return P
```
```python
def gen_permutation2(n):
""" int -> tableau[int]
Hypothese : n>0
renvoie une permutation de taille n."""
P = tableau(n)
for i in [1,2,...,n]:
P[i] = i
for i in [1,2,...,n]:
r = rand_int(i, n)
tmp = P[i]
P[i] = P[r]
P[r] = tmp
return P
```
#### Calcul de la complexité en bit aléatoire pour les générateurs ad-hoc
Dans les algo `gen_permutation` 1 & 2 la consommation de bits aléatoire se fait au niveau du `rand_int`.
Dans le meilleurs des cas cette fonction aura une complexité de bits aléatoire de $\lceil log_{2} n\rceil$ (dans le cas où il n'y a pas de rejet).
**S'il y'a des rejets** il faut ajouter un facteur multiplicatif $\alpha$, ce sera donc $\alpha * \lceil log_{2} n\rceil$ avec $\alpha$ nombre de rejets.
$$
\sum^n_{i=1} \lceil log_{2} i\rceil \leq \sum^n_{i=1} log_{2} i+1\\
= n+\sum^n_{i=1}log_2i = n + log_2(\prod^n_{i=1}i) \\
=n+log_2(n!) \text{ Il s'agit de l'ordre de grandeur optimal}
$$
### Génération de structures arborescente
#### Algorithme de Rémy
Rémy a remarqué qu'il y a $2 ( 2 n − 1 )$ moyens de construire un arbre décoré de taille $n$ à partir d'un arbre décoré de taille $n − 1$.
On choisit uniformément un nœud interne ou externe (une feuille) dans cet arbre, appelons le $x$.
Comme il y a $n − 1$ nœuds internes et $n$ feuilles, il y a $2 n − 1$ choix possibles de $x$.
On insère alors un nouveau nœud interne et une nouvelle feuille décorée par $n$, dont elle est la fille droite ou la fille gauche, tandis que $x$ en est alors le fils gauche ou le fils droit.
```
Algo de Rémy (n : Entier correspondant au nombre de noeuds dans l'arbre final)
Tant que k <= n:
x = choix uniforme d'un noeud interne ou externe (feuille)
F = Le sous arbre enraciné en x
y = nouveau noeud
k = nombre de noeuds internes dans l'arbre
Si pile_Ou_Face() == 0:
F devient l'enfant de gauche de y
l'enfant de droite a une étiquette de k + 2
Sinon :
F devient l'enfant de droite de y
l'enfant de gauche a une étiquette de k + 2
F' = y et ses deux nouveaux enfants
Le sous arbre F' ainsi créer remplace F dans l'arbre global A
```
- `pile_Ou_Face()` renvoie de manière uniforme 0 ou 1
**Exemple pour l'arbre A $n = 6$:**
**Probabilité d'existence d'un arbre (preuve de l'uniformité des résultats):**
Si on calcul la probabilité d'existence de l'arbre A cela donne:
$$
R(A) = \underbrace{
\overbrace{1}^{\text{Choisir l'unique noeud}}
*
\overbrace{\frac{1}{2}}^{\text{Probabilité du pile ou face}}
}_{\text{1ere itération}}
\ *\frac{1}{3}*\frac{1}{2}
\ *\frac{1}{5}*\frac{1}{2}
\ *\frac{1}{7}*\frac{1}{2}
\ *\frac{1}{9}*\frac{1}{2}
\ *\frac{1}{11}*\frac{1}{2}
$$
Etant donnée un arbre B avec ses feuilles étiquettées, de taille $n$ ($n$ noeuds internes) sa probabilité d'être construit par l'algo sont :
$$
R(B)=(\frac{1}{2})^n*1*\frac{1}{3}*\frac{1}{5}*...\frac{1}{2n-1}
\\ \text{Cette formule ne dépend} \textbf{ que } \text{de la taille de l'arbre}
$$
Tous les arbres de **taille $n$** ont donc la même probabilité d'être construit.
**Preuve de complexité en bit aléatoire :**
Pour générer un arbre de taille $n$, on passe par les même étapes :
- On tire entre $0$-$0$ puis on fait pile ou face
- On tire entre $0$-$3$ puis on fait pile ou face
- On tire entre $0$-$5$ puis on fait pile ou face
- On tire entre $0$-$2n-1$ puis on fait pile ou face
- etc...
Coûts en bis aléatoires de ces étapes:
- 0+1
- $\lceil log \ 3 \rceil+1$
- $\lceil log \ 5 \rceil+1$
- $\lceil log \ (2n-1) \rceil+1$
- etc...
> Rappel du nombre de Stirling
> $n! \approx \sqrt{2 \pi n}*(\frac{n}{e})^n$
Donc
$$
=2n+log(1*3*5*...*2n-1) \\
=2n+log(\frac{(2n)!}{2*4*....*2n}) \\
=2n+log((2n)!)-log(2*4*....*2n) \\
=2n+log((2n)!)-log(2^n*n!) \\
\approx 2n+log(\sqrt{4 \pi n}*(\frac{2n}{e})^{2n})-log \ 2-log \ (\sqrt{2 \pi n})*(\frac{n}{e})^n) \\
\approx n + log(\sqrt{4 \pi n})+log((\frac{2n}{e})^{2n})-log(\sqrt{2 \pi n}-log((\frac{n}{e})^n) \\
\approx \alpha*(n \ log \ n) \text{avec } \alpha \in \mathbb{R}^+
$$
On peut montrer que l'on consomme $O(n \ log \ n)$ bits aléatoires.
Avec comme borne optimale : $C_n \approx log(\frac{4^n}{\sqrt{\pi n^3}}) = O(n)$
## Génération de graphe aléatoire
### Erdoös-Rényi
### Modèle A (Nombre de sommets prédéfini)
Soit $G_{n,m}$ un graphe avec $n$ sommets et $m$ arêtes.
$|G_{n,m}|={{n \choose 2} \choose m}$ est l'ensemble des graphes simples possibles de sommets $n$ et arêtes $m$.
Explication:
Le nombre d'arêtes $m$ possible pour un graphe de sommet n est ${n \choose 2}$. Nous devons donc choisir les graphes de $m$ arêtes parmi ces ${n \choose 2}$ graphes possibles. Ce qui montre la formule ci-dessus.
**Implémentation:**
```
n: Nombre de sommets
m: Nombre d'arêtes
G(n, m):
Initialiser une matrice vide = graph
Pour i allant de 0 à n:
Tirer aléatoirement uniformément deux arêtes u et v,
différents et pas encore connectés
Connecter u et v dans graph
retourner graph
```
### Model B (Probabilité d'apparition d'une arête entre deux sommets fixée)
Soit $G_{n,p}$ un graphe avec $n$ sommets obtenus en connectant chaque pairs de sommets avec une probabilité $p$.
### Distribution des degrés
C'est la probabilité d'avoir des sommets de degrés $k$ dans le graphe.
Cette probabilité suit une loi binomiale car c'est totalement indépendant du reste du graphe.
##### Exemples
> ordonnées = Probabilité du degrés
> abscisse = Degrés
Il s'agit d'un grand graphe gnp
Les courbes sont les attentes théoriques, les points les mesures expérimentales
### Phase de transition
C'est un phénomène très classique de la physique, il s'agit des plateaux représentant les différentes phases. L'exemple classique est celui de l'eau :
Et ce phénomène apprait aussi surprenanament dans les graphes aléatoires.
Ces phases représente l'apparition d'une propriété précise, un seuil critique va se dégager et sous ce dernier la propriété n'a aucune chance d'apparaitre dans les graphes tirés aléatoirement.
Il est a noter que le paramètre variable ici est le nombre de sommets.
### Théorème du composant géant
### Diamètre et rayon du graphe
Le diamètre est utile car il permet d'avoir la distance max entre deux points du graphe.
### Taille caractéristique du chemin dans $G_{n,p}$
Cetta taille est définie par la formule $L \approx \frac{Ln \ n}{...}$
### Configuration model
#### Modèle A
Soit $n>0, k>0$ et $k = (k_1,k_2,...,k_n)$ alors $G_{n,k}$ est un graphe avec $n$ sommets et $k$ arêtes tel que le sommet $n_i$ est de degré $k_i$.
- La probabilité qu'un graphe apparaisse dans un matching est différente selon le type de graphe (simple, multi-arêtes, self-loop)
- Tous les graphes simples dans cette configuration ont une distribution uniforme.
## Mathématiques
#### Arithmétique
$2^{32} \equiv 0 \mod 2^{31}$
L'inverse modulaire d'un entier $a \mod m$ est l'entier $b$ tel que :
$a.b \equiv 1 \mod m$
#### Combinatoire
Coefficient binomiale : $\binom{n}{k}=\frac{n!}{k!(n-k)!}$. (n choose k), choisir k éléments dans un ensemble de taille n.
Identité binomiale : $(1+x)^{n}=\sum _{k=0}^{n}{n \choose k}x^{k}$.
#### Probabilités
Soit $S$ un ensemble fini de possibilités. Aussi appelé $\Omega$ ou univers.
Soit $A \in S$ tel que $A$ est un évènement dans $S$.
Soit $P(A)$ la probabilité que l'évènement $A$ se réalise.
Alors $P(A)=\frac{|A|}{|S|}$
Si $X$ une **variable aléatoire** alors $X$ est une fonction qui à chaque issue de $\Omega$ associe un réel.
Définir la **loi de probabilité** de $X$, c'est donner les valeurs de $P(X=x_1),...,P(X=x_n)$.
#### Espérance
C'est la valeur qu'on obtiendra en moyenne à chaque tirage.
L'espérance de $X$ notée $E(X)=\sum p_i.x_i$ t.q $p_i$ est la probabibilté d'obtenir $x_i$
##### Exemple
Pour un dé cubique à 6 faces.
$\Omega=\{1,2,3,4,5,6\}$
Si un joueur obtient 1,2,3 ou 4. Il perd 5 euros
Si un joueur obtient 5. Il gagne 7 euros. Sinon il gagne 10 euros
Dire que si l'on obtient 1,2,3 ou 4 à l'issue d'un tirage équivaut à une perte de 5 euros signifie que :
La variable aléatoire $X=-5$ à une probabilité $P(X=-5)=P(1)*P(2)*P(3)*P(4)=\frac{2}{3}$
Alors, la loi de probabilité de $X$ est $P(X)=P(X=-5),P(X=7),P(X=10)$.
Avec $P(X=-5)=\frac{2}{3}$ $P(X=7)=\frac{1}{6}$ $P(X=10)=\frac{1}{6}$
Dans ce jeu l'espérance sera défini comme l'estimation du gain obtenu en moyenne après chaque partie.
$E(X)=\sum{p_i.x_i}=\frac{2}{3}.-5 + \frac{1}{6}.7 + \frac{1}{6}.10= -\frac{1}{2}$
**Interprétation:** On gagne(perd) -0.5 euros en moyenne à chaque partie. Ce qui veut dire que si on joue à 1000 parties, on perd en moyenne 500 euros.
#### Variance
$Var(X)=\sum_{i=0}^{n} p_i.(x_i - E(X))^2$
#### Suite numérique
$\sum_{i=1}^n i = \frac{n(n+1)}{2}$
#### Suite géométrique
$\sum_{i=0}^{n} q^i=\frac{1-q^{n+1}}{1-q}$
#### Primitives et dérivées usuelles
Sign in with Wallet
Connect another wallet