This thesis is about graph-indexed random walks, Lipschitz mappings and graph homo- morphisms. It discusses connections between these notions, surveys the existing results, and shows new results. Graph homomorphism is an adjacency-preserving mapping between two graphs. Our main objects of study are graph homomorphisms to an infinite path. We are interested in two parameters: maximum range and average range. The average range of a graph is the expected size of the image of a uniformly picked random homomorphism to an infinite path. We obtain formulas for several graph classes and investigate main conjectures on this parameter. For maximum range parameter we show a general formula and an algorithm to compute it for general graphs. Besides that, we study the problem of extending a prescribed partial graph homomorphism to a full graph homomorphism. We show that this problem is polynomial in some cases. 1

This study investigates the independence assumption of the theory of random walks in stock market prices through the simulation of the moving average strategy. In the process of doing so, three related questions are examined: (1) Does the past relative volatility of a stock furnish a useful indication of its future behavior? (2) Is the performance of the decision rule improved by applying it to those securities which are likely to be highly volatile? (3) Does positive dependence in successive monthly price changes exist? The purpose of Test No. 1 was to gauge the tendency for a stock's relative volatility to remain constant over two adjacent intervals of time. As measured by the coefficient of variation, the volatility of each of the 200 securities was computed over the 1936 to 1945 and 1946 to 1955 decades. In order to evaluate the strength of the relationship between these paired observations, a rank correlation analysis was performed. The results indicated a substantial difference in relative volatility for each security over the two ten-year periods. In Test No. 2 a different experimental design was employed to determine whether the relative volatility of a stock tended to remain within a definite range over time. According to their volatility in the 1936 to 1945 period, the 200 securities were divided into ten groups. Portfolio No. 1 contained the twenty most volatile securities while Portfolio No. 2 consisted of the next twenty most volatile, etc. An average coefficient of variation was calculated for each group over the periods, 1936 to 1945 and 1946 to 1955. The rank correlation analysis on these ten paired observations revealed that the most volatile securities, as a group, tended to remain the most volatile. Test No. 3 consisted of the application of the moving average strategy (for long positions only) to forty series of month-end prices covering the interval, 1956 to 1966. These securities had demonstrated a high relative volatility over the previous decade and, on the basis of the findings reported in Test No. 2, it was forecasted that they would be the most volatile of the sample of 200 in the period under investigation. Four different moving averages ranging from three to six months, and thirteen different thresholds ranging from 2 to 50 per cent were simulated. The results of the simulation showed the moving average strategy to be much inferior to the two buy-and-hold models. Every threshold regardless of the length of the moving average yielded a negative return. In addition, the losses per threshold were spread throughout the majority of stocks. Altogether, therefore, considerable evidence was found in favour of the random walk theory of stock price behavior. / Business, Sauder School of / Graduate

A dissertation submitted in fulfillment of the requirements for the degree of Masters in Science in the, The Structured Light Group Department of Physics, University of the Witwatersrand, Johannesburg, 2018 / At the quantum level, entities and systems often behave counter-intuitively which we have come to describe with wave-particle duality. Accordingly, a particle that moves definitively from one position to another in our classical experience does something completely different on the quantum scale. The particle is not localized at any one position, but spreads out over all the possibilities as it moves. Here the particle can interfere with itself with wave-like propagation and generate, what is known as a Quantum Walk. This is the quantum mechanical analogue of the already well-known and used Random Walk where the particle takes random steps across the available positions, building up a series of random paths. The mechanics behind the random walk has already proved largely useful in many fields, from finance to simulation and computation. Analogously, the quantum walk promises even greater potential for development. Here, with many of the algorithms already developed, it would allow computations to outperform current classical methods on an unprecedented level. Additionally, by implementing these mechanics on various levels, it is possible to simulate and understand various quantum mechanical systems and phenomenon. This phenomenon consequently represents a significant advancement in several fields of study. Although there has been considerable theoretical development of this phenomenon, its potential now lies in implementing these quantum walks physically. Here, a physical system is required such that the quantum walk may be sustainably achieved, easily detected and dynamically altered as needed. Many systems have been subsequently proposed and demonstrated, but the criteria for a useful quantum walk leaves many such avenues lacking with the largest number of steps yet to reach 100 to the best of our knowledge. As a result, we explored a classical take on the quantum walk, utilizing the wave properties of light to achieve analogous mechanics with the advantage of the increased degree of control and robustness. While such an approach is not new, we considered a particular method where the quantum walk could be implemented in the spatial modes of light. By exploiting the non-separability (classical entanglement) of polarization and orbital angular momentum, such a classical quantum walk could be realized with greater intuitive implications and the potential for further study into the quantum mechanical nature of this phenomenon, over and above that of the other schemes, by walking the quantum-classical divide. The work presented here subsequently centres on experimentally achieving a quantum walk with classically entangled light for further development and useful implementation. Moreover, this work focused on demonstrating the sustainability, control and robustness necessary for this scheme to be beneficial for future development. In Chapter 1, an intuitive introduction is presented, highlighting the mechanics of this phenomenon that make it different from the Random walk counterpart. We also explore why this phenomenon is of such great importance with an overview of applications that physical implementation can result in. A more in-depth look into the dynamics and mathematical aspects of this walk is found in Chapter 2. Here a detailed look into the mechanisms behind the walk is taken with mathematical analysis. Furthermore, the subsequent differences and implications associated viii with utilizing classical light is explored, answering the question of what is quantum about the quantum walk. As the focus of this chapter is largely cemented in establishing a solid theoretical background, we also look into the physics behind classical light and develop the theoretical basis in the direction of structured light, with an emphasis on establishing classically entangled beams. Chapters 3 and 4 present the experimental work done throughout the course of this dissertation. With Chapter 3 we establish and characterize the elements necessary for obtaining a quantum walk in the spatial modes of light by utilizing waveplates as coins, q-plates as step operators and entanglement generators as well as mode sorters in a detection system. We also look into the characteristics of the modes that will be produced with these elements, allowing the propagation properties of the beam to be experimentally accounted for. In Chapter 4, we examine the experimental considerations of how to achieve a realistic and sustainable quantum walk. Here, we consider and implement the scheme proposed by Goyal et. al. [] where a light pulse follows a looped path, allowing the physical resources to be constant throughout the walk. We also show the experimental limitations of the equipment being utilized and the various steps needed to compensate. Finally, we not only implement a quantum walk with classically entangled light for the first time, but also demonstrate the flexibility of the system. Here, we achieve a maximum of 8 steps and show 5 different types of walks with varying dynamics and symmetry. The last chapter (Chapter 5) gives a summary of the dissertation in context of the goals and achievements of this work. The outlook and implications of these results are discussed and future steps outlined for extending this scheme into a highly competitive alternative for viable implementation of quantum walks for computing and simulation. / XL2019

In the present thesis, we investigate representations of Cuntz algebras coming from dilations of row co-isometries. First, we give some general results about such representations. Next, we show that by labeling a random walk, a row co-isometry appears naturally. We give an explicit form for representations that come from such random walks. Then, we give some conditions relating to the reducibility of these representations, exploring how properties of a random walk relate to the Cuntz algebra representation that comes from it

No description available.

This dissertation studies systems of "competing" discrete random walks as discrete and continuous time processes. A system is thought of as containing n imaginary particles performing random walks on lines parallel to the x-axis in Cartesian space. The particles act completely independently of each other and have, in general, different starting coordinates. In the discrete time situation, the motion of the n particles is governed by n independent streams of Bernoulli trials with success probabilities p₁, p₂,…, and p_n respectively. A success for any particle at a trial causes that particle to move one unit toward the origin, and a failure causes it to take a "zero-step" (i.e. remain stationary). A probabilistic description is first given of the positions of the particles at arbitrary points in time, and this is extended to provide time dependent and independent probabilities of which particle is the winner, that is to say, of which particle first reaches the origin. In this case "draws" are possible and the relevant probabilities are derived. The results are expressed, in particular, in terms of Generalized Hypergeometric Functions. In addition, formulae are given for the duration of what may now be regarded as a race with winning post at the origin. In the continuous time situation, the motion of the n particles is governed by n independent Poisson streams, in general, having different parameters. A treatment similar to that for the discrete time situation is given with the exception of draw probabilities which in this case are not possible. Approximations are obtained in many cases. Apart from their practical utility, these give insight into the operation of the systems in that they reveal how changes in one or more of the parameters may affect the win and draw probabilities and also the duration of the race. A chapter is devoted to practical applications. Here it is shown how the theory of random walks racing toward the origin can be utilized as a basic framework for explaining the operation of, and answering pertinent questions concerning several apparently diverse situations. Examples are Lanchester Combat theory, inventory control, reliability and queueing theory. / Ph. D.

This thesis studies two Markov processes describing the evolution of a system of many interacting random components. These processes undergo an absorbing-state phase transition, i.e., as one variates the parameter values, the process exhibits a transition from a convergence regime to one of the absorbing-states to an active regime. In Chapter 2 we study Activated Random Walk, which is an interacting particle system where the particles can be of two types and their number is conserved. Firstly, we provide a new lower bound for the critical density on Z as a function of the jump distribution and of the sleeping rate and we prove that the critical density is not a constant function of the jump distribution. Secondly, we prove that on Zd in the case of biased jump distribution the critical density is strictly less than one, provided that the sleeping rate is small enough. This answers a question that has been asked by Dickman, Rolla, Sidoravicius [9, 28] in the case of biased jump distribution. Our results have been presented in [33]. In Chapter 3 we study a class of probabilistic cellular automata which are related by a natural coupling to a special type of oriented percolation model. Firstly, we consider the process on a finite torus of size n, which is ergodic for any parameter value. By employing dynamic-renormalization techniques, we prove that the average absorption time grows exponentially (resp. logarithmically) with n when the model on Z is in the active (resp. absorbing) regime. This answers a question that has been asked by Toom [37]. Secondly, we study how the neighbourhood of the model affects the critical probability for the process on Z. We provide a lower bound for the critical probability as a function of the neighbourhood and we show that our estimates are sharp by comparing them with our numerical estimates. Our results have been presented in [34, 35].

This thesis studies two problems centered around non-backtracking walks on graphs. First, we analyze the spectrum of the non-backtracking matrix of a graph. We show how to obtain the eigenvectors of the non-backtracking matrix using a smaller matrix and in doing so, create a block diagonal decomposition which more clearly expresses the non-backtracking matrix eigenvalues. Additionally, we develop upper and lower bounds on the matrix spectrum and use the spectrum to investigate properties of the graph. Second, we investigate the difference between PageRank and non-backtracking PageRank. We show some instances where there is no difference and develop an algorithm to compare PageRank and non-backtracking PageRank under certain conditions using $\mu$-PageRank.

<p>This dissertation includes my research works during Ph.D. career about three different kinds of random walks in (dynamical) random environments. It includes my two published papers “Functional weak limit of random walks in cooling random environments” which has been published in electronic communications in probability in 2020, and “Variable speed symmetric random walk driven by the simple symmetric exclusion process” which is the joint work with Peterson and Menezes and has been published in electronic journals of probability in 2021. This dissertation also includes my two other projects, one is the joint work with Janjigian and Emrah about moderate deviation and exit time estimates in integrable directed polymer models. The other one is the joint work with Peterson and Conrado that extends the weak limit of random walks in cooling randon environments with underlying environment is in the transient case.</p>

O avanço das pesquisas em redes complexas proporcionou desenvolvimentos significativos para a compreensão de sistemas complexos. Uma rede complexa é modelada matematicamente por meio de um grafo, onde cada vértice representa uma unidade dinâmica e suas interações são simbolizadas por um conjunto de arestas. Para se determinar propriedades estruturais desse sistema, caminhadas aleatórias tem-se mostrado muito úteis pois dependem apenas de informações locais (vértices vizinhos). Entre elas, destaca-se o passeio auto-excludente (SAW) que possui a restrição de não visitar um vértice que já foi alcançado, ou seja, apresenta memória do caminho percorrido. Por este motivo o SAW tem apresentado melhores resultados do que caminhantes sem restrição, na exploração da rede. Entretanto, por não se tratar de um processo Markoviano ele apresenta grande complexidade analítica, tornando indispensável o uso de simulações computacionais para melhor compreensão de sua dinâmica em diferentes topologias. Mesmo com as dificuldades analíticas, o SAW se tornou uma ferramenta promissora na identificação de estruturas de comunidades. Apesar de sua importância, detecção de comunidades permanece um problema em aberto devido à alta complexidade computacional associada ao problema de optimização, além da falta de uma definição formal do significado de comunidade. Neste trabalho, propomos um método de detecção de comunidades baseado em SAW para extrair uma estrutura de comunidades da rede otimizando o parâmetro modularidade. Combinamos características extraídas desta dinâmica com a análise de componentes principais para posteriormente classificar os vértices em grupos por meio da clusterização hierárquica aglomerativa. Para avaliar a performance deste novo algoritmo, comparamos os resultados com outras quatro técnicas populares: Girvan-Newman, Fastgreedy, Walktrap e Infomap, aplicados em dois tipos de redes sintéticas e nove redes reais diversificadas e bem conhecidas. Para os benchmarks, esta nova técnica produziu resultados satisfatórios em diferentes combinações de parâmetros, como tamanho de rede, distribuição de grau e número de comunidades. Já para as redes reais, obtivemos valores de modularidade superior aos métodos tradicionais, indicando uma distribuição de grupos mais adequada à realidade. Feito isso, generalizamos o algoritmo para redes ponderadas e digrafos, além de incorporar metadados à estrutura topológica a fim de melhorar a classificação em grupos. / The progress in complex networks research has provided significant understanding of complex systems. A complex network is mathematically modeled by a graph, where each vertex represents a dynamic unit and its interactions are symbolized by groups of edges. To determine the system structural properties, random walks have shown to be a useful tool since they depend only on local information (neighboring vertices). Among them, the selfavoiding walk (SAW) stands out for not visiting vertices that have already been reached, meaning it can record the path that has been travelled. For this reason, SAW has shown better results when compared to non-restricted walkers network exploration methods. However, as SAW is not a Markovian process, it has a great analytical complexity and needs computational simulations to improve its dynamics in different topologies. Even with the analytical complexity, SAW has become a promising tool to identify the community structure. Despite its significance, detecting communities remains an unsolved problem due to its high computational complexity associated to optimization issues and the lack of a formal definition of communities. In this work, we propose a method to identify communities based on SAW to extract community structure of a network through optimization of the modularity score. Combining technical features of this dynamic with principal components analyses, we classify the vertices in groups by using hierarchical agglomerative clustering. To evaluate the performance of this new algorithm, we compare the results with four other popular techniques: Girvan-Newman, Fastgreedy, Walktrap and Infomap, applying the algorithm in two types of synthetic networks and nine different and well known real ones. For the benchmarks, this new technique shows satisfactory results for different combination of parameters as network size, degree distribution and number of communities. As for real networks, our data shows better modularity values when compared to traditional methods, indicating a group distribution most suitable to reality. Furthermore, the algorithm was adapted for general weighted networks and digraphs in addition to metadata incorporated to topological structure, in order to improve the results of groups classifications.