Brief Announcement: Node Sampling Using Centrifugal Random Walks.

We propose distributed algorithms for sampling networks based on a new class of random walks that we call Centrifugal Random Walks (CRW). A CRW is a random walk that starts at a source and always moves away from it. We propose CRW algorithms for connected networks with arbitrary probability distributions, and for grids and networks with regular concentric connectivity with distance based distributions. All CRW sampling algorithms select a node with the exact probability distribution, do not need warm-up, and end in a number of hops bounded by the network diameter.

Node sampling using random centrifugal walks

Sampling a network with a given probability distribution has been identified as a useful operation. In this paper we propose distributed algorithms for sampling networks, so that nodes are selected by a special node, called the source, with a given probability distribution. All these algorithms are based on a new class of random walks, that we call Random Centrifugal Walks (RCW). A RCW is a random walk that starts at the source and always moves away from it. Firstly, an algorithm to sample any connected network using RCW is proposed. The algorithm assumes that each node has a weight, so that the sampling process must select a node with a probability proportional to its weight. This algorithm requires a preprocessing phase before the sampling of nodes. In particular, a minimum diameter spanning tree (MDST) is created in the network, and then nodes weights are efficiently aggregated using the tree. The good news are that the preprocessing is done only once, regardless of the number of sources and the number of samples taken from the network. After that, every sample is done with a RCW whose length is bounded by the network diameter. Secondly, RCW algorithms that do not require preprocessing are proposed for grids and networks with regular concentric connectivity, for the case when the probability of selecting a node is a function of its distance to the source. The key features of the RCW algorithms (unlike previous Markovian approaches) are that (1) they do not need to warm-up (stabilize), (2) the sampling always finishes in a number of hops bounded by the network diameter, and (3) it selects a node with the exact probability distribution.

Empirical analysis of traffic volume for the application of the options theory to highway concessions

*************************************************************************************** EL WCTR es un Congreso de reconocido prestigio internacional en el ámbito de la investigación del transporte que hasta el 2010 publicaba sus libros de abstracts con ISBN. Por ello consideramos que debería seguir teníendose en cuenta para los indicadores de calidad ******************************************************************************************* Investment projects in the field of transportation infrastructures have a high degree of uncertainty and require an important amount of resources. In highway concessions in particular, the calculation of the Net Present Value (NPV) of the project by means of the discount of cash flows, may lead to erroneous results when the project incorporates certain flexibility. In these cases, the theory of real options is an alternative tool for the valuation of concessions. When the variable that generates uncertainty (in our case, the traffic) follows a random walk (or Geometric Brownian Motion), we can calculate the value of the options embedded in the contract starting directly from the process followed by that variable. This procedure notably simplifies the calculation method. In order to test the hypothesis of the evolution of traffic as a Geometric Brownian Motion, we have used the available series of traffic in Spanish highways, and we have applied the Augmented Dickey-Fuller approach, which is the most widely used test for this kind of study. The main result of the analysis is that we cannot reject the hypothesis that traffic follows a Geometric Brownian Motion in the majority of both toll highways and free highways in Spain.

Random recursion

Thesis (Ph.D.)--University of Washington, 2016-06

Pseudo memory effects, majorization and entropy in quantum random walks

A quantum random walk on the integers exhibits pseudo memory effects, in that its probability distribution after N steps is determined by reshuffling the first N distributions that arise in a classical random walk with the same initial distribution. In a classical walk, entropy increase can be regarded as a consequence of the majorization ordering of successive distributions. The Lorenz curves of successive distributions for a symmetric quantum walk reveal no majorization ordering in general. Nevertheless, entropy can increase, and computer experiments show that it does so on average. Varying the stages at which the quantum coin system is traced out leads to new quantum walks, including a symmetric walk for which majorization ordering is valid but the spreading rate exceeds that of the usual symmetric quantum walk.

Essays on exchange rate economics

Exchange rate economics has achieved substantial development in the past few decades. Despite extensive research, a large number of unresolved problems remain in the exchange rate debate. This dissertation studied three puzzling issues aiming to improve our understanding of exchange rate behavior. Chapter Two used advanced econometric techniques to model and forecast exchange rate dynamics. Chapter Three and Chapter Four studied issues related to exchange rates using the theory of New Open Economy Macroeconomics. ^ Chapter Two empirically examined the short-run forecastability of nominal exchange rates. It analyzed important empirical regularities in daily exchange rates. Through a series of hypothesis tests, a best-fitting fractionally integrated GARCH model with skewed student-t error distribution was identified. The forecasting performance of the model was compared with that of a random walk model. Results supported the contention that nominal exchange rates seem to be unpredictable over the short run in the sense that the best-fitting model cannot beat the random walk model in forecasting exchange rate movements. ^ Chapter Three assessed the ability of dynamic general-equilibrium sticky-price monetary models to generate volatile foreign exchange risk premia. It developed a tractable two-country model where agents face a cash-in-advance constraint and set prices to the local market; the exogenous money supply process exhibits time-varying volatility. The model yielded approximate closed form solutions for risk premia and real exchange rates. Numerical results provided quantitative evidence that volatile risk premia can endogenously arise in a new open economy macroeconomic model. Thus, the model had potential to rationalize the Uncovered Interest Parity Puzzle. ^ Chapter Four sought to resolve the consumption-real exchange rate anomaly, which refers to the inability of most international macro models to generate negative cross-correlations between real exchange rates and relative consumption across two countries as observed in the data. While maintaining the assumption of complete asset markets, this chapter introduced endogenously segmented asset markets into a dynamic sticky-price monetary model. Simulation results showed that such a model could replicate the stylized fact that real exchange rates tend to move in an opposite direction with respect to relative consumption. ^

Essays on Exchange Rate Economics

Exchange rate economics has achieved substantial development in the past few decades. Despite extensive research, a large number of unresolved problems remain in the exchange rate debate. This dissertation studied three puzzling issues aiming to improve our understanding of exchange rate behavior. Chapter Two used advanced econometric techniques to model and forecast exchange rate dynamics. Chapter Three and Chapter Four studied issues related to exchange rates using the theory of New Open Economy Macroeconomics. Chapter Two empirically examined the short-run forecastability of nominal exchange rates. It analyzed important empirical regularities in daily exchange rates. Through a series of hypothesis tests, a best-fitting fractionally integrated GARCH model with skewed student-t error distribution was identified. The forecasting performance of the model was compared with that of a random walk model. Results supported the contention that nominal exchange rates seem to be unpredictable over the short run in the sense that the best-fitting model cannot beat the random walk model in forecasting exchange rate movements. Chapter Three assessed the ability of dynamic general-equilibrium sticky-price monetary models to generate volatile foreign exchange risk premia. It developed a tractable two-country model where agents face a cash-in-advance constraint and set prices to the local market; the exogenous money supply process exhibits time-varying volatility. The model yielded approximate closed form solutions for risk premia and real exchange rates. Numerical results provided quantitative evidence that volatile risk premia can endogenously arise in a new open economy macroeconomic model. Thus, the model had potential to rationalize the Uncovered Interest Parity Puzzle. Chapter Four sought to resolve the consumption-real exchange rate anomaly, which refers to the inability of most international macro models to generate negative cross-correlations between real exchange rates and relative consumption across two countries as observed in the data. While maintaining the assumption of complete asset markets, this chapter introduced endogenously segmented asset markets into a dynamic sticky-price monetary model. Simulation results showed that such a model could replicate the stylized fact that real exchange rates tend to move in an opposite direction with respect to relative consumption.

Analysis and modelling of immune cell behaviour in lymph nodes based on multi-photon imaging

This thesis presents quantitative studies of T cell and dendritic cell (DC) behaviour in mouse lymph nodes (LNs) in the naive state and following immunisation. These processes are of importance and interest in basic immunology, and better understanding could improve both diagnostic capacity and therapeutic manipulations, potentially helping in producing more effective vaccines or developing treatments for autoimmune diseases. The problem is also interesting conceptually as it is relevant to other fields where 3D movement of objects is tracked with a discrete scanning interval. A general immunology introduction is presented in chapter 1. In chapter 2, I apply quantitative methods to multi-photon imaging data to measure how T cells and DCs are spatially arranged in LNs. This has been previously studied to describe differences between the naive and immunised state and as an indicator of the magnitude of the immune response in LNs, but previous analyses have been generally descriptive. The quantitative analysis shows that some of the previous conclusions may have been premature. In chapter 3, I use Bayesian state-space models to test some hypotheses about the mode of T cell search for DCs. A two-state mode of movement where T cells can be classified as either interacting to a DC or freely migrating is supported over a model where T cells would home in on DCs at distance through for example the action of chemokines. In chapter 4, I study whether T cell migration is linked to the geometric structure of the fibroblast reticular network (FRC). I find support for the hypothesis that the movement is constrained to the fibroblast reticular cell (FRC) network over an alternative 'random walk with persistence time' model where cells would move randomly, with a short-term persistence driven by a hypothetical T cell intrinsic 'clock'. I also present unexpected results on the FRC network geometry. Finally, a quantitative method is presented for addressing some measurement biases inherent to multi-photon imaging. In all three chapters, novel findings are made, and the methods developed have the potential for further use to address important problems in the field. In chapter 5, I present a summary and synthesis of results from chapters 3-4 and a more speculative discussion of these results and potential future directions.

Conditional entropy and predictability for non-reversible Markov systems

The purpose of this thesis is to clarify the role of non-equilibrium stationary currents of Markov processes in the context of the predictability of future states of the system. Once the connection between the predictability and the conditional entropy is established, we provide a comprehensive approach to the definition of a multi-particle Markov system. In particular, starting from the well-known theory of random walk on network, we derive the non-linear master equation for an interacting multi-particle system under the one-step process hypothesis, highlighting the limits of its tractability and the prop- erties of its stationary solution. Lastly, in order to study the impact of the NESS on the predictability at short times, we analyze the conditional entropy by modulating the intensity of the stationary currents, both for a single-particle and a multi-particle Markov system. The results obtained analytically are numerically tested on a 5-node cycle network and put in correspondence with the stationary entropy production. Furthermore, because of the low dimensionality of the single-particle system, an analysis of its spectral properties as a function of the modulated stationary currents is performed.

Spontaneous symmetry breaking in amnestically induced persistence

We investigate a recently proposed non-Markovian random walk model characterized by loss of memories of the recent past and amnestically induced persistence. We report numerical and analytical results showing the complete phase diagram, consisting of four phases, for this system: (i) classical nonpersistence, (ii) classical persistence, (iii) log-periodic nonpersistence, and (iv) log-periodic persistence driven by negative feedback. The first two phases possess continuous scale invariance symmetry, however, log-periodicity breaks this symmetry. Instead, log-periodic motion satisfies discrete scale invariance symmetry, with complex rather than real fractal dimensions. We find for log-periodic persistence evidence not only of statistical but also of geometric self-similarity.

Stretching and folding mechanism in foams

We have described the stretching and folding of foams in a vertical Hele-Shaw cell containing air and a surfactant solution, from a sequence of upside-down flips. Besides the firactal dimension of the foam, we have observed the logistic growth for the soap film length. The stretching and folding mechanism is present during the foam formation, and this mechanism is observed even after the foam has reached its respective maximum fractal dimension. Observing the motion of bubbles inside the foam, large bubbles present power spectrum associated with random walk motion in both directions, while the small bubbles are scattered like balls in a Galton board. (C) 2008 Published by Elsevier B.V.

Dynamic Imaging in Electrical Impedance Tomography of the Human Chest With Online Transition Matrix Identification

One of the electrical impedance tomography objectives is to estimate the electrical resistivity distribution in a domain based only on electrical potential measurements at its boundary generated by an imposed electrical current distribution into the boundary. One of the methods used in dynamic estimation is the Kalman filter. In biomedical applications, the random walk model is frequently used as evolution model and, under this conditions, poor tracking ability of the extended Kalman filter (EKF) is achieved. An analytically developed evolution model is not feasible at this moment. The paper investigates the identification of the evolution model in parallel to the EKF and updating the evolution model with certain periodicity. The evolution model transition matrix is identified using the history of the estimated resistivity distribution obtained by a sensitivity matrix based algorithm and a Newton-Raphson algorithm. To numerically identify the linear evolution model, the Ibrahim time-domain method is used. The investigation is performed by numerical simulations of a domain with time-varying resistivity and by experimental data collected from the boundary of a human chest during normal breathing. The obtained dynamic resistivity values lie within the expected values for the tissues of a human chest. The EKF results suggest that the tracking ability is significantly improved with this approach.

Improving the tracking capability of adaptive filters via convex combination

As is well known, Hessian-based adaptive filters (such as the recursive-least squares algorithm (RLS) for supervised adaptive filtering, or the Shalvi-Weinstein algorithm (SWA) for blind equalization) converge much faster than gradient-based algorithms [such as the least-mean-squares algorithm (LMS) or the constant-modulus algorithm (CMA)]. However, when the problem is tracking a time-variant filter, the issue is not so clear-cut: there are environments for which each family presents better performance. Given this, we propose the use of a convex combination of algorithms of different families to obtain an algorithm with superior tracking capability. We show the potential of this combination and provide a unified theoretical model for the steady-state excess mean-square error for convex combinations of gradient- and Hessian-based algorithms, assuming a random-walk model for the parameter variations. The proposed model is valid for algorithms of the same or different families, and for supervised (LMS and RLS) or blind (CMA and SWA) algorithms.

Modelling dispersal behaviour on a fractal landscape

We use a spatially explicit population model to explore the population consequences of different habitat selection mechanisms on landscapes with fractal variation in habitat quality. We consider dispersal strategies ranging from random walks to perfect habitat selectors for two species of arboreal marsupial, the greater glider (Petauroides volans) and the mountain brushtail possum (Trichosurus caninus). In this model increasing habitat selection means individuals obtain higher quality territories, but experience increased mortality during dispersal. The net effect is that population sizes are smaller when individuals actively select habitat. We find positive relationships between habitat quality and population size can occur when individuals do not use information about the entire landscape when habitat quality is spatially autocorrelated. We also find that individual behaviour can mitigate the negative effects of spatial variation on population average survival and fecundity. (C) 1998 Elsevier Science Ltd. All rights reserved.

Characterization of the rat exploratory behavior in the elevated plus-maze with Markov chains

The elevated plus-maze is an animal model of anxiety used to study the effect of different drugs on the behavior of the animal It consists of a plus-shaped maze with two open and two closed arms elevated 50 cm from the floor The standard measures used to characterize exploratory behavior in the elevated plus-maze are the time spent and the number of entries in the open arms In this work we use Markov chains to characterize the exploratory behavior of the rat in the elevated plus-maze under three different conditions normal and under the effects of anxiogenic and anxiolytic drugs The spatial structure of the elevated plus-maze is divided into squares which are associated with states of a Markov chain By counting the frequencies of transitions between states during 5-min sessions in the elevated plus-maze we constructed stochastic matrices for the three conditions studied The stochastic matrices show specific patterns which correspond to the observed behaviors of the rat under the three different conditions For the control group the stochastic matrix shows a clear preference for places in the closed arms This preference is enhanced for the anxiogenic group For the anxiolytic group the stochastic matrix shows a pattern similar to a random walk Our results suggest that Markov chains can be used together with the standard measures to characterize the rat behavior in the elevated plus-maze (C) 2010 Elsevier B V All rights reserved