Cette thèse s'intéresse à deux modèles de processus auto intéagissant étroitement reliés: le processus de sauts renforcé par sites (VRJP) et la marche aléatoire renforcée par arêtes (ERRW). Nous étudions aussi les liens entre ces processus et un opérateur de Schrödinger aléatoire. Dans le chapitre 3, nous montrons que le VRJP est le seul processus satisfaisant la propriété d'échangeabilité partielle et tel que la probabilité de transition ne dépende que du temps local des voisins, sous quelques conditions techniques. Le chapitre 4 donne la transition de phase entre vitesse positive et vitesse nulle pour un VRJP transitoire sur un arbre de Galton Watson, utilisant le fait que sur un arbre, le VRJP est une marche aléatoire en milieu aléatoire. Dans le chapitre 5, une nouvelle famille exponentielle de loi est introduite et ses liens avec le VRJP sont étudiés. En particulier, nous donnons une preuve de la formule de Coppersmith et Diaconis, n'utilisant que des calculs élémentaires. Finalement, dans le chapitre 6 nous étudions la représentation du VRJP comme mélange de processus de Markov sur les graphes infinis. Nous représentons le VRJP à l'aide de la fonction de Green et d'une fonction propre généralisée d'un opérateur de Schrödinger aléatoire associé au VRJP. En conséquence, nous obtenons un principe d'invariance pour le VRJP quand le renforcement est suffisamment faible, ainsi que la récurrence du ERRW sur ℤ2 pour toute valeurs initiales des paramètres / This thesis is dedicated to the study of two closely related self-interacting processes: the vertex reinforced jump process (VRJP) and the edge reinforced random walk (ERRW). We also study the relations between these processes and a random Schrödinger operator. In Chapter 3, we prove that the VRJP is the only partially exchangeable process whose transition probability depends only on neighbor local times, under some technical conditions. Chapter 4 gives the phase transition between positive speed and null speed of a transient VRJP on a Galton Watson tree, using a representation of random walk in independent random environment. In Chapter 5, we introduce a new exponential family of probability distributions generalizing the Inverse Gaussian distribution, and we show some of its relations to the VRJP. In particular, we give an elementary proof of the formula of Coppersmith and Diaconis. Finally, we show in Chapter 6 that the VRJP on infinite graph is a mixture of Markov jump processes, by constructing the random environment using the Green function and a generalized eigenfunction related to a random Schrödinger operator associated with the VRJP. As a consequence, we obtain a central limit theorem when the reinforcement is weak enough, and also the recurrence of ERRW on ℤ2 for any initial constant weights

Bewegungen von prozessiven molekularen Motoren des Zytoskeletts sind durch ein Wechselspiel von gerichteter Bewegung entlang von Filamenten und Diffusion in der umgebenden Lösung gekennzeichnet. Diese eigentümlichen Bewegungen werden in der vorliegenden Arbeit untersucht, indem sie als Random Walks auf einem Gitter modelliert werden. Ein weiterer Gegenstand der Untersuchung sind Effekte von Wechselwirkungen zwischen den Motoren auf diese Bewegungen. <br /> <br /> Im einzelnen werden vier Transportphänomene untersucht: <br /> (i) Random Walks von einzelnen Motoren in Kompartimenten verschiedener Geometrien, <br /> (ii) stationäre Konzentrationsprofile, die sich in geschlossenen Kompartimenten infolge dieser Bewegungen einstellen,<br /> (iii) randinduzierte Phasenübergänge in offenen röhrenartigen Kompartimenten, die an Motorenreservoirs gekoppelt sind, und <br /> (iv) der Einfluß von kooperativen Effekten bei der Motor-Filament-Bindung auf die Bewegung. Alle diese Phänomene sind experimentell zugänglich, und mögliche experimentelle Realisierungen werden diskutiert. / Movements of processive cytoskeletal motors are characterized by an interplay between directed motion along filament and diffusion in the surrounding solution. In the present work, these peculiar movements are studied by modeling them as random walks on a lattice. An additional subject of our studies is the effect of motor-motor interactions on these movements. <br /> <br /> In detail, four transport phenomena are studied: <br /> (i) Random walks of single motors in compartments of various geometries, <br /> (ii) stationary concentration profiles which build up as a result of these movements in closed compartments, <br /> (iii) boundary-induced phase transitions in open tube-like compartments coupled to reservoirs of motors, and <br /> (iv) the influence of cooperative effects in motor-filament binding on the movements. All these phenomena are experimentally accessible and possible experimental realizations are discussed.

In this thesis, we study the power and limit of algorithms on various models, aiming at applications in distributed networks and databases. In distributed networks, graph algorithms are fundamental to many applications. We focus on computing random walks which are an important primitive employed in a wide range of applications but has always been computed naively. We show that a faster solution exists and subsequently develop faster algorithms by exploiting random walk properties leading to two immediate applications. We also show that this algorithm is optimal. Our technique in proving a lower bound show the first non-trivial connection between communication complexity and lower bounds of distributed graph algorithms. We show that this technique has a wide range of applications by proving new lower bounds of many problems. Some of these lower bounds show that the existing algorithms are tight. In database searching, we think of the database as a large set of multi-dimensional points stored in a disk and want to help the users to quickly find the most desired point. In this thesis, we develop an algorithm that is significantly faster than previous algorithms both theoretically and experimentally. The insight is to solve the problem on the streaming model which helps emphasize the benefits of sequential access over random disk access. We also introduced the randomization technique to the area. The results were complemented with a lower bound. We also initiat a new direction as an attempt to get a better query. We are the first to quantify the output quality using "user satisfaction" which is made possible by borrowing the idea of modeling users by utility functions from game theory and justify our approach through a geometric analysis.

The phenomenon of scale dependent spectral dimension has attracted special interest in the quantum gravity community over the last eight years. It was first observed in computer simulations of the causal dynamical triangulation (CDT) approach to quantum gravity and refers to the reduction of the spectral dimension from 4 at classical scales to 2 at short distances. Thereafter several authors confirmed a similar result from different approaches to quantum gravity. Despite the contribution from different approaches, no analytical model was proposed to explain the numerical results as the continuum limit of CDT. In this thesis we introduce graph ensembles as toy models of CDT and show that both the continuum limit and a scale dependent spectral dimension can be defined rigorously. First we focus on a simple graph ensemble, the random comb. It does not have any dynamics from the gravity point of view, but serves as an instructive toy model to introduce the characteristic scale of the graph, study the continuum limit and define the scale dependent spectral dimension. Having defined the continuum limit, we study the reduction of the spectral dimension on more realistic toy models, the multigraph ensembles, which serve as a radial approximation of CDT. We focus on the (recurrent) multigraph approximation of the two-dimensional CDT whose ensemble measure is analytically controlled. The latter comes from the critical Galton-Watson process conditioned on non-extinction. Next we turn our attention to transient multigraph ensembles, corresponding to higher-dimensional CDT. Firstly we study their fractal properties and secondly calculate the scale dependent spectral dimension and compare it to computer simulations. We comment further on the relation between Horava-Lifshitz gravity, asymptotic safety, multifractional spacetimes and CDT-like models.

Current Question Answering (QA) systems have been significantly advanced in demonstrating finer abilities to answer simple factoid and list questions. Such questions are easier to process as they require small snippets of texts as the answers. However, there is a category of questions that represents a more complex information need, which cannot be satisfied easily by simply extracting a single entity or a single sentence. For example, the question: “How was Japan affected by the earthquake?” suggests that the inquirer is looking for information in the context of a wider perspective. We call these “complex questions” and focus on the task of answering them with the intention to minimize the existing gaps in the literature. The major limitation of the available search and QA systems is that they lack a way of measuring whether a user is satisfied with the information provided. This was our motivation to propose a reinforcement learning formulation to the complex question answering problem. Next, we presented an integer linear programming formulation where sentence compression models were applied for the query-focused multi-document summarization task in order to investigate if sentence compression improves the overall performance. Both compression and summarization were considered as global optimization problems. We also investigated the impact of syntactic and semantic information in a graph-based random walk method for answering complex questions. Decomposing a complex question into a series of simple questions and then reusing the techniques developed for answering simple questions is an effective means of answering complex questions. We proposed a supervised approach for automatically learning good decompositions of complex questions in this work. A complex question often asks about a topic of user’s interest. Therefore, the problem of complex question decomposition closely relates to the problem of topic to question generation. We addressed this challenge and proposed a topic to question generation approach to enhance the scope of our problem domain. / xi, 192 leaves : ill. ; 29 cm

Recent years have seen progress in the analysis of the heat kernel for certain reversible random walks in random environments. In particular the work of Barlow(2004) showed that the heat kernel for the random walk on the infinite component of supercritical bond percolation behaves in a Gaussian fashion. This heat kernel control was then used to prove a quenched functional central limit theorem. Following this work several examples have been analysed with anomalous heat kernel behaviour and, in some cases, anomalous scaling limits. We begin by generalizing the first result - looking for sufficient conditions on the geometry of the environment that ensure standard heat kernel upper bounds hold. We prove that these conditions are satisfied with probability one in the case of the random walk on continuum percolation and use the heat kernel bounds to prove an invariance principle. The random walk on dynamic environment is then considered. It is proven that if the environment evolves ergodically and is, in a certain sense, geometrically d-dimensional then standard on diagonal heat kernel bounds hold. Anomalous lower bounds on the heat kernel are also proven - in particular the random conductance model is shown to be "more anomalous" in the dynamic case than the static. Finally, the reflected random walk amongst random conductances is considered. It is shown in one dimension that under the usual scaling, this walk converges to reflected Brownian motion.

Cette thèse traite l’utilisation des agents mobiles dans le domaine des algo- rithmes distribués en les déplaçant de manière aléatoire dans le réseau. Initialement k agents mobiles ayant les identités uniques sont placés dans le réseau. On décrit un algorithme distribué pour calculer un arbre couvrant dans les réseaux dynamiques en utilisant les agents mobiles. Les agents marquent les noeuds sur les quelles ils arrivent. Ils utilisent deux techniques di?érentes : le clonage dans lequel un agent crée son propre clone pour faire quelques tâches et le marquage sur la tableau de bord (un espace mémoire sur les noeuds). Ces techniques sont utilisés dans les applications comme l’arbre couvrant, le rassemblement et la collecte d’information. Chacun des agents détient une information partielle. Quand deux ou plusieurs agents se rencontrent sur un noeud, ils fusionnent en un seul agent. On s’intéresse alors au temps nécessaire ou tous les k agents fusionnent en un seul et unique agent. On présent une chaîne de Markov pour le comportement des agents, et on montre comment on peut utiliser cette technique pour calculer la bourne supérieur. On étudie le même problème quand les agents mobile commencent la marche aléatoire sous un régime stationnaire. On a aussi étudié le problème de Handshake et on l’a analysé en utilisant les agents mobiles. / This thesis deals with the use of mobile agents in distributed algorithms by performing random walks in the network. k mobile agents having unique identities are placed initially in a network. We describe a distributed algorithm for computing spanning trees in dynamic networks by using mobile agents. The agents mark the nodes on which they arrive. They use two di?erent techniques. In one problem they use the cloning in which an agent creates its own clone to do some task assigned. In the second, the mobile agents mark on the whiteboard (a memory location on the nodes). These techniques are used in applications such as spanning tree, gathering and collecting information. The mobile agents have limited knowledge and hence, they are not intelligent and do not have computational capabilities. When two or more agents meet at a node of the underlying graph, they merge into a single agent. The parameter of interest is the expected time for all the agents to merge into a single agent. We present a Markov chain, modelling the agents behavior, and show how this can be used to upper bound the expected time for all the k agents to merge into a single agent. We study the same problem when the mobile agents start their walk directly under stationary regime. Handshake problem is also studied and analyzed using mobile agents.

Epidemiologists rely on human interaction networks for determining states and dynamics of disease propagations in populations. However, such networks are empirical snapshots of the past. It will greatly benefit if human interaction networks are statistically predicted and dynamically created while an epidemic is in progress. We develop an application framework for the generation of human interaction networks and running epidemiological processes utilizing research on human mobility patterns and agent-based modeling. The interaction networks are dynamically constructed by incorporating different types of Random Walks and human rules of engagements. We explore the characteristics of the created network and compare them with the known theoretical and empirical graphs. The dependencies of epidemic dynamics and their outcomes on patterns and parameters of human motion and motives are encountered and presented through this research. This work specifically describes how the types and parameters of random walks define properties of generated graphs. We show that some configurations of the system of agents in random walk can produce network topologies with properties similar to small-world networks. Our goal is to find sets of mobility patterns that lead to empirical-like networks. The possibility of phase transitions in the graphs due to changes in the parameterization of agent walks is the focus of this research as this knowledge can lead to the possibility of disruptions to disease diffusions in populations. This research shall facilitate work of public health researchers to predict the magnitude of an epidemic and estimate resources required for mitigation.

O estudo de caminhadas aleatórias em meios desordenados e um assunto bastante explorado e pode modelar uma grande variedade de problemas, como por exemplo, problemas de transporte (difusão). O estudo de caminhadas determinísticas em meios desordenados é um assunto pouco explorado. Em uma paisagem composta de N sítios distribuídos aleatoriamente no espaço, um caminhante ("turista") visita estes sítios seguindo a seguinte regra determinística: ir para o sítio vizinho mais próximo que não tenha sido visitado nos últimos passos. De cada sítio inicial, a trajetória obtida com esta dinâmica determinística apresenta inicialmente um tempo de transiente t, onde novos sítios são visitados, e no final um atrator de período p, onde os mesmos sítios são sempre revisitados. Apesar da simplicidade do modelo, a dinâmica e complexa e os resultados não são triviais. Para dimensionalidades d = 2, a distribuição de atratores de período p, obtida numericamente, pode ser descrita por uma lei de potência com um corte exponencial. Os modelos de ligações aleatórias simétricas (que representa o limite de alta dimensionalidade d = 1 do modelo proposto) e assimétricas indicam que o corte exponencial se torna menos importante à medida que N aumenta. O expoente da lei de potência independe da memória tau, sendo portanto uma distribuição robusta. A dinâmica do turista pode ser aplicada a problemas mais abstratos, onde apenas relações de ordem entre vizinhos são dados. O estudo (por amostragem) da estrutura de um dicionário de sinônimos e um exemplo que foi considerado. Mostrou-se que as palavras podem ser embebidas em um espaço Euclidiano de baixa dimensionalidade.Este resultado concorda com um recente estudo exaustivo realizado e questiona o modelo de análise semântica latente. Com a finalidade de entender a transição entre uma caminhada determinística e uma caminhada aleatória, generalizou-se o problema com memória nula designando uma distribuição de probabilidades para o turista visitar os diversos sítios. Esta distribuição e parametrizada por uma variável externa T (temperatura) de modo que para T = 0 têm-se a caminhada do turista como caso limite e para T tendendo para infinito todos os sítios são visitados com igual probabilidade. Resultados analíticos (d = 1) e numéricos mostram a existência de uma região bem delimitada de transição entre os regimes não-ergódico (baixa temperatura) e ergódico (alta temperatura). Uma analogia é estabelecida com o modelo de vidros de Bouchaud. A eficiência da caminhada com relação aos novos sítios visitados, foi estudada e ela e máxima na borda da aleatoriedade, ou seja, ao redor da temperatura de transição. / The study of random walks in disordered media is one well-developed subject and it can model a great variety of problems, for instance, problems of transport (diffusion). The study of deterministic walks in disordered media is a subject not too explored. In a landscape composed of N sites randomly distributed in of, a walker ("tourist") visits these sites following the deterministic rule: going to the nearest site that has not been visited in the last tau steps. From each initial site, the trajectory, obtained with this deterministic dynamics, presents initially a time transient t, where new sites are visited, and, in the end, a p-period attractor, where the same sites are always revisited. In spite of the simplicity of the model, the dynamics is complex and the results are not trivial. For dimensionalities d = 2, the distribution of p-period obtained numerically can be described by a power law with an exponential cut. The models of symmetrical random connections (that represents the limit of high dimensionality d = 1 of the proposed model) and asymmetrical random connections indicate that the exponential cut turns out to be less important as N increases. The exponent law of the power law does not depend on the memory tau, being therefore a robust distribution. The tourist dynamics can be applied to more abstract problems, where just relationships of neighbor order are given. The study (by sampling) of the structure of a dictionary of synonyms has been considered. It has been shown that the words can be embedded in an Euclidean space of low dimensionality. This result agrees with a recent exhaustive study accomplished and it challenges the model of latent semantic analysis. With the purpose of understanding the transition between a deterministic and a random walk a generalization of the problem, with null memory has been performed by designating a distribution of probabilities for the tourist to visit the several sites. This distribution has the external variable T (temperature) as a parameter so that, when T = 0 it has the tourist walk as a limiting case and for T tending to infinity all of the sites are visited ith equal probability. Analytical numerical results (d = 1) show the existence of well delimited transition between non-ergodic (low temperature) and ergodic (high temperature) regime. An analogy is established Bouchaud glass model. The walk efficiency, regarding the new visited sites to trajectory length, has been studied and it is maximum at the edge of stochasticity, in other words, around the temperature of transition.

O estudo de caminhadas aleatórias em meios desordenados e um assunto bastante explorado e pode modelar uma grande variedade de problemas, como por exemplo, problemas de transporte (difusão). O estudo de caminhadas determinísticas em meios desordenados é um assunto pouco explorado. Em uma paisagem composta de N sítios distribuídos aleatoriamente no espaço, um caminhante ("turista") visita estes sítios seguindo a seguinte regra determinística: ir para o sítio vizinho mais próximo que não tenha sido visitado nos últimos passos. De cada sítio inicial, a trajetória obtida com esta dinâmica determinística apresenta inicialmente um tempo de transiente t, onde novos sítios são visitados, e no final um atrator de período p, onde os mesmos sítios são sempre revisitados. Apesar da simplicidade do modelo, a dinâmica e complexa e os resultados não são triviais. Para dimensionalidades d = 2, a distribuição de atratores de período p, obtida numericamente, pode ser descrita por uma lei de potência com um corte exponencial. Os modelos de ligações aleatórias simétricas (que representa o limite de alta dimensionalidade d = 1 do modelo proposto) e assimétricas indicam que o corte exponencial se torna menos importante à medida que N aumenta. O expoente da lei de potência independe da memória tau, sendo portanto uma distribuição robusta. A dinâmica do turista pode ser aplicada a problemas mais abstratos, onde apenas relações de ordem entre vizinhos são dados. O estudo (por amostragem) da estrutura de um dicionário de sinônimos e um exemplo que foi considerado. Mostrou-se que as palavras podem ser embebidas em um espaço Euclidiano de baixa dimensionalidade.Este resultado concorda com um recente estudo exaustivo realizado e questiona o modelo de análise semântica latente. Com a finalidade de entender a transição entre uma caminhada determinística e uma caminhada aleatória, generalizou-se o problema com memória nula designando uma distribuição de probabilidades para o turista visitar os diversos sítios. Esta distribuição e parametrizada por uma variável externa T (temperatura) de modo que para T = 0 têm-se a caminhada do turista como caso limite e para T tendendo para infinito todos os sítios são visitados com igual probabilidade. Resultados analíticos (d = 1) e numéricos mostram a existência de uma região bem delimitada de transição entre os regimes não-ergódico (baixa temperatura) e ergódico (alta temperatura). Uma analogia é estabelecida com o modelo de vidros de Bouchaud. A eficiência da caminhada com relação aos novos sítios visitados, foi estudada e ela e máxima na borda da aleatoriedade, ou seja, ao redor da temperatura de transição. / The study of random walks in disordered media is one well-developed subject and it can model a great variety of problems, for instance, problems of transport (diffusion). The study of deterministic walks in disordered media is a subject not too explored. In a landscape composed of N sites randomly distributed in of, a walker ("tourist") visits these sites following the deterministic rule: going to the nearest site that has not been visited in the last tau steps. From each initial site, the trajectory, obtained with this deterministic dynamics, presents initially a time transient t, where new sites are visited, and, in the end, a p-period attractor, where the same sites are always revisited. In spite of the simplicity of the model, the dynamics is complex and the results are not trivial. For dimensionalities d = 2, the distribution of p-period obtained numerically can be described by a power law with an exponential cut. The models of symmetrical random connections (that represents the limit of high dimensionality d = 1 of the proposed model) and asymmetrical random connections indicate that the exponential cut turns out to be less important as N increases. The exponent law of the power law does not depend on the memory tau, being therefore a robust distribution. The tourist dynamics can be applied to more abstract problems, where just relationships of neighbor order are given. The study (by sampling) of the structure of a dictionary of synonyms has been considered. It has been shown that the words can be embedded in an Euclidean space of low dimensionality. This result agrees with a recent exhaustive study accomplished and it challenges the model of latent semantic analysis. With the purpose of understanding the transition between a deterministic and a random walk a generalization of the problem, with null memory has been performed by designating a distribution of probabilities for the tourist to visit the several sites. This distribution has the external variable T (temperature) as a parameter so that, when T = 0 it has the tourist walk as a limiting case and for T tending to infinity all of the sites are visited ith equal probability. Analytical numerical results (d = 1) show the existence of well delimited transition between non-ergodic (low temperature) and ergodic (high temperature) regime. An analogy is established Bouchaud glass model. The walk efficiency, regarding the new visited sites to trajectory length, has been studied and it is maximum at the edge of stochasticity, in other words, around the temperature of transition.