Dans le chapitre 1, nous présentons les congruences linéaires simples et les tests de qualité des nombres pseudo-aléatoires (n.p.a.) congruentiels. L'accent est mis sur le test des treillis, le test spectral et le test sériel. Le test sériel est base sur l'estimation de la discrépance des vecteurs de n.p.a. Partant de cette estimation, on introduit une quantité appelée figure de mérite. Celle-ci nous permet de rechercher, pour m et b fixes, des multiplicateurs a tels que deux termes successifs de la suite (a,b,m,x#0) soient statistiquement indépendants. Nous débutons le chapitre 2 par l'étude des longueurs de cycle et du transitoire des suites engendrées par une congruence linéaire multidimensionnelle (c.l.m.). Ensuite, nous décrivons quelques méthodes de transformation de ces suites en suites de n.p.a. Enfin, nous faisons une discussion sur le choix des paramètres d'une c.l.m. Dans le chapitre 3, nous étudions la période d'un générateur vectoriel base sur le modèle de Daykin et une c.l.m. De période maximale, puis nous faisons un aperçu sur les principaux générateurs non linéaires de n.p.a. Le chapitre 4, réservé a la cryptographie, traite du problème du décryptage de l'ordre et du modulo d'une c.l.m

L'objectif principal de cette thèse est la description des propriétés de taille et de grande intersection des ensembles apparaissant lors de l'analyse multifractale de certains processus stochastiques. Dans ce but, nous introduisons de nouvelles classes d'ensembles à grande intersection associées à des fonctions de jauge générales et nous prouvons, à l'aide de techniques d'ubiquité, des résultats d'appartenance à ces classes pour certains ensembles limsup. Cela nous permet en particulier de décrire exhaustivement les propriétés de taille et de grande intersection des ensembles issus de la théorie classique de l'approximation diophantienne comme l'ensemble des points bien approchables par des rationnels ou l'ensemble des nombres de Liouville. Nous fournissons aussi des résultats du même type lorsque les rationnels intervenant dans l'approximation doivent vérifier certaines conditions, comme les conditions de Besicovitch. Nos techniques d'ubiquité nous permettent en outre de décrire complètement les propriétés de taille et de grande intersection des ensembles intervenant dans l'analyse multifractale des processus de Lévy et d'un modèle de séries lacunaires d'ondelettes. Nous obtenons des résultats similaires pour un nouveau modèle de séries aléatoires d'ondelettes dont les coefficients sont corrélés via une chaîne de Markov indexée par un arbre. Nous déterminons en particulier la loi du spectre de singularités de ce modèle. Pour mener cette étude, nous nous intéressons à une large classe de fractals aléatoires généralisant les constructions récursives aléatoires précédemment introduites par de nombreux auteurs.

Cette thèse se décompose en deux parties indépendantes. Notre objectif dans la première partie est d'étudier le comportement asymptotique des $U$-statistiques, basées sur des noyaux d'ordre 2, échantillonnées par une marche aléatoire. Plus précisément, on se donne $(S_n)_(n \in \N)$ une marche aléatoire sur $\Z^d$, $d \geq 1$ et $(\xi_x)_(x \in \Z^(d))$ une collection de variables aléatoires indépendantes, identiquement distribuées, indépendante de $(S_n)_(n \in \N)$. On note $\mu$ la loi de $\xi_0$ et l'on désigne par $h : \R^2\ra \R$, une fonction mesurable, symétrique, telle que $h \in L^2(\mu\otimes\mu)$. On s'intéresse au comportement asymptotique de la suite de processus, $$ \cU_n(t)=\sum_(i,j=0)^([nt])h(\xi_(S_i), \xi_(S_j)), \quad t\in[0,1], \quad n=0,1,\ldots, $$ à valeurs dans $\cD([0,1])$, l'espace des fonctions c.à.l.à.g. définies sur $[0,1]$, muni de la topologie de Skorohod. Cabus et Guillotin ont obtenu la distribution asymptotique de ces objets, dans le cas où la marche aléatoire, $(S_n)_(n \in \N)$, est récurrente sur $\Z^2$, ainsi que dans le cas où elle est transiente sur $\Z^d$, pour $d\geq3$. Elles ont également conjecturé la forme de la distribution limite, dans le cas de la marche aléatoire simple, symétrique, sur $\Z$. Dans le cas où $\Sn$ appartient au domaine d'attraction d'une loi stable d'indice $1<\alpha\leq2$, nous prouvons deux théorèmes limites fonctionnels, décrivant le comportement asymptotique de $\(\cU_n, n=1,2,\ldots\)$. Nous démontrons ainsi, la conjecture de Cabus et Guillotin. Par ailleurs, nous donnons une nouvelle preuve de leurs résultats.\\ Dans une seconde partie, nous étudions le comportement asymptotique du temps d'atteinte de deux versions d'un algorithme d'évolution simplifié, modélisant le repliement d'une protéine : le $(1+1)$-EA sur le problème LeadingOnes. Pour chaque algorithme nous donnons une loi des grands nombres, un théorème central limite et nous comparons la performance des deux modèles.\\

La marche de Sinai est un modèle élémentaire de marches aléatoires en milieu aléatoire unidimensionnelle effectuant des sauts unités sur ses plus proches voisins. On impose trois conditions sur le milieu aléatoire : deux hypothèses nécessaires pour obtenir un processus récurrent non réduit à un marche aléatoire simple et une hypothèse de régularité qui nous permet un bon contrôle des fluctuations du milieu aléatoire. Le comportement asymptotique de ce processus a été découvert par Y. Sinai en 1982 : il montre qu'il est sous diffusif et que pour instant n donné il est localisé dans le voisinage d'un point déterminé du réseau. Ce point est une variable aléatoire dépendant uniquement du milieu aléatoire et de n dont la distribution limite a été déterminée par H. Kesten et A. O. Golosov (indépendamment) en 1986. Une partie de cette thèse (partie II) a eu pour but de donner une preuve alternative au résultat de Y. Sinai . L'étude détaillée des résultats sur la localisation nous a permis de découvrir un nouvel aspect du comportement de la marche de Sinai que nous avons appelé concentration (partie III de la thèse). Nous avons montré que celle-ci était concentrée dans un voisinage restreint du point de localisation, c'est-à-dire que pour un intervalle de temps de longueur n la marche de Sinai passe la quasi-totalité de ce temps n dans un voisinage du point de localisation dont la taille est négligeable devant la distance parcourue. Nous avons également montré que le temps local de la marche de Sinai au point de localisation normalisé par n converge en probabilité vers une variable aléatoire dépendant uniquement du milieu et de n. Cette variable aléatoire est l'inverse de la moyenne du temps local dans la vallée où la marche de Sinai reste prisonnière, en un temps de retour au point de localisation. Les résultats que nous avons obtenus sont de type « trempé », c'est-à-dire que l'on travaille avec un milieu aléatoire appartenant à un sous-espace de probabilité du milieu aléatoire et on montre que ce sous-espace à une probabilité qui tend vers 1. De ces résultats est apparu des conséquences naturelles sur le maximum des temps locaux et le lieu favori de la marche de Sinai, notamment nous avons montré que la marche de Sinai et les lieux favoris de cette marche, correctement normalisés, ont même distribution limite.

La géométrie complexe est un outil puissant pour étudier les systèmes intégrables classiques, la physique statistique sur réseau aléatoire, les problèmes de matrices aléatoires, la théorie topologique des cordes, ...Tous ces problèmes ont en commun la présence de relations, appelées équations de boucle ou contraintes de Virasoro. Dans le cas le plus simple, leur solution complète a été trouvée récemment, et se formule naturellement en termes de géométrie différentielle sur une surface de Riemann : la "courbe spectrale", qui dépend du problème. Cette thèse est une contribution au développement de ces techniques et de leurs applications.Pour commencer, nous abordons les questions de développement asymptotique à tous les ordres lorsque N tend vers l'infini, des intégrales N-dimensionnelles venant de la théorie des matrices aléatoires de taille N par N, ou plus généralement des gaz de Coulomb. Nous expliquons comment établir, dans les modèles de matrice beta et dans un régime à une coupure, le développement asymptotique à tous les ordres en puissances de N. Nous appliquons ces résultats à l'étude des grandes déviations du maximum des valeurs propres dans les modèles beta, et en déduisons de façon heuristique des informations sur l'asymptotique à tous les ordres de la loi de Tracy-Widom beta, pour tout beta positif. Ensuite, nous examinons le lien entre intégrabilité et équations de boucle. En corolaire, nous pouvons démontrer l'heuristique précédente concernant l'asymptotique de la loi de Tracy-Widom pour les matrices hermitiennes.Nous terminons avec la résolution de problèmes combinatoires en toute topologie. En théorie topologique des cordes, une conjecture de Bouchard, Klemm, Mariño et Pasquetti affirme que des séries génératrices bien choisies d'invariants de Gromov-Witten dans les espaces de Calabi-Yau toriques, sont solution d'équations de boucle. Nous l'avons démontré dans le cas le plus simple, où ces invariants coïncident avec les nombres de Hurwitz simples. Nous expliquons les progrès récents vers la conjecture générale, en relation avec nos travaux. En physique statistique sur réseau aléatoire, nous avons résolu le modèle O(n) trivalent sur réseau aléatoire introduit par Kostov, et expliquons la démarche à suivre pour résoudre des modèles plus généraux.Tous ces travaux soulignent l'importance de certaines "intégrales de matrices généralisées" pour les applications futures. Nous indiquons quelques éléments appelant à une théorie générale, encore basée sur des "équations de boucles", pour les calculer

Les limites d'échelle de grands arbres aléatoires jouent un rôle central dans cette thèse.Nous nous intéressons plus spécifiquement au comportement asymptotique de plusieurs fonctions codant des arbres de Galton-Watson conditionnés. Nous envisageons plusieurs types de conditionnements faisant intervenir différentes quantités telles que le nombre total de sommets ou le nombre total de feuilles, avec des lois de reproductions différentes.Lorsque la loi de reproduction est critique et appartient au domaine d'attraction d'uneloi stable, un phénomène d'universalité se produit : ces arbres ressemblent à un même arbre aléatoire continu, l'arbre de Lévy stable. En revanche, lorsque la criticalité est brisée, la communauté de physique théorique a remarqué que des phénomènes de condensation peuvent survenir, ce qui signifie qu'avec grande probabilité, un sommet de l'arbre a un degré macroscopique comparable à la taille totale de l'arbre. Une partie de cette thèse consiste à mieux comprendre ce phénomène de condensation. Finalement, nous étudions des configurations non croisées aléatoires, obtenues à partir d'un polygône régulier en traçant des diagonales qui ne s'intersectent pas intérieurement, et remarquons qu'elles sont étroitement reliées à des arbres de Galton-Watson conditionnés à avoir un nombre de feuilles fixé. En particulier, ce lien jette un nouveau pont entre les dissections uniformes et les arbres de Galton-Watson, ce qui permet d'obtenir d'intéressantes conséquences de nature combinatoire.

Cette thèse porte sur plusieurs questions liées aux mesures de Yang-Mills planaires et aux champs markoviens d'holonomies planaires. Les problèmes sont de deux sortes : étude des champs markoviens d'holonomies planaires pour un groupe de structure donné et l'étude asymptotique des mesures de Yang-Mills lorsque la dimension du groupe tend vers l'infini. On définit la notion de champs markoviens d'holonomies planaires qui axiomatise la notion de mesures de Yang-Mills planaires. En utilisant une nouvelle symétrie en théorie des probabilités, l'invariance par tresse, on construit, caractérise et classifie les champs markoviens d'holonomies planaires. Nous montrons que tout champ markovien d'holonomies planaire est associé à un processus de Lévy qui satisfait une condition de symétrie et vice-versa. Ceci nous permet de caractériser, pour les surfaces sphériques, les champs markoviens d'holonomies tels que définis précédemment par Thierry Lévy. Lorsque le groupe de structure est le groupe symétrique, on peut construire le champ markovien d'holonomies planaire associé grâce à un modèle de revêtements aléatoires. On prouve la convergence des monodromies de ce revêtement aléatoire en s'appuyant sur l'étude, développée dans cette thèse, de l'asymptotique des matrices aléatoires invariantes par conjugaison par le groupe symétrique. / This thesis focuses on planar Yang-Mills measures and planar Markovian holonomy fields. We consider two different questions : the study of planar Markovian holonomy fields with fixed structure group and the asymptotic study of the planar Yang-Mills measures when the dimension of the structure group grows. We define the notion of planar Markovian holonomy fields which generalizes the concept of planar Yang-Mills measures. We construct, characterize and classify the planar Markovian holonomy fields by introducing a new symmetry : the invariance under the action of braids. We show that there is a bijection between planar Markovian holonomy fields and some equivalent classes of Lévy processes. We use these results in order to characterize Markovian holonomy fields on spherical surfaces. The Markovian holonomy fields with the symmetric group as structure group can be constructed using random ramified coverings. We prove that the monodromies of these models of random ramified coverings converge as the number of sheets of the covering goes to infinity. To prove this, we develop general tools in order to study the limits of families of random matrices invariant by the symmetric group. This allows us to generalize ideas, developped by Thierry Lévy in order to study the planar Yang-Mills measure with the unitary structure group, to the setting where the structure group is the symmetric group.

Dans cette thèse, on s'intéresse à des algorithmes d'analyse de données utilisant des marches aléatoires sur des graphes de voisinage, ou graphes géométriques aléatoires, construits à partir des données. On sait que les marches aléatoires sur ces graphes sont des approximations d'objets continus appelés processus de diffusion. Dans un premier temps, nous utilisons ce résultat pour proposer un nouvel algorithme de partitionnement de données flou de type recherche de modes. Dans cet algorithme, on définit les paquets en utilisant les propriétés d'un certain processus de diffusion que l'on approche par une marche aléatoire sur un graphe de voisinage. Après avoir prouvé la convergence de notre algorithme, nous étudions ses performances empiriques sur plusieurs jeux de données. Nous nous intéressons ensuite à la convergence des mesures stationnaires des marches aléatoires sur des graphes géométriques aléatoires vers la mesure stationnaire du processus de diffusion limite. En utilisant une approche basée sur la méthode de Stein, nous arrivons à quantifier cette convergence. Notre résultat s'applique en fait dans un cadre plus général que les marches aléatoires sur les graphes de voisinage et nous l'utilisons pour prouver d'autres résultats : par exemple, nous arrivons à obtenir des vitesses de convergence pour le théorème central limite. Dans la dernière partie de cette thèse, nous utilisons un concept de topologie algébrique appelé homologie persistante afin d'améliorer l'étape de "pooling" dans l'approche "sac-de-mots" pour la reconnaissance de formes 3D. / In this thesis, we study data analysis algorithms using random walks on neighborhood graphs, or random geometric graphs. It is known random walks on such graphs approximate continuous objects called diffusion processes. In the first part of this thesis, we use this approximation result to propose a new soft clustering algorithm based on the mode seeking framework. For our algorithm, we want to define clusters using the properties of a diffusion process. Since we do not have access to this continuous process, our algorithm uses a random walk on a random geometric graph instead. After proving the consistency of our algorithm, we evaluate its efficiency on both real and synthetic data. We then deal tackle the issue of the convergence of invariant measures of random walks on random geometric graphs. As these random walks converge to a diffusion process, we can expect their invariant measures to converge to the invariant measure of this diffusion process. Using an approach based on Stein's method, we manage to obtain quantitfy this convergence. Moreover, the method we use is more general and can be used to obtain other results such as convergence rates for the Central Limit Theorem. In the last part of this thesis, we use the concept of persistent homology, a concept of algebraic topology, to improve the pooling step of the bag-of-words approach for 3D shapes.

Dans cette thèse, nous étudions les graphes aléatoires en utilisant des outils de la théorie des matrices aléatoires et l’analyse probabilistique afin de résoudre des problèmes clefs dans le domaine des réseaux complexes et Big Data. Le premier problème qu’on considère est de détecter un sous graphe Erdős–Rényi G(m,p) plante dans un graphe Erdős–Rényi G(n,q). Nous dérivons les distributions d’une statistique basée sur les propriétés spectrales d’une matrice définie du graphe. Ensuite, nous considérons le problème de la récupération des sommets du sous graphe en présence de l’information supplémentaire. Pour cela nous utilisons l’algorithme «Belief Propagation». Le BP sans informations supplémentaires ne réussit à la récupération qu’avec un SNR effectif lambda au-delà d’un seuil. Nous prouvons qu’en présence des informations supplémentaires, ce seuil disparaît et le BP réussi pour n’importe quel lambda. Finalement, nous dérivons des expressions asymptotiques pour PageRank sur une classe de graphes aléatoires non dirigés appelés « fast expanders », en utilisant des techniques théoriques à la matrice aléatoire. Nous montrons que PageRank peut être approché pour les grandes tailles du graphe comme une combinaison convexe du vecteur de dégré normalisé et le vecteur de personnalisation du PageRank, lorsque le vecteur de personnalisation est suffisamment délocalisé. Par la suite, nous caractérisons les formes asymptotiques de PageRank sur le Stochastic Block Model (SBM) et montrons qu’il contient un terme de correction qui est fonction de la structure de la communauté. / In this thesis, we study random graphs using tools from Random Matrix Theory and probability to tackle key problems in complex networks and Big Data. First we study graph anomaly detection. Consider an Erdős-Rényi (ER) graph with edge probability q and size n containing a planted subgraph of size m and probability p. We derive a statistical test based on the eigenvalue and eigenvector properties of a suitably defined matrix to detect the planted subgraph. We analyze the distribution of the derived test statistic using Random Matrix Theoretic techniques. Next, we consider subgraph recovery in this model in the presence of side-information. We analyse the effect of side-information on the detectability threshold of Belief Propagation (BP) applied to the above problem. We show that BP correctly recovers the subgraph even with noisy side-information for any positive value of an effective SNR parameter. This is in contrast to BP without side-information which requires the SNR to be above a certain threshold. Finally, we study the asymptotic behaviour of PageRank on a class of undirected random graphs called fast expanders, using Random Matrix Theoretic techniques. We show that PageRank can be approximated for large graph sizes as a convex combination of the normalized degree vector and the personalization vector of the PageRank, when the personalization vector is sufficiently delocalized. Subsequently, we characterize asymptotic PageRank on Stochastic Block Model (SBM) graphs, and show that it contains a correction term that is a function of the community structure.

Nous nous penchons sur les fluctuations des marches dans plusieurs modèles de marches aléatoires en milieux aléatoires. En particulier, le résultat principal de ce mémoire est de prouver qu'il existe un théorème central limite trempé pour la marche aléatoire sur un arbre de Galton-Watson infini avec feuilles équipé de biais aléatoires plus grand que 1. Un tel théorème a été prouvé dans le cas où le biais est constant dans [1]; il s'agit donc de généraliser ce théorème. / We examine the fluctuations of walks in multiple models of random walks in random environments. In particular, the primary result of this dissertation is to prove there exists a quenched central limit theorem for the random on an infinite Galton-Watson tree with leaves equiped with random biases greater than 1. Such a theorem has already been proven in the case where the bias is constant in [1]; this is a generalization of that theorem.