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.

Univerzita Karlova Pedagogická fakulta Katedra občanské výchovy a filosofie DIPLOMOVÁ PRÁCE Historie a význam vybraných kulturních památek Odoleny Vody a okolí ve vlastivědných vycházkách History and value of chosen cultural sights in Odolena Voda and its surroundings in relation to historical walks Autor práce: Jitka Skýpalová, DiS. Vedoucí práce: Ing. Michaela Dvořáková, Ph.D. Studijní program: Učitelství pro základní školy Studijní obor: I.ST (7503T047) 2017 2 ABSTRACT The goal of this thesis History and value of chosen cultural sights in Odolena Voda and its surroundings in relation to historical walks is to create theoretical and practical foundation for teaching History for the students of the 5th grade, that aligns theoretical and practical education within regional history, represented by cultural monuments. The thesis is dispensed into theoretical and practical part. The theoretical part is firstly concerning the implementation of the topic into Czech national educational curriculum secondly demographic and mainly historical characteristic of the region. The historical part is focusing on Odolena Voda town and Panenske Brezany village. My greatest attention is dedicated to cultural monuments, which are going to be presented to students. This part is followed by practical section consisting of the...

No description available.

Le but de cette thèse est d'établir des résultats énumératifs sur certaines classes de chemins et d'animaux. Ces résultats sont obtenus en appliquant la théorie des empilements de pièces développée par Viennot. Nous étudions les excursions discrètes (ou chemins de Dyck généralisés) de hauteur bornée; nous obtenons des résultats énumératifs qui interprètent combinatoirement et étendent des résultats de Banderier, Flajolet et Bousquet-Mélou. Nous décrivons et énumérons plusieurs classes de chemins auto-évitants, dits chemins faiblement dirigés. Ces chemins sont plus nombreux que les chemins prudents qui forment la classe naturelle la plus grande jusqu'alors. Nous calculons le périmètre de site moyen des animaux dirigés, prouvant des conjectures de Conway et Le Borgne. Enfin, nous obtenons des résultats nouveaux sur l'énumération des animaux de Klarner et les animaux multi-dirigés de Bousquet-Mélou et Rechnitzer. / The goal of this thesis is to prove enumerative results on some classes of lattice walks and animals. These results are applications of the theory of heaps of pieces developed by Viennot. We study discrete excursions (or generalized Dyck paths) with bounded height; we obtain enumerative results that give a combinatorial interpretation and extend results by Banderier, Flajolet and Bousquet-Mélou. We describe and enumerate several classes of self-avoiding walks called weakly directed walks. These classes are larger than the class of prudent walks, the largest natural class enumerated so far. We compute the average site perimeter of directed animals, proving conjectures by Conway and Le Borgne. Finally, we obtain new results on the enumeration of Klarner animals and multi-directed animals defined by Bousquet-Mélou and Rechnitzer.

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.

This work presents a numerical investigation of self-avoiding walks (SAWs) on percolation clusters, a canonical model for polymers in disordered media. A new algorithm has been developed allowing exact enumeration of over ten thousand steps. This is an increase of several orders of magnitude compared to previously existing enumeration methods, which allow for barely more than forty steps. Such an increase is achieved by exploiting the fractal structure of critical percolation clusters: they are hierarchically organized into a tree of loosely connected nested regions in which the walks segments are enumerated separately. After the enumeration process, a region is \"decimated\" and behaves in the following effectively as a single point. Since this method only works efficiently near the percolation threshold, a chain-growth Monte Carlo algorithm has also been used. Main focus of the investigations was the asymptotic scaling behavior of the average end-to-end distance as function of the number of steps on critical clusters in different dimensions. Thanks the highly efficient new method, existing estimates of the scaling exponents could be improved substantially. Also investigated were the number of possible chain conformation and the average entropy, which were found to follow an unusual scaling behavior. For concentrations above the percolation threshold the exponent describing the growth of the end-to-end distance turned out to differ from that on regular lattices, defying the prediction of the accepted theory. Finally, SAWs with short range attractions on percolation clusters are discussed. Here, it emerged that there seems to be no temperature-driven collapse transition as the asymptotic scaling behavior of the end-to-end distance even at zero temperature is the same as for athermal SAWs. / Die vorliegenden Arbeit präsentiert eine numerische Studie von selbstvermeidenden Zufallswegen (SAWs) auf Perkolationsclustern, ein kanonisches Modell für Polymere in stark ungeordneten Medien. Hierfür wurde ein neuer Algorithmus entwickelt, welcher es ermöglicht SAWs von mehr als zehntausend Schritten exakt auszuzählen. Dies bedeutet eine Steigerung von mehreren Größenordnungen gegenüber der zuvor existierenden Methode, welche kaum mehr als vierzig Schritte zulässt. Solch eine Steigerung wird erreicht, indem die fraktale Struktur der Perkolationscluster geziehlt ausgenutzt wird: Die Cluster werden hierarchisch in lose verbundene Gebiete unterteilt, innerhalb welcher Wegstücke separat ausgezählt werden können. Nach dem Auszählen wird ein Gebiet \"dezimiert\" und verhält sich während der Behandlung größerer Gebiete effektiv wie ein Gitterpunkt. Da diese neue Methode nur nahe der Perkolationsschwelle funktioniert, wurde zum Erzielen der Ergebnisse zudem ein Kettenwachstums-Monte-Carlo-Algorithmus (PERM) eingesetzt. Untersucht wurde zunächst das asymptotische Skalenverhalten des Abstands der beiden Kettenenden als Funktion der Schrittzahl auf kritischen Clustern in verschiedenen Dimensionen. Dank der neuen hochperformanten Methode konnten die bisherigen Schätzer für den dies beschreibenden Exponenten signifikant verbessert werden. Neben dem Abstand wurde zudem die Anzahl der möglichen Konformationen und die mittlere Entropie angeschaut, für welche ein ungewöhnliches Skalenverhalten gefunden wurde. Für Konzentrationen oberhalb der Perkolationsschwelle wurde festgestellt, dass der Exponent, welcher das Wachstum des Endabstands beschreibt, nicht dem für freie SAWs entspricht, was nach gängiger Lehrmeinung der Fall sein sollte. Schlussendlich wurden SAWs mit Anziehung zwischen benachbarten Monomeren untersucht. Hier zeigte sich, dass es auf kritischen Perkolationsclustern keinen Phasenübergang zu geben scheint, an welchem die Ketten kollabieren, sondern dass das Skalenverhalten des Endabstands selbst am absoluten Nullpunkt der Temperatur unverändert ist.

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.