Search Results

Navigation and search

Sergey N. Dorogovtsev

in Lectures on Complex Networks

This chapter considers the specifics of walks, navigation, and search processes in networks of various architectures and geometries. It starts with discussion of random walks on complex networks, ... More

This chapter considers the specifics of walks, navigation, and search processes in networks of various architectures and geometries. It starts with discussion of random walks on complex networks, then biased random walks and in application to packet routing in the Internet. It discusses the famous Kleinberg's problem and searchability of networks with underlining metric spaces. Finally, the Google PageRank is explained.Less

RANDOM WALK

Robert M. Mazo

in Brownian Motion: Fluctuations, Dynamics, and Applications

This chapter introduces the idea of random walk and studies a number of simple cases to illustrate the concepts, mostly in one dimension. The symmetric Pearson walk, the biased walk, and the ... More

This chapter introduces the idea of random walk and studies a number of simple cases to illustrate the concepts, mostly in one dimension. The symmetric Pearson walk, the biased walk, and the persistent walk are treated for lattice walks in discrete time, and the results generalized to continuum walks. Asymptotic results for large number of steps or long times are emphasized. The problems of random walk with boundaries and first passage times are introduced. Remarks on further generalizations and problems are briefly made.Less

The random walk

Eric Renshaw

in Stochastic Population Processes: Analysis, Approximations, Simulations

This chapter considers path analyses for random walks, which leads on to first passage and return probabilities and the Arc Sine Law. Both absorbing and reflecting barriers are considered in some ... More

This chapter considers path analyses for random walks, which leads on to first passage and return probabilities and the Arc Sine Law. Both absorbing and reflecting barriers are considered in some depth. Since the assumption of independent steps is not universally true, a classic case being the movement of share prices driven by market sentiment, the correlated random walk is introduced.Less

Random Walk and Mean-Reversion

Christian Gollier

in Pricing the Planet's Future: The Economics of Discounting in an Uncertain World

This chapter illustrates that the shape of the term structure of discount rates is determined by the way the wealth effect and the precautionary effects evolve with the time horizon. When the growth ... More

This chapter illustrates that the shape of the term structure of discount rates is determined by the way the wealth effect and the precautionary effects evolve with the time horizon. When the growth rate of consumption is constant, then consumption increases exponentially, and the intertemporal rate of substitution, which is the discount factor, decreases exponentially. This requires that the discount rate is constant. The simplest extension of this to uncertainty is to assume that the growth rate of the economy follows a random walk. In that case, the variance of log consumption increases linearly, which yields an exponentially increasing precautionary effect for the discount factor. This justifies a constant precautionary effect on the discount rate, yielding a crucial result for the theory of efficient discount rates.Less

Solving the Tower of Hanoi with Random Moves

Max A. Alekseyev and Toby Berger

in The Mathematics of Various Entertaining Subjects: Research in Recreational Math

This chapter studies solutions of the Tower of Hanoi puzzle and some of its variants with random moves, where each move is chosen uniformly from the set of the valid moves in the current state. The ... More

This chapter studies solutions of the Tower of Hanoi puzzle and some of its variants with random moves, where each move is chosen uniformly from the set of the valid moves in the current state. The Tower of Hanoi puzzle consists of n disks of distinct sizes distributed across three pegs. At a single move it is permitted to transfer a disk from the top of one peg to the top of another peg, if this results in a valid state, i.e. a particular distribution of the disks across the pegs. The chapter proves the exact formulas for the expected number of random moves to solve the puzzles. It also presents an alternative proof for one of the formulas that couples a theorem about expected commute times of random walks on graphs with the delta-to-wye transformation used in the analysis of three-phase AC systems for electrical power distribution.Less

Securities Markets and Their Efficiency

Hendrik S. Houthakker and Peter J. Williamson

in The Economics of Financial Markets

The discussion in this chapter begins with an analysis of central trading places, which looks at the economics of securities trading and the rationale for brokers and central trading places (with ... More

The discussion in this chapter begins with an analysis of central trading places, which looks at the economics of securities trading and the rationale for brokers and central trading places (with reference to US stock exchanges), the types of orders buyers or sellers may place in the market and the way these are executed, and the system of ‘specialists’ commonly found in stock exchanges (which is designed to provide a smooth and continuous market for individual stocks). Next, it briefly examines financial markets without central trading places. This is followed by a look at the mechanics of securities trading in the stock exchanges in London (UK) and Tokyo (Japan). The last section of the chapter discusses the operational efficiency of the stock market and the efficient market hypothesis (EFM), looking at the implications of central exchanges in which information flows rapidly between participants for the efficiency of the stock market as a whole and, in particular, at the ‘random walk’ behavior of share prices.Less

Mathematics of networks: An introduction to the mathematical tools used in the study of networks, tools that will be important to many subsequent developments

M. E. J. Newman

in Networks: An Introduction

This chapter introduces the basic theoretical tools used to describe and analyze networks, most of which come from graph theory, the branch of mathematics that deals with networks. Topics covered ... More

This chapter introduces the basic theoretical tools used to describe and analyze networks, most of which come from graph theory, the branch of mathematics that deals with networks. Topics covered include the adjacency matrix, weighted networks, directed networks, hypergraphs, bipartite networks, trees, planar networks, the graph Laplacian, and random walks. Exercises are provided at the end of the chapter.Less

Special topics and interdisciplinary models

Ralph Skomski

in Simple Models of Magnetism

Atomic disorder has far-reaching consequences for the behavior of magnetic materials. It modifies the electronic structure but does not necessarily destroy ferromagnetism, as exemplified by amorphous ... More

Atomic disorder has far-reaching consequences for the behavior of magnetic materials. It modifies the electronic structure but does not necessarily destroy ferromagnetism, as exemplified by amorphous ferromagnets. Spin glasses combine disorder with competing exchange, and their ground state is neither ferromagnetic nor antiferromagnetic. The equilibrium and nonequilibrium properties of spin glasses have remained a complex problem, and several models have been developed, such as the Edwards–Anderson and Sherrington–Kirkpatrick models. On a mean-field level, the determination of ordering and spin-glass temperatures involves the diagonalisation of large random matrices. This chapter discusses disordered magnets and spin glasses, ferromagnetic order in inhomogeneous magnets, soft matter, transport, magnetism, random walks, polymers, diffusion, polymers and critical dimensionality, gases in magnetic metals, magnetoresistance, Bruggeman model, nanostructures, thin films, length scales in nanomagnetism, random anisotropy, and two-phase nanostructures. The use of models in disciplines other than magnetism is also considered, including metallurgy, biology and medicine, and social sciences.Less

Random Walks and Rapid Mixing

Cristopher Moore and Stephan Mertens

in The Nature of Computation

Random sampling is a technique for dealing with possible states or solutions having an exponentially large space. The best method of random sampling generally involves a random walk or a Markov ... More

Random sampling is a technique for dealing with possible states or solutions having an exponentially large space. The best method of random sampling generally involves a random walk or a Markov chain. A Markov chain requires a number of steps to approach equilibrium, and thus provide a good random sample of the state space. This number of steps is called mixing time, which can be calculated by thinking about how quickly its choices overwhelm the system’s memory of its initial state, the extent to which one part of a system influences another, and how smoothly probability flows from one part of the state space to another. This chapter explores random walks and rapid mixing, first by considering a classic example from physics: a block of iron. It then discusses transition matrices, ergodicity, coupling, spectral gap, and expanders, as well as the role of conductance and the spectral gap in rapid mixing. It concludes by showing that temporal mixing is closely associated with spatial mixing.Less

Properties of Integrated Processes

Anindya Banerjee, Juan J. Dolado, John W. Galbraith, and David F. Hendry

in Co-integration, Error Correction, and the Econometric Analysis of Non-Stationary Data

Presents the important properties of integrated variables and sets out some of the preliminary asymptotic theories essential for the consideration of such processes. It explores the concepts of unit ... More

Presents the important properties of integrated variables and sets out some of the preliminary asymptotic theories essential for the consideration of such processes. It explores the concepts of unit roots, non‐stationarity, orders of integration, and near integration, and demonstrates the use of the theory in understanding the behaviour of least‐squares estimators in spurious regressions and in models involving integrated data. The theoretical analysis is accompanied by evidence from Monte Carlo simulations. Several examples are also provided to illustrate the use of Wiener distribution theory in deriving asymptotic results for such models.Less

Universality and the continuum limit

Jean Zinn-Justin

in Phase Transitions and Renormalization Group

This chapter discusses the related questions of universality and macroscopic continuum limit in random systems with a large number of degrees of freedom. It first explains the notion of universality ... More

This chapter discusses the related questions of universality and macroscopic continuum limit in random systems with a large number of degrees of freedom. It first explains the notion of universality using the classical example of the central limit theorem in probability theory. It then discusses the properties of the random walk on a lattice, where universality is directly related to the continuum limit. In both examples, the chapter is interested in the collective properties of an infinite number of random variables in a situation where the probability of large deviations with respect to the mean value decreases fast enough. They differ in the sense that a random walk is based on a spatial structure that does not necessarily exist in the case of the central limit theorem. From the study of these first examples emerges the importance of Gaussian distributions, and this justifies the technical considerations of Chapter 2. The chapter introduces some transformations, acting on distributions, which decrease the number of random variables. It shows that Gaussian distributions are attractive fixed points for these transformations. This will provides the first, extremely simple, applications of the renormalization group (RG) ideas and allows the establishment of corresponding terminology. Finally, in this context of the random walk, a path integral representation is associated with the existence of a continuum limit. Exercises are provided at the end of the chapter.Less

The Central Binomial Coefficient

Thomas Koshy

in Catalan Numbers with Applications

This chapter focuses on the ubiquitous central binomial coefficient and its properties. It confirms that Cn is a positive integer. The chapter covers Lagrange's identity.

Ecological and Behavioral Approaches to Search Behavior

David W. Stephens, Iain Couzin, and Luc-Alain Giraldeau

in Cognitive Search: Evolution, Algorithms, and the Brain

This chapter offers a selective review of behavioral and ecological perspectives on search behavior. Basic results from foraging theory are presented and their relationship to search is discussed. ... More

This chapter offers a selective review of behavioral and ecological perspectives on search behavior. Basic results from foraging theory are presented and their relationship to search is discussed. Techniques for the statistical description of searching motion are outlined, with a focus on the correlated random walk and the so-called Lévy flights—a technique that holds considerable promise. The problems of search in groups are reviewed at several levels. Both cooperative search (as conducted, e.g., by members of a social insect colony) and group movements of extremely selfish animals are considered. Finally, a review is provided of the producer-scrounger game, which considers the interactions within groups when some individuals parasitize the search behavior of others. The implications of these ideas are discussed and potential future directions for future enquiry are highlighted.Less

A Theory of the Decreasing Term Structure of Discount Rates

Christian Gollier

in Pricing the Planet's Future: The Economics of Discounting in an Uncertain World

This chapter aims to provide a unified theoretical foundation to the term structure of discount rates. To do this the chapter develops a benchmark model based on two assumptions: individual ... More

This chapter aims to provide a unified theoretical foundation to the term structure of discount rates. To do this the chapter develops a benchmark model based on two assumptions: individual preferences toward risk, and the nature of the uncertainty over economic growth. Previously, it was shown that constant relative risk aversion, combined with a random walk for the growth of log consumption, yields a flat term structure for efficient discount rates. In this chapter, these two assumptions are relaxed by using a stochastic dominance approach. Stochastic models of economic growth with mean-reversion, Markov switches, and parametric uncertainty all exhibit some forms of positive statistical dependence of successive growth rates. Because this tends to magnify the long-term risk, it is the driving force of the decreasing nature of the term structure.Less

Metric stability for random walks (with applications in renormalization theory)

Carlos Gustavo Moreira and Daniel Smania

Araceli Bonifant, Mikhail Lyubich, and Scott Sutherland (eds)

in Frontiers in Complex Dynamics: In Celebration of John Milnor's 80th Birthday

This chapter considers the stability of metric (measure-theoretic) properties of dynamical systems. A well-known example is that of (C²) expanding maps on the circle; this class is structurally ... More

This chapter considers the stability of metric (measure-theoretic) properties of dynamical systems. A well-known example is that of (C²) expanding maps on the circle; this class is structurally stable, and all such maps have an absolutely continuous and ergodic invariant probability satisfying certain decay of correlations estimates. In particular, in the measure theoretic sense, most of the orbits are dense in the phase space. The chapter uses the idea of random walk, which describes transitions between various dynamical scales, to prove a surprising rigidity result: the conjugacy between two unimodal maps of the same degree with Feigenbaum or wild attractors is absolutely continuous.Less

Standard finance theory

NEIL F. JOHNSON, PAUL JEFFERIES, and PAK MING HUI

in Financial Market Complexity

This chapter focuses on the basics of standard finance theory. It discusses the details of a random walk and quantifying risk using volatility σ. It then looks at the hedging of risk within standard ... More

This chapter focuses on the basics of standard finance theory. It discusses the details of a random walk and quantifying risk using volatility σ. It then looks at the hedging of risk within standard finance theory using derivatives beginning with a review of what derivatives are followed by a description of the Black–Scholes theory.Less

Examples of Markovian processes

Melvin Lax, Wei Cai, and Min Xu

in Random Processes in Physics and Finance

Consider two physical problems describable by the same random process. The first process is the radioactive decay of a collection of nuclei. The second is the production of photoelectrons by a steady ... More

Consider two physical problems describable by the same random process. The first process is the radioactive decay of a collection of nuclei. The second is the production of photoelectrons by a steady beam of light on a photodetector. In both cases, we can let a discrete, positive, integer valued, variable n(t) represent the number of counts emitted in the time interval between 0 and t. This is the essence of the Poisson process, an example of Markovian process. Other examples of Markovian processes include the one dimensional random walk, gambler's ruin, diffusion processes and the Einstein relation, Brownian motion, Langevin theory of velocities in Brownian motion, Langevin theory of positions in Brownian motion, and chaos.Less