Tableau d’honneur de la Faculté des études supérieures et postdoctorales, 2012-2013. / Cette thèse a pour but d'élaborer et d'étudier des modèles mathématiques reproduisant le comportement de systèmes composés de plusieurs éléments dont les interactions forment un réseau complexe. Le corps du document est découpé en trois parties ; un chapitre introductif et une conclusion récapitulative complétent la thèse. La partie I s'intéresse à une dynamique spécifique (propagation de type susceptibleinfectieux- retiré, SIR) sur une classe de réseaux également spécifique (modèle de configuration). Ce problème a entre autres déjà été étudié comme un processus de branchement dans la limite où la taille du système est infinie, fournissant une solution probabiliste pour l'état final de ce processus stochastique. La principale contribution originale de la partie I consiste à modifier ce modèle afin d'introduire des éffets dûs à la taille finie du système et de permettre l'étude de son évolution temporelle (temps discret) tout en préservant la nature probabiliste de la solution. La partie II, contenant les principales contributions originales de cette thèse, s'intéresse aux processus stochastiques sur réseaux complexes en général. L'état du système (incluant la structure d'interaction) est partiellement représenté à l'aide de motifs, et l'évolution temporelle (temps continu) est étudiée à l'aide d'un processus de Markov. Malgré que l'état ne soit que partiellement représenté, des résultats satisfaisants sont souvent possibles. Dans le cas particulier du problème étudié en partie I, les résultats sont exacts. L'approche se révèle très générale, et de simples méthodes d'approximation permettent d'obtenir une solution pour des cas d'une complexité appréciable. La partie III cherche une solution analytique exacte sous forme fermée au modèle développé en partie II pour le problème initialement étudié en partie I. Le système est réexprimé en terme d'opérateurs et différentes relations sont utilisées afinn de tenter de le résoudre. Malgré l'échec de cette entreprise, certains résultats méritent mention, notamment une généralisation de la relation de Sack, un cas particulier de la relation de Zassenhaus. / The goal of this thesis is to develop and study mathematical models reproducing the behaviour of systems composed of numerous elements whose interactions make a complex network structure. The body of the document is divided in three parts; an introductory chapter and a recapitulative conclusion complete the thesis. Part I pertains to a specific dynamics (susceptible-infectious-removed propagation, SIR) on a class of networks that is also specific (configuration model). This problem has already been studied, among other ways, as a branching process in the infinite system size limit, providing a probabilistic solution for the final state of this stochastic process. The principal original contribution of part I consists of modifying this model in order to introduce finite-size effects and to allow the study of its (discrete) time evolution while preserving the probabilistic nature of the solution. Part II, containing the principal contributions of this thesis, is interested in the general problem of stochastic processes on complex networks. The state of the system (including the interaction structure) is partially represented through motifs, then the (continuous) time evolution is studied with a Markov process. Although the state is only partially represented, satisfactory results are often possible. In the particular case of the problem studied in part I, the results are exact. The approach turns out to be very general, and simple approximation methods allow one to obtain a solution for cases of considerable complexity. Part III searches for a closed form exact analytical solution to the the model developed in part II for the problem initially studied in part I. The system is re-expressed in terms of operators and different relations are used in an attempt to solve it. Despite the failure of this enterprise, some results deserve mention, notably a generalization of Sack's relationship, a special case of the Zassenhaus relationship.

De manière générale, les problèmes séquentiels de décisions multiagents sont très difficiles à résoudre surtout lorsque les agents n'observent pas parfaitement ni complètement l'état de leur environnement. Les modèles actuels pour représenter ces problèmes restent à ce jour très généraux et difficilement applicables dans les multiples applications possibles. Nous proposons dans cette thèse plusieurs approches de réduction de la complexité computationnelle et en pire cas de ces modèles. Une première approche se base sur l'utilisation de contraintes sur l'espace des actions possibles que les différents agents du système peuvent entreprendre. Cette utilisation de connaissances a priori dans la modélisation au travers de modèles déjà connus, mais non appliqués à la prise de décision séquentielle permet une réduction significative d'un des facteurs de la complexité algorithmique. La seconde approche consiste à restreindre les possibilités d'observations de l'agent à un ensemble similaire à l'espace d'états utilisé pour représenter son environnement. De cette manière, nous montrons que les agents peuvent converger rapidement en probabilité vers des croyances communes sans nécessairement avoir à communiquer. Dans ce contexte, nous avons également développé un algorithme permettant alors aux agents de se coordonner au moment de l'exécution lorsqu'il n'existe pas de communication explicite. Enfin, nous avons entrepris la mise en application de telles réductions à deux problèmes. Un premier problème de patrouille multiagent est considéré et modélisé, et un second problème lié à l'apprentissage de POMDPS continus dans des cas précis de transition et d'observabilité est également abordé. Les résultats obtenus montrent que dans certains cas de problèmes de coordination, la communication ? lorsqu'elle est disponible ? est non négligeable, et que dans le cas de l'apprentissage de POMDPs, considérer le quasi-déterminisme du modèle permet l'apprentissage de converger.

Les mathématiques offrent un cadre convenable pour raisonner rigoureusement sur les systèmes et phénomènes réels. Par exemple, en génie logiciel, les méthodes formelles sont parmi les outils les plus efficaces pour détecter les anomalies dans les logiciels. Plusieurs systèmes réels sont stochastiques par nature dans le sens où leur comportement est sujet à un aspect d'incertitude. La représentation de ce genre de systèmes requiert des modèles stochastiques comme les processus de Markov étiquetés (LMP), les processus de Markov décisionnels (MDP), etc. Cette thèse porte sur la quantification de la différence entre les systèmes stochastiques. Les contributions majeures sont : 1. une nouvelle approche pour quantifier la divergence entre les systèmes stochastiques basée sur l'apprentissage par renforcement, 2. une nouvelle famille de notions d'équivalence qui se situe entre l'équivalence par trace et la bisimulation, et 3. un cadre plus flexible pour la définition des notions d'équivalence qui se base sur les tests. Le résultat principal de la thèse est que l'apprentissage par renforcement, qui est une branche de l'intelligence artificielle particulièrement efficace en présence d'incertitude, peut être utilisé pour quantifier efficacement cette divergence. L'idée clé est de définir un MDP à partir des systèmes à comparer de telle sorte que la valeur optimale de cet MDP corresponde à la divergence entre eux. La caractéristique la plus attrayante de l'approche proposée est qu'elle est complètement indépendante des structures internes des systèmes à comparer. Pour cette raison, l'approche peut être appliquée à différents types de systèmes stochastiques. La deuxième contribution est une nouvelle famille de notions d'équivalence, que nous appelons moment, qui est plus forte que l'équivalence par trace mais plus faible que la bisimulation. Cette famille se définit naturellement à travers la coïncidence de moments de variable aléatoires (d'où son nom) et possède une caractérisation simple en terme de tests. Nous montrons que moment fait partie d'un cadre plus grand, appelé test-observation-equivalence (TOE), qui constitue la troisième contribution de cette thèse. Il s'agit d'un cadre plus flexible pour la définition des notions d'équivalence basé sur les tests. / Modelling real-life systems and phenomena using mathematical based formalisms is ubiquitous in science and engineering. The reason is that mathematics offer a suitable framework to carry out formal and rigorous analysis of these systems. For instance, in software engineering, formal methods are among the most efficient tools to identify flaws in software. The behavior of many real-life systems is inherently stochastic which requires stochastic models such as labelled Markov processes (LMPs), Markov decision processes (MDPs), predictive state representations (PSRs), etc. This thesis is about quantifying the difference between stochastic systems. The main contributions are: 1. a new approach to quantify the divergence between pairs of stochastic systems based on reinforcement learning, 2. a new family of equivalence notions which lies between trace equivalence and bisimulation, and 3. a refined testing framework to define equivalence notions. The important point of the thesis is that reinforcement learning (RL), a branch of artificial intelligence particularly efficient in presence of uncertainty, can be used to quantify efficiently the divergence between stochastic systems. The key idea is to define an MDP out of the systems to be compared and then to interpret the optimal value of the MDP as the divergence between them. The most appealing feature of the proposed approach is that it does not rely on the knowledge of the internal structure of the systems. Only a possibility of interacting with them is required. Because of this, the approach can be extended to different types of stochastic systems. The second contribution is a new family of equivalence notions, moment, that constitute a good compromise between trace equivalence (too weak) and bisimulation (too strong). This family has a natural definition using coincidence of moments of random variables but more importantly, it has a simple testing characterization. moment turns out to be part of a bigger framework called test-observation-equivalence (TOE), which we propose as a third contribution of this thesis. It is a refined testing framework to define equivalence notions with more flexibility.

Dans cette thèse, on s'intéresse à la notion de temps fort de stationnarité et à celle, étroitement liée, de dual de stationnarité forte. Ces outils permettent d'étu- dier la convergence de processus ergodiques, en déterminant un instant aléatoire où l'équilibre est atteint. Les espaces d'état des processus considérés ici sont des graphes continus ou discrets. Dans la première partie, on considère le cas discret, et on dégage une condition nécessaire et suffisante à l'existence, pour n'importe quelle loi initiale, d'un temps fort de stationnarité fini. Pour cela, on construit explicitement un dual de station- narité forte, à valeurs dans l'ensemble des parties connexes du graphe, qui évolue à chaque étape en ajoutant ou en enlevant des points de sa frontière. Lorsque cette opération sépare l'ensemble dual en plusieurs parties, afin de ne pas le déconnecter, une de ces parties est choisie au hasard, avec une probabilité proportionnelle à son poids par la mesure invariante. On s'intéresse également au comportement général d'un processus dual, et on donne quelques exemples différents de celui construit précédemment. Dans la deuxième partie, on traite le cas continu, et le processus étudié est alors une diffusion. On caractérise notamment sa mesure invariante, et on explicite un générateur infinitésimal qui devrait être celui d'un processus dual. Néanmoins, ce cas s'avère plus compliqué que le cas discret. Le processus dual n'est donc construit que pour un mouvement brownien sur un graphe particulier, comme l'unique so- lution d'un problème de martingale. Des pistes sont présentées pour traiter des diffusions sur des graphes plus généraux, notamment en utilisant la convergence d'une suite de processus de saut tels que ceux présentés dans la première partie. / In this thesis, we are interested in the notion of strong stationary time, and in that, strongly connected, of strong stationary dual. These tools allow to study the convergence of ergodic processes, by determining a random time when the equilibrium is reached. The state space of the considered processes are discrete or continuous graphs. In the first part, we consider the discrete case, and we explicit a necessary and sufficient condition to the existence, for any initial distribution, of a finite strong stationary time. To do so, we construct explicitly a strong stationary dual, with values in the set of connected subsets of the graph, which evolves at each step by adding or removing some points at its border. Whenever this operation separates the dual set in several parts, in order not to disconnect it, one of these parts is chosen randomly, with a probability proportionnal to its weight relative to the invariant distribution. We also study the general behaviour of any dual process,2 and we give some other examples. In the second part, we deal with the continuous case, and the studied process is then a diffuion. We caracterize its invariant distribution, and we explicit an infinitesimal generator, which is expected to be that of a dual process. Nevertheless, this case turns out to be a little more involved that the discrete one. The dual process is thus constructed only for a brownian motion on a particular graph, as the unique solution of a martingale problem. Some leads are given to solve the case of diffusions on more general graphs, especially by using the convergence of a sequence of jump processes such as those presented in the first part.

Le sujet principal de cette thèse de doctorat est l'étude de diverses quantités reliées aux processus de fragmentation. Ces processus sont destinés à modéliser un objet de masse unité se fragmentant au cours du temps.<br />Ce travail comporte quatre chapitres. Le premier chapitre est consacré à l'étude de la dimension de Hausdorff de l'ensemble des points ayant une décroissance exponentielle dans une fragmentation homogène en intervalles. Dans le deuxième chapitre, on construit un processus de Markov auto-similaire qui généralise les fragmentations classiques autorisant en particulier la taille des descendants à être plus grande que celle de leurs parents. On établit ensuite certains théorèmes limites en utilisant la théorie des processus auto-similaires. Dans le troisième chapitre, on s'intéresse à un problème statistique provenant de l'industrie minière avec l'estimation statistique de la mesure de Lévy du subordinateur classiquement associé à la fragmentation. Plus précisément, on observe les fragments seulement à l'instant où ils atteignent une taille inférieure à un seuil fixé. Enfin, dans un quatrième chapitre on étudie le coût énergétique d'une succession de fragmentations.

Dans de nombreux domaines, décrire l'évolution des phénomènes dans le temps est d'un intérêt capital, en particulier pour aborder les problématiques de la prédiction et de la recherche de facteurs causaux. En épidémiologie, on dispose de données de cohorte qui renseignent sur un groupe de patients suivis dans le temps. Les modèles multi-états de type Markovien proposent un outil intéressant qui permet d'étudier l'évolution d'un patient à travers les différents stades d'une maladie. Dans ce manuscrit, nous rappelons tout d'abord la méthodologie relative au modèle de Markov homogène. Ce modèle est le moins complexe, il suppose que les intensités de transition entre les états sont constantes dans le temps. Dans un second temps, nous étudions un modèle semi-Markovien homogène qui suppose que les intensités de transition dépendent du temps écoulé dans un état de santé. La théorie des processus de comptage est ensuite présentée afin d'introduire des méthodes d'estimations non-paramétriques dans le cadre d'un modèle de Markov non-homogène. Dans ce modèle, les intensités de transition dépendent du temps depuis l'inclusion dans l'étude. Les méthodes d'estimation supposent que le mécanisme de censure n'apporte aucune information sur l'évolution de la maladie. Cette hypothèse étant rarement vérifiée en pratique, nous proposons une méthode d'estimation permettant de prendre en compte une censure informative. Nous présentons également une méthode de programmation visant à faciliter la mise en œuvre des estimateurs basés sur les processus de comptage. Toutes ces méthodes sont appliquées afin d'étudier une base de données de patients asthmatiques. L'objectif est d'aider les cliniciens à mieux comprendre l'évolution de la maladie. Les résultats permettent de mettre en évidence l'impact négatif du surpoids sur l'évolution de l'asthme.

Pour obtenir des listes de mots de fréquences exceptionnelles par rapport à un modèle aléatoire, par exemple dans un contexte de biologie moléculaire, il faut quantifier la qualité de la prédiction des fréquences d'une famille de mots. Nous étudions les probabilités de grandes déviations du processus vectoriel de comptage d'une famille de mots dans des modèles de Markov et des modèles de Markov cachés. Pour démontrer ces résultats, nous établissont un développement du type Edgeworth sur les fonctionnelles additives d'une chaîne de Markov finie. Nous utilisons les théorèmes obtenus pour produire des listes de mots exceptionnels dans les génomes d'Escherichia Coli et de Bacillus Subtilis par conditionnements successifs d'un modèle statistique initial.

On étudie à la fois l'estimation de l'entropie de Shannon d'une probabilité à partir d'observations indépendantes ou markoviennes, et l'estimation du taux d'entropie d'un processus markovien de sauts d'espace d'état fini, à partir d'observations continues ou discrètes. Plusieurs problèmes connexes sont traités. Certains apparaissent en amont de l'estimation, comme l'étude de la géométrie de la divergence de Kullback-Leibler en lien avec la transformation escorte. D'autres apparaissent comme des applications des résultats d'estimation obtenus. On construit ainsi des tests sur le niveau d'entropie d'une probabilité, à partir d'un principe de grandes déviations pour la suite des estimateurs empiriques de l'entropie d'une suite de variables indépendantes. On étudie également diverses propriétés en lien avec l'estimation de l'entropie et du taux d'entropie de files d'attente modélisées par des processus markoviens de naissance et de mort.

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.

Les processus de Markov auto-similaires apparaissent souvent dans diverses parties de la théorie de probabilités comme limites de processus normalisés. La propriété de Markov ajoutée à l'auto-similarité fournit des propriétés très intéressantes comme l'avait remarqué Lamperti. La première partie de cette thèse est consacrée à l'étude de l'enveloppe inférieure et supérieure au moyen de test intégraux et de lois du logarithme itéré pour une classe suffisamment grandes des processus de Markov auto-similaires positifs et quelques processus associés, comme le minimum futur et le processus de Markov auto-similaire positif réflechi en son minimum futur. La seconde partie concernent à l'étude des forêt de Lévy stables conditionnés par leur taille et leur masse. En particulier, un principe d'invariance est établi pour la forêt de Galton-Watson conditionnée par leur taille et leur masse.