AnnalesÉcoles d'ingénieurs

Centrale-Supélec PSI 2019 — Maths 1

Analyse combinatoire de différents modèles d'urne · 5 pages

Le sujet présente la méthode de Flajolet pour les urnes équilibrées : après des préliminaires sur le développement en série entière de $(1 - x)^{-\alpha}$ à l'aide des polynômes $L_k = X(X + 1)\cdots(X + k - 1)$ , il montre que, dans l'urne de Pólya élémentaire, le nombre de boules blanches après $n$ tirages suit la loi uniforme sur $[\![1, n + 1]\!]$ . Il code ensuite les issues d'une urne équilibrée par des polynômes $P_n(u, v)$ dont la série génératrice exponentielle $H$ vérifie une équation aux dérivées partielles, ce qui donne la loi explicite de $X_n$ pour l'urne de Pólya générale. Il termine avec l'urne de Friedman, dont la loi s'obtient par développement limité, et une bijection entre tirages et permutations qui identifie le nombre de permutations de $\mathfrak{S}_n$ ayant $m$ montées.

Le sujet, partie par partie

Notations et Partie I — Résultats préliminaires p. 1

Séries entières · Équations différentielles linéaires · Familles sommables et produit de Cauchy · Coefficients binomiaux — série du binôme, produit de Cauchy, théorème de Cauchy linéaire, factorielle montante, formule de Vandermonde, série dérivée

Partie II — Un modèle particulier d'urne de Pólya p. 2

Processus de branchement et urnes · Fonctions génératrices · Probabilités totales et formule de Bayes · Espérance, variance, moments — urne de Pólya, fonction génératrice, loi uniforme discrète, formule des probabilités totales, relation de récurrence

Partie III — Modèle général d'urne équilibrée p. 2–3

Processus de branchement et urnes · Fonctions génératrices · Équations aux dérivées partielles · Séries entières · Interversion des limites · Dénombrement et combinatoire — urne équilibrée, série génératrice exponentielle, dérivée partielle, dérivation terme à terme, méthode de Flajolet, dénombrement des issues

Partie IV — Modèle général d'une urne de Pólya p. 3–4

Processus de branchement et urnes · Équations aux dérivées partielles · Séries entières · Interversion des limites · Espérance, variance, moments · Coefficients binomiaux — urne de Pólya, équation aux dérivées partielles, unicité des coefficients, série du binôme, loi de Pólya

Partie V.A — Urne de Friedman p. 4

Processus de branchement et urnes · Développements limités · Séries entières · Coefficients binomiaux · Fonctions génératrices — urne de Friedman, développement limité, fonction génératrice, somme alternée, nombres eulériens

Partie V.B — Montées d'une permutation p. 5

Dénombrement de configurations · Groupe symétrique · Processus de branchement et urnes — montées et descentes, permutations, nombres eulériens, bijection, algorithme d'insertion

Dans l'édifice

Séries entières et rayon de convergence Une série entière est holomorphe Les fonctions holomorphes sont analytiques Systèmes linéaires et exponentielle de matrices La demi-droite achevée et les sommes positives Ensembles finis et principe des tiroirs Martingales et temps d'arrêt Variables aléatoires, lois, fonctions de répartition Indépendance d'événements et de tribus Espérance, variance et inégalités Fonctions de classe Cᵏ Sommes, produits et puissances Dérivabilité Groupe symétrique et signature