Thesis (Ph. D.)--University of Missouri-Columbia, 2002. / Typescript. Vita. Includes bibliographical references (leaves 79-81). Also available on the Internet.

L’Internet a complètement révolutionné la façon dont nous communiquons. En parallèle, la croissance importante des réseaux mobiles s'est accompagnée d'une explosion du nombre d’usagers et d'une augmentation exponentielle de la demande. Cependant, l’Internet n'est pas encore, voire n'est pas toujours, universellement accessible. Par exemple, c'est le cas en ce qui concerne l’accès dans les économies émergentes ou dans les régions éloignées, les obstacles physiques empêchant le déploiement de réseaux mobiles et les désastres naturels. C'est dans ce contexte que les réseaux tolérants au délai ont été introduits pour faire face aux environnements caractérisés par des interruptions et des délais de transmission élevés. Ces réseaux, manquent souvent de routes pré-déterminées ou même de toute infrastructure pour permettre une communication de bout-en-bout. Dans ce contexte, tous les nœuds de ces réseaux peuvent interagir en utilisant leurs contacts comme une opportunité de communication. Le paradigme stockage/transport permet à ces nœuds d’exploiter des chemins spatio-temporels créés par ces possibilités de contact afin de livrer des messages au fil du temps. Dans ce travail, nous soulevons ici une question générique : pouvons-nous concevoir une infrastructure mobile et opportuniste qui pourrait aider à transmettre ces messages ? Afin de fournir une telle infrastructure, nous étudions l’application des marches aléatoires temporelles (TRWs) dans réseaux opportunistes. Nous explorons l’application et l’impact de la TRW pour fournir une infrastructure minimale et non-invasive à partir de deux points de vue : le stockage des données et leur transmission. / The Internet has entirely reshaped the way we communicate and interact with one another. The rapid development of the wireless infrastructure by network providers has being accompanied by an exponential growth in the number of mobile users. However, global Internet access and connectivity still face several challenges: scarce or poor quality connectivity in developing countries or places with limited accessibility, physical obstacles limiting the deployment of wireless networks and natural or man-made disasters. Delay tolerant networks (DTNs) were introduced to deal with environments where interruptions or disruptions of service were expected. Such networks usually lack of end-to-end paths or any infrastructure to help communications. In these networks, mobile nodes may interact using their contacts as a communication opportunity. The store-carry-forward paradigm allows nodes to exploit spatio-temporal paths created by contact opportunities in order to deliver messages over time. Instead we raise the question: can we design a mobile and opportunistic infrastructure that could help deliver messages? In the quest to provide such infrastructure, we study the application of temporal random walks (TRW) over the opportunistic networks. We explore the application and impact of TRW as a minimal and non invasive infrastructure from two points of view: data forwarding and data recollection/transmission.

A computação quântica é um modelo computacional baseado nas leis da mecânica quântica, que pode ser utilizado para desenvolver algoritmos mais eficientes que seus correspondentes clássicos. O desenvolvimento de algoritmos quânticos eficientes, no entanto, é uma tarefa altamente desafiadora. Uma abordagem recente que vem se mostrando bem-sucedida é a utilização de caminhadas quânticas. Neste trabalho, estudamos a caminhada quântica no hipercubo, calculando analiticamente sua distribuição estacionária e analisando propriedades de seu mixing time, tanto na situação ideal como na situação com descoerência gerada por ligações interrompidas. Também estudamos a caminhada na malha bidimensional, calculando sua distribuição estacionária analiticamente e explorando a relação entre o mixing time e a complexidade do algoritmo de busca nesse grafo. Desenvolvemos uma ferramenta computacional para simulação numérica de caminhadas quânticas em malhas uni- e bidimensionais com diversas condições de contorno. Finalmente, estudamos alguns algoritmos de busca em grafos e analisamos numericamente o impacto que a descoerência exerce sobre seus desempenhos. / Quantum computing is a model of computation based on the laws of quantum mechanics, which can be used to develop faster algorithms. The development of efficient quantum algorithms, however, is a highly challenging task. A recent successful approach is the use of quantum walks. In this work, we have studied the quantum walk on the hypercube, obtaining the exact stationary distribution and analyzing properties of its mixing time both in the ideal and in the noisy set-ups, with noise generated by broken links. We have also studied the walk in a two-dimensional grid, where we have obtained its stationary distribution analytically and have explored the relation between mixing time and the complexity of the search algorithm for this graph. We have developed a computational tool for numerical simulation of quantum walks in one- and two-dimensional grids with several boundary conditions. Finally, we have studied some algorithms for search on graphs and have numerically analyzed the impact of decoherence over their performances.

Orientadores: Christophe Frédéric Gallesco, Serguei Popov / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matemática, Estatística e Computação Científica / Made available in DSpace on 2018-08-22T17:31:03Z (GMT). No. of bitstreams: 1 VasquezMercedes_ClaudiaEdith_M.pdf: 743991 bytes, checksum: 587d04d1b7b45c75dd5eeea766258b02 (MD5) Previous issue date: 2013 / Resumo: O resumo poderá ser visualizado no texto completo da tese digital / Abstract: The abstract is available with the full electronic document / Mestrado / Estatistica / Mestra em Estatística

In this thesis, we investigate examples of random walks on free products of cyclic groups. Free products are groups that contain words constructed by concatenation with possible simplifications[20]. Mairesse in [17] proved that the harmonic measure on the boundary of these random walks has a Markovian Multiplicative structure (this is a class of Markov measures which requires fewer parameters than the usual Markov measures for its description ), and also showed how in the case of the harmonic measure these parameters can be found from Traffic Equations. Then Mairesse and Math ́eus in [20] continued investigation of these random walks and the associated Traffic Equations. They introduced the Stationary Traffic Equations for the situation when the measure is shift-invariant in addition to being μ-invariant. In this thesis, we review these developments as well as explicitly describe several concrete examples of random walks on free products, some of which are new.

Le sujet principal de ce mémoire est le comportement asymptotique de la géométrie et topologie des variétés localement symétriques Gamma\ X quand le volume tend vers l’infini. Notre premier résultat porte sur la convergence Benjamini-Schramm des 2 ou 3-variétés hyperboliques arithmétiques. Une suite d'espaces localement symétriques (Gamma_n\ X) converge Benjamini-Schramm vers l'espace symétrique X si pour chaque R>0 la limite de \Vol((\Gamma\X)_{<R})/Vol(\Gamma\bs X). On montre qu'il existe une constante réelle C=C_R satisfaisant la propriété suivante: pour chaque réseau arithmétique de congruence Gamma de \PGL(2,R) ou PGL(2,C) sans torsion on a Vol ((Gamma\ X)_{<R})<= C_R \ Vol (Gamma\ X)^0.986. Il n'y a qu'un nombre fini de réseaux arithmétiques de covolume borné par une constante donc ce résultat implique la convergence Benjamini-Schramm pour des variétés arithmétiques de congruence. On donne aussi une version de (\ref{AbsFr1}) un peu plus faible qui reste vraie pour des réseaux arithmétiques qui ne sont pas de congruence. Les majorations de volume de la partie $R$-mince sont déduites d'une version forte de la propriété de la multiplicité limite satisfaite par les réseaux arithmétiques de PGL(2,R) et PGL(2,C). En utilisant nos résultats on confirme la conjecture de Gelander pour des 3-variétés arithmétiques hyperboliques: pour chaque telle variété M on construit un complexe simplicial N homotope à M dont le nombre des simplexes est O(Vol(M)) et le degré des nœuds est uniformément borné par une constante absolue. Dans la deuxième partie on s'intéresse aux espaces localement symétriques Gamma\X où X est de rang supérieur ou égal à 2. Notre résultat principal affirme que la dimension du premier groupe d'homologie à coefficients dans F_2 (corps avec 2 éléments) est sous-linéaire en le volume. Ce résultat est à comparer avec des travaux de Calegari et Emerton sur la cohomologie mod-p dans les tours p-adiques des 3-variétés et les résultats d'Abert, Gelander et Nikolov sur le rang des sous-groupes d'un réseau de rang supérieur à angles droits. Le point fort de notre approche est qu'il n'y a pas besoin de travailler dans une seule classe de commensurabilité. La troisième partie est indépendante des deux premières. Elle porte sur une extension du théorème de Kesten. Le théorème de Kesten affirme que si Gamma est un groupe engendré par un ensemble fini symétrique S, N est un sous-groupe normal de Gamma alors N est moyennable si et seulement si les rayons spectraux du graphe de Cayley Cay(Gamma,S) et du graphe de Scheier Sch(Gamma/N,S) coïncident. En utilisant les techniques de Abert, Glasner et Virag on généralise le theorème de Kesten aux N-uniformément récurrents. / The main theme of this work is the study of geometry and topology of locally symmetric spaces Gamma\ X as ther volume Vol(\Gamma\ X) tends to infinity. Our first main result concerns the Benjamini-Schramm convergence for arithmetic hyperbolic 2 or 3-manifolds. A sequence of locally symmetric spaces (Gamma_n\ X) converges Benjamini-Schramm to X if and only if for every radius R>0 the limit Vol((Gamma\ X)_{<R}/Vol (Gamma\ X) as n goes to infinity is 0, where (\Gamma\X)_{<R} stands for the R-thin part of Gamma\ X. We prove that there exists a positive constant C=C_R with the following property: for every torsion free, uniform, congruence arithmetic lattice Gamma in PGL(2,R) or PGL(2,C) Vol ((Gamma\ X)_{<R})<= C Vol (Gamma\X))^0.986. There is only finitely many arithmetic lattices of covolume bounded by a constant so the result above implies the Benjamini-Schramm convergence for any sequence of congruence arithmetic hyperbolic 3-manifolds. We also prove a similar but slightly weaker inequality for non-congruence subgroups. Our results are deduced form a strong form of the limit multiplicity property that holds for arithmetic lattices in PGL(2,R) of PGL(2,C). As an application of our bounds we confirm Gelander's conjecture on the triangulations of arithmetic hyperbolic 3-manifolds: we show that every arithmetic hyperbolic 3-manifold M admits a triangulation with O(Vol(M)) simplices and degrees of vertices bounded uniformly by an absolute constant. Next, we move to the setting of higher rank locally symmetric spaces. Let M_n=Gamma_n\ X be a sequence of pairwise distinct locally symmetric spaces modeled after a higher rank symmetric space X. We show that the dimension of the first homology group with coefficients in F_2 is sublinear in volume. This can be compared with the results of Calegari and Emerton on mod-p homology growth in p-adic analytic towers of 3-manifolds as well as the results of Abert, Gelander and Nikolov on the rank gradient of right-angled lattices in higher rank Lie groups.The main strength of our theorem is that we do not need to assume that the manifolds in question are commensurable. Our third result is independent of the first two. Kesten theorem asserts that if Gamma is group generated by a finite symmetric set S and N is a normal subgroup of Gamma then N is amenable if and only if the spectral radii of the Cayley graphs Cay(Gamma, S) and the Schreier graph Sch(Gamma/N,S) are equal. Building on the work of Abert, Glasner and Virag we extend Kesten's theorem to uniformly recurrent subgroups.

In Chapter 1 the classical secretary problem is introduced. Chapters 2 and 3 are variations of this problem. Chapter 2, discusses the problem of maximizing the probability of stopping with one of the two highest values in a Bernoulli random walk with arbitrary parameter p and finite time horizon n. The optimal strategy (continue or stop) depends on a sequence of threshold values (critical probabilities) which has an oscillating pattern. Several properties of this sequence have been proved by Dr. Allaart. Further properties have been recently proved. In Chapter 3, a gambler will observe a finite sequence of continuous random variables. After he observes a value he must decide to stop or continue taking observations. He can play two different games A) Win at the maximum or B) Win within a proportion of the maximum. In the first section the sequence to be observed is independent. It is shown that for each n>1, theoptimal win probability in game A is bounded below by (1-1/n)^{n-1}. It is accomplished by reducing the problem to that of choosing the maximum of a special sequence of two-valued random variables and applying the sum-the-odds theorem of Bruss (2000). Secondly, it is assumed the sequence is i.i.d. The best lower bounds are provided for the winning probabilities in game B given any continuous distribution. These bounds are the optimal win probabilities of a game A which was examined by Gilbert and Mosteller (1966).

La prévision d'événements extrêmes est une question cruciale dans des domaines divers allant de la météorologie à la finance. Trois classes d'universalité (Gumbel, Fréchet et Weibull) ont été identifiées pour des variables aléatoires indépendantes et de distribution identique (i.i.d.).La modélisation par des variables aléatoires i.i.d., notamment avec le modèle d'énergie aléatoire de Derrida, a permis d'améliorer la compréhension des systèmes désordonnés. Cette hypothèse n'est toutefois pas valide pour de nombreux systèmes physiques qui présentent de fortes corrélations. Dans cette thèse, nous étudions trois modèles physiques de variables aléatoires fortement corrélées : des fermions piégés,des matrices aléatoires et des marches aléatoires. Dans la première partie, nous montrons plusieurs correspondances exactes entre l'état fondamental d'un gaz de Fermi piégé et des ensembles de matrices aléatoires. Le gaz Fermi est inhomogène dans le potentiel de piégeage et sa densité présente un bord fini au-delà duquel elle devient essentiellement nulle. Nous développons une description précise des statistiques spatiales à proximité de ce bord, qui va au-delà des approximations semi-classiques standards (telle que l'approximation de la densité locale). Nous appliquons ces résultats afin de calculer les statistiques de la position du fermion le plus éloigné du centre du piège, le nombre de fermions dans un domaine donné (statistiques de comptage) et l'entropie d'intrication correspondante. Notre analyse fournit également des solutions à des problèmes ouverts de valeurs extrêmes dans la théorie des matrices aléatoires. Nous obtenons par exemple une description complète des fluctuations de la plus grande valeur propre de l'ensemble complexe de Ginibre.Dans la deuxième partie de la thèse, nous étudions les questions de valeurs extrêmes pour des marches aléatoires. Nous considérons les statistiques d'écarts entre positions maximales consécutives (gaps), ce qui nécessite de prendre en compte explicitement le caractère discret du processus. Cette question ne peut être résolue en utilisant la convergence du processus avec son pendant continu, le mouvement Brownien. Nous obtenons des résultats analytiques explicites pour ces statistiques de gaps lorsque la distribution de sauts est donnée par la loi de Laplace et réalisons des simulations numériques suggérant l'universalité de ces résultats. / Predicting the occurrence of extreme events is a crucial issue in many contexts, ranging from meteorology to finance. For independent and identically distributed (i.i.d.) random variables, three universality classes were identified (Gumbel, Fréchet and Weibull) for the distribution of the maximum. While modelling disordered systems by i.i.d. random variables has been successful with Derrida's random energy model, this hypothesis fail for many physical systems which display strong correlations. In this thesis, we study three physically relevant models of strongly correlated random variables: trapped fermions, random matrices and random walks.In the first part, we show several exact mappings between the ground state of a trapped Fermi gas and ensembles of random matrix theory. The Fermi gas is inhomogeneous in the trapping potential and in particular there is a finite edge beyond which its density vanishes. Going beyond standard semi-classical techniques (such as local density approximation), we develop a precise description of the spatial statistics close to the edge. This description holds for a large universality class of hard edge potentials. We apply these results to compute the statistics of the position of the fermion the farthest away from the centre of the trap, the number of fermions in a given domain (full counting statistics) and the related bipartite entanglement entropy. Our analysis also provides solutions to open problems of extreme value statistics in random matrix theory. We obtain for instance a complete description of the fluctuations of the largest eigenvalue in the complex Ginibre ensemble.In the second part of the thesis, we study extreme value questions for random walks. We consider the gap statistics, which requires to take explicitly into account the discreteness of the process. This question cannot be solved using the convergence of the process to its continuous counterpart, the Brownian motion. We obtain explicit analytical results for the gap statistics of the walk with a Laplace distribution of jumps and provide numerical evidence suggesting the universality of these results.

In this thesis, I study fluctuations and rare events of time-additive observables of discrete-time Markov chains on finite state spaces. The observable of interest is the mean node connectivity visited by a random walk running on instances of an Erdős-Rényi (ER) random graph. I implement and analyze the Adaptive Power Method (APM) which converges to the driven process, a biased random walk defined through a control parameter that simulates trajectories corresponding to rare events of the observable in the original dynamics. The APM demonstrates good convergence and accurately produces the desired quantities from a single trajectory. Due to the bulk-dangling-chain structure in the ER graph, the driven process seems to undergo a dynamical phase transition (DPT) for infinitely large graphs, meaning the behavior of the trajectories changes abruptly as the control parameter is varied. Observations show that the random walk visits two distinct phases, being de-localized in the bulk or localized in the chain. Through two simpler models capturing the bulk-dangling-chain property of the ER graph I study how the DPT occurs as the graph size increases. I observe that the trajectories of the driven process near the transition show intermittent behavior between the two phases. The diverging time scale of the DPT is found to be the average time that the random walk spends in a phase before it transitions to the other one. On the ER graph the trajectories are also intermittent but the form of the time scaling remains open due to computational limits on the graph size.

No description available.