Ce mémoire de thèse est consacré à l'étude de quelques problèmes de probabilités provenant de l'informatique théorique. Dans une première partie, nous étudions un algorithme probabiliste qui compte le nombre de mots différents dans une liste. Nous montrons que l'étude peut se ramener à un problème d'estimation, et qu'en modifiant légèrement cet algorithme, il est d'une certaine manière optimal. La deuxième partie est consacrée à l'étude de plusieurs problèmes de convergences pour des systèmes finis de particules, nous envisageons différents types de passage à une limite infinie. La première famille de systèmes considérés est une classe particulière d'automates cellulaires. En dimension 1, il apparaît des marches aléatoires dont nous caractérisons de façon complète les comportements limites. En dimension 2, sur une grille carrée, nous étudions quelques-un des cas les plus représentatifs. Nous en déterminons le temps moyen de convergence vers une configuration fixe. Enfin, nous étudions un modèle d'urnes avec des boules à deux états. Dans la troisième partie, nous étudions deux problèmes particuliers de marches aléatoires. Ces deux questions sont initialement motivées par l'étude de certains automates cellulaires, mais nous les présentons de façon indépendante. Le premier de ces deux problèmes est l'étude de marches aléatoires sur un tore discret, réfléchies les unes sur les autres. On montre la convergence de ce processus vers une limite brownienne. Nous étudions enfin de façon entièrement combinatoire une famille de marches aléatoires sur un intervalle, biaisées vers le bas. Nous déterminons le temps moyen de sortie vers le haut de la marche. / This thesis deals with several problems in probability, mostly motivated by theoretical computer science. In the first part, we study of a probabilistic algorithm that counts the number of different words in a given sequence, by boiling it down to a statistical problem. We show that slightly improved, it achieves an optimal bound. The second and main part is devoted to different asymptotic problems concerning finite particle systems, for which we consider different kinds of infinite limits. We first deal with cellular automata. In dimension one, it appears random walks for which we entirely describe the asymptotic behaviors. In dimension two, on a square grid, we study some caracteristic rules for which we estimate the converge time. Lastly, we study a family of urn models. The third part focuses on two random walks problems. These questions where motivated by the study of cellular automata, but presented here in a self-contained way. The first problem is the study of a family of self-reflected random walks on a circle, for which we show a ``brownian limit''. The latter is a combinatorial description of a family of biased random walks on an interval.

Nous étudions des équations aux dérivées partielles non linéaires du type McKean-Vlasov. Nous leur associons des systèmes de particules en interaction de type champ moyen pour lesquels nous établissons des inégalités de Sobolev logarithmiques à temps fini. Grâce à un résultat supplémentaire de propagation du chaos, nous déduisons, dans certains cas, le comportement en temps long de l'équation non linéaire en fonction de celui du système de particules. Enfin, nous établissons des intervalles de confiance exacts pour la convergence de méthodes de Monte-Carlo pour les schémas d'Euler explicites et implicites associés à des processus de diffusion. Ces résultats s'appliquent notamment pour les systèmes de particules cités plus haut.

Ce mémoire de thèse est consacré à l'étude de quelques problèmes de probabilités provenant de l'informatique théorique. Dans une première partie, nous étudions un algorithme probabiliste qui compte le nombre de mots différents dans une liste. Nous montrons que l'étude peut se ramener à un problème d'estimation, et qu'en modifiant légèrement cet algorithme, il est d'une certaine manière optimal. La deuxième partie est consacrée à l'étude de plusieurs problèmes de convergences pour des systèmes finis de particules, nous envisageons différents types de passage à une limite infinie. La première famille de systèmes considérés est une classe particulière d'automates cellulaires. En dimension 1, il apparaît des marches aléatoires dont nous caractérisons de façon complète les comportements limites. En dimension 2, sur une grille carrée, nous étudions quelques-un des cas les plus représentatifs. Nous en déterminons le temps moyen de convergence vers une configuration fixe. Enfin, nous étudions un modèle d'urnes avec des boules à deux états. Dans la troisième partie, nous étudions deux problèmes particuliers de marches aléatoires. Ces deux questions sont initialement motivées par l'étude de certains automates cellulaires, mais nous les présentons de façon indépendante. Le premier de ces deux problèmes est l'étude de marches aléatoires sur un tore discret, réfléchies les unes sur les autres. On montre la convergence de ce processus vers une limite brownienne. Nous étudions enfin de façon entièrement combinatoire une famille de marches aléatoires sur un intervalle, biaisées vers le bas. Nous en déterminons le temps moyen de sortie vers le haut.

La synthèse d'images de paysages naturels reste encore un problème peu abordé en infographie. Pourtant, des modèles convaincants en particulier pour la modélisation de végétaux existent, mais n'ont pu être exploités dans des scènes comportant un nombre très important d'éléments. Je présente dans ce travail, une approche pour la modélisation et le rendu d'objets naturels qui doit permettre de contourner l'obstacle de la complexité géométrique et offrir un cadre simple pour la création de structures naturelles. Ainsi un modèle basé sur les systèmes de particules est proposé pour la création de structures végétales. Ce modèle fait appel à la définition d'un automate pour le contrôle des trajectoires, de la création et de la destruction des particules. Il peut être également utilisé pour modéliser et rendre un certain nombre d'autres phénomènes naturels (nuages, eau...). Par ailleurs, une scène de paysage naturel se compose de très nombreux éléments ayant des échelles très différentes sur l'image finale. Aussi nous proposons des techniques rapides et précises, basées sur les multi-textures, qui permettent un rendu multi-échelles efficace des éléments de végétation. De part leurs caractéristiques, ces méthodes peuvent être intégrées dans une architecture spécialisée pour la synthèse d'images de paysages naturels que nous présentons.

Les résultats de cette thèse sont composés de trois parties relativement indépendantes. Dans la première partie, nous reprenons le problème de la définition d'une classe de processus markoviens à une infinité de coordonnées (systèmes de particules en interaction). Nous en proposons une construction ne mettant en jeu ni d'analyse fonctionnelle (ou peu), ni de problème de martingale. Ceci est fait en utilisant des outils probabilistes élémentaires, notamment des couplages adéquats. On fait pour cela une certaine hypothèse sur les taux individuels de transition, qui a été déjà exploitée dans la construction de T. M. Liggett (1972) notamment. Notre construction a l'avantage d'expliquer, plus concrètement que dans les autres constructions, le caractère naturel de cette hypothèse. \\Dans une seconde partie, nous considérons un modèle de croissance cristalline introduit par D. J. Gates et M. Westcott en 1987, où des particules du milieu environnant s'agrègent à la surface d'un cristal à maille carrée. Le modèle est caractérisé par des taux de déposition en chaque site qui prennent une certaine forme. Nos résultats portent principalement sur la question de la récurrence et de la récurrence positive de la surface du cristal en fonction de certains paramètres. Nous montrons notamment l'existence d'une zone de paramètres dans laquelle transience et récurrence positive coexistent, et suspectée de présenter un phénomène critique. La troisième partie porte sur la question de la convergence en loi pour le processus de contact (sur Z) sous-critique vu du bord, partant d'une demi-droite de sites occupés. Nous donnons dans un premier temps une démonstration alternative d'un résultat récent de E. D. Andjel, pour la convergence en loi dans la percolation 2D orientée qui est un équivalent discret du contact. Nous établissons un résultat en relation : le processus de contact vu du bord, sur les configurations finies, admet une limite de Yaglom. Enfin nous mettons en évidence les difficultés à surmonter pour adapter le résultat d'Andjel au temps continu.

Le processus d’exclusion simple est défini formellement de la façon suivante : chaque particule effectue une marche aléatoire sur un ensemble de sites et interagit avec les autres particules en ne se déplaçant jamais sur un site occupé.Malgré sa simplicité, ce processus présente des propriétés que l’on retrouve dans beaucoup de modèles de mécanique statistique plus complexes. C’est la conjonction de la simplicité du processus et de l’intérêt des phénomènes observés quien fait l’un des modèles de référence en mécanique statistique hors équilibre. Dans cette thèse, je me suis intéressé au cas du processus d’exclusion totalement asymétrique (les particules sautent uniquement vers la droite) sur Nafin d’étudier son comportement en fonction du mécanisme de création de particules: on crée des particules au site 0 avec un taux dépendant de la configurationactuelle. Dès que ce mécanisme n’est plus un processus de Poisson, le processusd’exclusion associé n’admet plus de mesure invariante sous forme de produitce qui fait que les méthodes classiques de calcul sur le générateur infinitésimaln’aboutissent que rarement. Je me suis donc appuyé principalement sur les méthodesde couplage et de particules de deuxième classe.Dans la première partie de la thèse, je me suis intéressé au modèle introduitpar Grosskinsky pour lequel j’ai obtenu les résultats suivants : si le taux maximumde création et la densité initiale de particules sont plus petits que 12 et sile mécanisme de création est à portée intégrable, il n’y a pas de transition dephase c’est-à-dire qu’il n’y a qu’une seule mesure invariante.Dans la deuxième partie de la thèse, je me suis intéressé au problème inversedont le but est de construire un processus à portée finie mais non-intégrableayant une transition de phase. Pour cela, je me suis inspiré des méthodes développéespour le processus des spécifications de Bramson et Kalikow. / The simple exclusion process is formally defined as follows : each particle performs a simple random walk on a set of sites and interacts with other particles by never moving on occupied sites. Despite its simplicity, this process has properties that are found in many more complex statistical mechanics models. It is the combination of the simplicity of the process and the importance of the observed phenomena that make it one of the reference models in out of equilibrium statistical mechanics. In this thesis, I’m interested in the case of the totally asymmetric exclusion process (particles jump only to the right) on N to study its behavior according to the mechanism of particle creation : particles are created at site 0 with arate depending on the current configuration. Once this mechanism is no longer a Poisson process, the associated exclusion process does not admit a product invariant measure. As a consequence, classical computation methods with theinfinitesimal generator are rarely successful. So I used mainly the methods of coupling and second class particles.In the first part of the thesis, I’m interested in the model introduced by Grosskinsky for which I get the following result : if the maximum rate of creation and the initial density of particles are smaller than 12 and if the creation mechanism is of integrable range, there is no phase transition which means that there is only one invariant measure. In the second part of the thesis, my goal was to construct a process with finite and non-integrable range that has a phase transition. For this, I was inspired by methods developed for the process of specification of Bramson and Kalikow.

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

Le sujet principal de la thèse sont les systèmes de particules en interaction sur des graphes soit deterministes soit aléatoires. Les systèmes de particules en interaction sont des processus de Markov qui décrivent l'évolution de particules indistingables en interaction forte les unes avec les autres qui sont utilisés pour modéliser des phénomènes d'épidémies, de dynamiques des populations ou des processus chimiques. Dans la première partie de la thèse nous avons analysé l'ordre stochastique et l'attractivité dans une classe de systèmes de particules avec des naissances, des morts et des sauts de plus d'une particule à la fois qui dépendent de la conguration de manière très générale: nous avons utilisé l'attractivité pour obtenir des resultats d'ergodicité pour des modèles d'epidemie et pour construire des mesures invariantes non-triviales pour des modèles de dinamiques de métapopulations. Dans la deuxième partie de la thèse nous avons analysé les marches aléatoires coalescentes sur des graphes aléatoires, les graphes small world. Nous avons montré que le nombre de particules d'un processus de n marches aléatoires coalescentes renormalisées qui partent d'une ensemble particulier sur le small world converge vers un processus coalescent de Kingman. Nous avons aussi obtenu des resultats detaillés sur le temps de rencontre de deux particules sur le small world.

Ce document de synthèse est consacré à l'interprétation probabiliste de certaines équations d'évolution liénaires ou non-linéaires ainsi qu'à l'étude de méthodes numériques probabilistes. La première partie réunit plusieurs résultats qui mettent en évidence les liens qui existent entre les équations aux dérivées partielles et les processus de diffusion pour des modèles linéaires ou non-linéaires. Un paragraphe important est consacré à l'approche probabiliste des modèles de coagulation et/ou fragmentation. Nous présentons dans la seconde partie la construction de nouveaux algorithmes de simulation de type Monte-Carlo pour une large classe d'équations différentielles stochastiques. Cette méthode permet d'estimer de façon précise le premier moment de sortie d'un domaine et la position de sortie pour un processus stochastique. Nous nous intéressons ensuite aux techniques d'échantillonnage pondéré afin de réduire la variance de nos éstimateurs. Dans la troisième partie nous présentons des travaux sur l'analyse fine de certains processus stochastiques dans les espaces de Besov. La quatrième partie est consacrée à des applications issues de collaborations industrielles.

Les travaux présentés concernent trois thématiques connexes~: Interprétation et étude probabiliste d'équations de McKean-Vlasov - propagation du chaos, - estimation quantitative de la convergence à l'équilibre, - modèles cinétiques. Inégalités fonctionnelles - inégalités fonctionnelles et concentration de la mesure pour les schémas d'Euler, - comportement en temps long de diffusions inhomogènes, - inégalités fonctionnelles et concentration de la mesure pour un mélange. Processus de Markov déterministes par morceaux - modélisation markovienne (télécomunications, biologie, chimie), - construction de couplage explicites et convergence en temps long, - propriétés de la mesure invariante. Le fil rouge de ce travail est la recherche de bornes quantitatives pour l'étude de processus de Markov issus de la modélisation (physique, biologie, etc). Souvent, ces processus possèdent des propriétés de symétrie, de régularité ou de monotonie qu'il est possible d'exploiter pour étudier finement leurs comportements. L'idée est donc ici non pas de chercher à établir des propriétés génériques et qualitatives valables pour la classe la plus large de processus mais bien d'utiliser la dynamique spécifique des processus étudiés pour décrire leur convergence à l'équilibre.