The work in this thesis can be divided into two different parts. In the first part, we suggest an approximate edge 3-coloring polynomial time algorithm for cubic graphs. For any cubic graph with n vertices, using this coloring algorithm, we get an edge 3-coloring with at most n/3 error vertices. In the second part, we study Jim Propp's Rotor-Router model on some non-bipartite graph. We find the difference between the number of chips at vertices after performing a walk on this graph using Propp model and the expected number of chips after a random walk. It is known that for line of integers and d-dimenional grid, this deviation is constant. However, it is also proved that for k-ary infinite trees, for some initial configuration the deviation is no longer a constant and say it is D. We present a similar study on some non-bipartite graph constructed from k-ary infinite trees and conclude that for this graph with the same initial configuration, the deviation is almost (k²)D.

In this thesis we develop and use a continuum random walk framework to solve problems that are usually studied using a discrete random walk on a discrete lattice. Problems studied include; the time it takes for a random walker to be absorbed at a trap on a fractal lattice, the calculation of the spectral dimension for several different classes of networks, the calculation of the density of states for a multi-layered Bethe lattice and the relationship between diffusion exponents and a resistivity exponent that occur in relevant power laws. The majority of the results are obtained by deriving an expression for a Laplace transformed Green’s function or first passage time, and then using Tauberian theorems to find the relevant asymptotic behaviour. The continuum framework is established by studying the diffusion equation on a 1-d bar with non-homogeneous boundary conditions. The result is extended to model diffusion on networks through linear algebra. We derive the transformation linking the Green’s functions and first passage time results in the continuum and discrete settings. The continuum method is used in conjunction with renormalization techniques to calculate the time taken for a random walker to be absorbed at a trap on a fractal lattice and also to find the spectral dimension of new classes of networks. Although these networks can be embedded in the d- dimensional Euclidean plane, they do not have a spectral dimension equal to twice the ratio of the fractal dimension and the random walk dimension when the random walk on the network is transient. The networks therefore violate the Alexander-Orbach law. The fractal Einstein relationship (a relationship relating a diffusion exponent to a resistivity exponent) also does not hold on these networks. Through a suitable scaling argument, we derive a generalised fractal Einstein relationship which holds for our lattices and explains anomalous results concerning transport on diffusion limited aggregates and Eden trees.

We establish a strong connection between buildings and Hecke algebras through the study of two algebras of averaging operators on buildings. To each locally finite regular building we associate a natural algebra B of chamber set averaging operators, and when the building is affine we also define an algebra A of vertex set averaging operators. In the affine case, it is shown how the building gives rise to a combinatorial and geometric description of the Macdonald spherical functions, and of the centers of affine Hecke algebras. The algebra homomorphisms from A into the complex numbers are studied, and some associated spherical harmonic analysis is conducted. This generalises known results concerning spherical functions on groups of p-adic type. As an application of this spherical harmonic analysis we prove a local limit theorem for radial random walks on affine buildings.

Neste trabalho, estudamos o passeio aleatório do elefante introduzido em (SCHUTZ; TRIMPER, 2004). Um processo estocástico não Markoviano com memória de alcance ilimitada que apresenta transição de fase. Nosso objetivo é demonstrar a convergência quase certa do passeio aleatório do elefante nos casos subcrítico e crítico. Além destes resultado, também apresentamos a demonstração do Teorema Central do Limite para ambos os regimes. Para o caso supercrítico, vamos demonstrar a convergência do passeio aleatório do elefante para uma variável aleatória não normal com base nos artigos (BAUR; BERTOIN, 2016), (BERCU, 2018) e (COLETTI; GAVA; SCHUTZ, 2017b). / In this work we study the elephant random walk introduced in (SCHUTZ; TRIMPER, 2004), a discrete time, non-Markovian stochastic process with unlimited range memory that presents phase transition. Our objective is to proof the almost sure convergence for the subcritical and critical regimes of the model. We also present a demonstration of the Central Limit Theorem for both regimes. For the supercritical regime we proof the convergence of the elephant random walk to a non-normal random variable based on the articles (BAUR; BERTOIN, 2016), (BERCU, 2018) and (COLETTI; GAVA; SCHUTZ, 2017b).

L’objet de cette thèse est d’étudier la probabilité de survie d’un processus de branchement en environnement aléatoire markovien et d’étendre dans ce cadre les résultats connus en milieu aléatoire i.i.d.. le cœur de l’étude repose sur l’utilisation des théorèmes limites locaux pour une marche aléatoire centrée (Sn)n≥0 sur R à pas markoviens et pour (rnn)n≥0, où mn = min (0, S1,... , Sn). Pour traiter le cas d’un environnement aléatoire markovien, nous développons dans un premier temps une étude des théorèmes locaux pour une chaîne semi-markovienne à valeurs réelles en améliorant certains résultats déjà connus et développés initialement par E. L. Presman (voir aussi [21]). Nous utilisons ensuite ces résultats pour l’étude du comportement asymptotique de la probabilité de survie d’un processus de branchement critique en environnement aléatoire markovien. Les résultats principaux de cette thèse (théorème limite local et son application au processus de branchement critique eu milieu aléatoire) ont été acceptés et publiés dans le Comptes Rendus de l‘Académie des Sciences ([20]). Le texte principal de cette mémoire de thèse consisite les détails des preuves. / The purpose of this thesis is to study the survival probability of a branching process in markovian random environment and expand in this framework some known results which have been developed for a branching processus in i.i.d. random environment, the core of the study is based on the use of the local limit theorem for a centered random walk (Sn)n≥o on R with markovian increasements and for (mn)n≥0. where mn = min (O. S1,……. , Sn). In order to treat the case of a markovian random environment, we establish firstly a local limit theorem for a semi-markovian chain on R. which improves certain results developed initially by E. P. Presman (see also [21]). And then we use these results to study the asymptotic behavior of a critical branching process in markovian environment. The main results et this thesis (local limit theorem and its application to the critical branching process in random environment) are accepted and published in Comptes Rendus de l’Académie des Sciences ([20]). The principal text et this thesis contains the details of the proofs.

O passeio aleatório quântico foi totalmente entendido por [3] e desde então muitos esforços foram feitos para compreender casos mais gerais como no passeio aleatório tradicional. Nós introduzimos o caso periódico e discutimos a heurística sendo considerada como uma partícula quântica difundindo em um cristal atômico linear. Assim, estendemos o teorema de Grimmett-Janson- Scudo [3] para este caso que é um método para obter a densidade de probabilidade limite do operador posição dependendo da diagonalização da matriz de evolução unitária e mostramos que o caso periódico é de fato balístico, [9]. Como um exemplo, édiscutida a densidade probabilidade limite de período dois. / The homogeneous quantum random walk was completely understood by [3] and since then many efforts were made to compreehend more general cases like in the tradicional random walk. We introduce the periodic case and discuss a heuristic to be considered as a quantum particle diffusion in a atomic linear crystal. Thus, we extend the theorem of Grimmett-Janson-Scudo [3] to this case which is a method to obtain the limit of the probability density of the position operator depending on the diagonalization of the unitary evolution matrix and show that the periodic case is in fact ballistic, [9]. As an example, it is shown the limit probability density of the period two.

This diploma thesis analyses the market efficiency hypothesis of chosen currency pairs EUR/USD, EUR/CZK and USD/CZK. The aim of this study is to describe the price behaviour of chosen financial assets and verify the random walk hypothesis on the foreign exchange market. Model of random walk says there is no relationship between historical and future prices, so price changes are random and cannot be predicted. Random walk hypothesis was tested by chosen statistic tests runs test, test of auto-correlation, variance ratio test and unit root test (Augmented Dickey-Fuller Test). Data were collected through the online trading platform and tested in EViews. Period of testing for daily changes (D1) was chosen from 31.12.2009 to 29.12.2017 and for weekly changes (T1) from 2.1.2005 to 29.12.2017. This thesis proved weak-form efficiency of EUR/USD and USD/CZK for both daily changes and weekly changes in a chosen period. Inefficient behaviour of daily changes of EUR/CZK (D1) was indicated by runs test, test of autocorrelation and variance ratio test. There is a question what the cause of inefficiency is. The most likely explanation is currency intervention of the Czech National Bank which took place from April 2013 to April 2017 in order to achieve the inflation target and prevent deflation. Traders could also achieve profits by speculating on appreciation of Czech Crown below 27,-crowns/euro which is not in harmony with efficient-market hypothesis. Moreover, currency pair EUR/CZK is not liquid as major currency pairs and there are bigger transaction costs because of bid-offer spread. This work can contribute to next research in connection with results of this study. To verify if the cause of inefficient behaviour of daily price changes of EUR/USD are currency interventions of the Czech National Bank, I would suggest testing efficient-market hypothesis exactly at the time of interventions. It would be also suitable to compare results of different methodologies including testing in short-time intervals of price changes.

abstract: Overhead high voltage transmission lines are widely used around the world to deliver power to customers because of their low losses and high transmission capability. Well-coordinated insulation systems are capable of withstanding lightning and switching surge voltages. However, flashover is a serious issue to insulation systems, especially if the insulator is covered by a pollution layer. Many experiments in the laboratory have been conducted to investigate this issue. Since most experiments are time-consuming and costly, good mathematical models could contribute to predicting the insulator flashover performance as well as guide the experiments. This dissertation proposes a new statistical model to calculate the flashover probability of insulators under different supply voltages and contamination levels. An insulator model with water particles in the air is simulated to analyze the effects of rain and mist on flashover performance in reality. Additionally, insulator radius and number of sheds affect insulator surface resistivity and leakage distance. These two factors are studied to improve the efficiency of insulator design. This dissertation also discusses the impact of insulator surface hydrophobicity on flashover voltage. Because arc propagation is a stochastic process, an arc could travel on different paths based on the electric field distribution. Some arc paths jump between insulator sheds instead of travelling along the insulator surfaces. The arc jumping could shorten the leakage distance and intensify the electric field. Therefore, the probabilities of arc jumping at different locations of sheds are also calculated in this dissertation. The new simulation model is based on numerical electric field calculation and random walk theory. The electric field is calculated by the variable-grid finite difference method. The random walk theory from the Monte Carlo Method is utilized to describe the random propagation process of arc growth. This model will permit insulator engineers to design the reasonable geometry of insulators, to reduce the flashover phenomena under a wide range of operating conditions. / Dissertation/Thesis / Doctoral Dissertation Engineering 2016

A wireless sensor network (WSN) is made of tiny sensor nodes usually deployed in high density within a targeted area to monitor a phenomenon of interest such as temperature, vibration or humidity. The WSNs can be employed in various applications (e.g., Structural monitoring, agriculture, environment monitoring, machine health monitoring, military, and health). For each application area there are different technical issues and remedies. Various challenges need to be considered while setting up a WSN, including limited computing, memory and energy resources, wireless channel errors and network scalability. One way of addressing these problems is by implementing a routing protocol that efficiently uses these limited resources and hence reduces errors, improves scalability and increases the network lifetime. The topology of any network is important and wireless sensor networks (WSNs) are no exception. In order to effectively model an energy-efficient routing algorithm, the topology of the WSN must be factored in. However, little work has been done on routing for WSNs with regular patterned topologies, except for the shortest path first (SPF) routing algorithms. The issue with the SPF algorithm is that it requires global location information of the nodes from the sensor network, which proves to be a drain on the network resources. In this thesis a novel algorithm namely, BRALB (Biased Random Algorithm for Load Balancing) is proposed to overcome the issues faced in routing data within WSNs with regular topologies such as square-base topology and triangle-based topology. It is based on random walk and probability. The proposed algorithm uses probability theory to build a repository of information containing the estimate of energy resources in each node, in order to route packets based on the energy resources in each node and thus does not require any global information from the network. It is shown in this thesis by statistical analysis and simulations that BRALB uses the same energy as the shortest path first routing as long as the data packets are comparable in size to the inquiry packets used between neighbours. It is also shown to balance the load (i.e. the packets to be sent) efficiently among the nodes in the network. In most of the WSN applications the messages sent to the base station are very small in size. Therefore BRALB is viable and can be used in sensor networks employed in such applications. However, one of the constraints of BRALB is that it is not very scalable; this is a genuine concern as most WSNs deployment is large scale. In order to remedy this problem, C-BRALB (Clustered Biased Random Algorithm for Load Balancing) has been proposed as an extension of BRALB with clustering mechanism. The same clustering technique used in Improved Directed Diffusion (IDD) has been adopted for C-BRALB. The routing mechanism in C-BRALB is based on energy biased random walk. This algorithm also does not require any global information apart from the initial flooding initiated by the sink to create the clusters. It uses probability theory to acquire all the information it needs to route packets based on energy resources in each cluster head node. It is shown in this thesis by using both simulations and statistical analysis that C-BRALB is an efficient routing algorithm in applications where the message to be sent is comparable to the inquiry message among the neighbours. It is also shown to balance the load (i.e. the packets to be sent) among the neighbouring cluster head nodes.

O passeio aleatório quântico foi totalmente entendido por [3] e desde então muitos esforços foram feitos para compreender casos mais gerais como no passeio aleatório tradicional. Nós introduzimos o caso periódico e discutimos a heurística sendo considerada como uma partícula quântica difundindo em um cristal atômico linear. Assim, estendemos o teorema de Grimmett-Janson- Scudo [3] para este caso que é um método para obter a densidade de probabilidade limite do operador posição dependendo da diagonalização da matriz de evolução unitária e mostramos que o caso periódico é de fato balístico, [9]. Como um exemplo, édiscutida a densidade probabilidade limite de período dois. / The homogeneous quantum random walk was completely understood by [3] and since then many efforts were made to compreehend more general cases like in the tradicional random walk. We introduce the periodic case and discuss a heuristic to be considered as a quantum particle diffusion in a atomic linear crystal. Thus, we extend the theorem of Grimmett-Janson-Scudo [3] to this case which is a method to obtain the limit of the probability density of the position operator depending on the diagonalization of the unitary evolution matrix and show that the periodic case is in fact ballistic, [9]. As an example, it is shown the limit probability density of the period two.