Limits...
A scaling law for random walks on networks.

Perkins TJ, Foxall E, Glass L, Edwards R - Nat Commun (2014)

Bottom Line: The dynamics of many natural and artificial systems are well described as random walks on a network: the stochastic behaviour of molecules, traffic patterns on the internet, fluctuations in stock prices and so on.The vast literature on random walks provides many tools for computing properties such as steady-state probabilities or expected hitting times.The form of the distribution depends only on the structure of the network, while the stepping probabilities control the parameters of the distribution.

View Article: PubMed Central - PubMed

Affiliation: Ottawa Hospital Research Institute, 501 Smyth Road, Ottawa, Ontario, Canada K1H 8L6.

ABSTRACT
The dynamics of many natural and artificial systems are well described as random walks on a network: the stochastic behaviour of molecules, traffic patterns on the internet, fluctuations in stock prices and so on. The vast literature on random walks provides many tools for computing properties such as steady-state probabilities or expected hitting times. Previously, however, there has been no general theory describing the distribution of possible paths followed by a random walk. Here, we show that for any random walk on a finite network, there are precisely three mutually exclusive possibilities for the form of the path distribution: finite, stretched exponential and power law. The form of the distribution depends only on the structure of the network, while the stepping probabilities control the parameters of the distribution. We use our theory to explain path distributions in domains such as sports, music, nonlinear dynamics and stochastic chemical kinetics.

No MeSH data available.


Related in: MedlinePlus

Stretched exponential path distributions explained by random walks on networks: sequences of outs in American baseball and symbolic dynamics of the Lorenz attractor.(a) Outs sequences from the half-innings in the first game of the 2012 season between the Kansas City Athletics and the Anaheim Angels (coordinates perturbed slightly for visibility). (b) The empirical frequencies of outs sequences from all 2012 Major League baseball games (blue) do not conform to a power law, as shown by the poor fit of a least-squares regression line (cyan). (c) A random walk model, with stepping probabilities estimated from the same 2012 data. (d) The empirical path probabilities (blue) scale as the third root of rank, with slope close to that predicted by our theory (red). (e) xy projection of a trajectory of the Lorenz system. Any trajectory can be divided into return paths to the plane x=0 travelling in the  direction. Qualitatively, each path comprises one or more loops in the right halfspace (R, or x>0), followed by one or more loops in the left halfspace (L, or x<0). (f) The empirical frequencies of different qualitative paths in a very long simulated trajectory (blue) are not power law. (g) A random walk model of the qualitative dynamics with stepping probabilities estimated from the simulated trajectory. (h) The empirical frequencies scale as the square root of rank, with slope very close to that predicted by our theory (red).
© Copyright Policy - open-access
Related In: Results  -  Collection

License
getmorefigures.php?uid=PMC4214407&req=5

f2: Stretched exponential path distributions explained by random walks on networks: sequences of outs in American baseball and symbolic dynamics of the Lorenz attractor.(a) Outs sequences from the half-innings in the first game of the 2012 season between the Kansas City Athletics and the Anaheim Angels (coordinates perturbed slightly for visibility). (b) The empirical frequencies of outs sequences from all 2012 Major League baseball games (blue) do not conform to a power law, as shown by the poor fit of a least-squares regression line (cyan). (c) A random walk model, with stepping probabilities estimated from the same 2012 data. (d) The empirical path probabilities (blue) scale as the third root of rank, with slope close to that predicted by our theory (red). (e) xy projection of a trajectory of the Lorenz system. Any trajectory can be divided into return paths to the plane x=0 travelling in the direction. Qualitatively, each path comprises one or more loops in the right halfspace (R, or x>0), followed by one or more loops in the left halfspace (L, or x<0). (f) The empirical frequencies of different qualitative paths in a very long simulated trajectory (blue) are not power law. (g) A random walk model of the qualitative dynamics with stepping probabilities estimated from the simulated trajectory. (h) The empirical frequencies scale as the square root of rank, with slope very close to that predicted by our theory (red).

Mentions: To demonstrate the use of our theory in understanding path distributions in real systems, and in particular the largely overlooked case of stretched exponential scaling, we turn first to the game of American baseball. Each baseball game has nine innings, and each inning has two halves: one in which the visiting team is ‘at-bat’ and the home team is in the field, and one in which the home team is at-bat and the visiting team is in the field. Each half-inning begins with the batting team at zero ‘outs’ and concludes when the team reaches three outs. Each time an individual player comes up to bat, his actions, and the actions of the players on the field, result in zero or more outs. For instance, if the first batter generated an out, the second batter did not and the third batter generated two outs, as happened twice during the first 2012-season game between the Kansas City Athletics and the Anaheim Angels, then the sequence of total outs would be 0113 (see Fig. 2a for this and other example trajectories). Reasoning about outs sequences is part of the strategy of the game, including the order in which players are selected to bat and the batting instructions they receive. Thus understanding outs sequences in strategically important.


A scaling law for random walks on networks.

Perkins TJ, Foxall E, Glass L, Edwards R - Nat Commun (2014)

Stretched exponential path distributions explained by random walks on networks: sequences of outs in American baseball and symbolic dynamics of the Lorenz attractor.(a) Outs sequences from the half-innings in the first game of the 2012 season between the Kansas City Athletics and the Anaheim Angels (coordinates perturbed slightly for visibility). (b) The empirical frequencies of outs sequences from all 2012 Major League baseball games (blue) do not conform to a power law, as shown by the poor fit of a least-squares regression line (cyan). (c) A random walk model, with stepping probabilities estimated from the same 2012 data. (d) The empirical path probabilities (blue) scale as the third root of rank, with slope close to that predicted by our theory (red). (e) xy projection of a trajectory of the Lorenz system. Any trajectory can be divided into return paths to the plane x=0 travelling in the  direction. Qualitatively, each path comprises one or more loops in the right halfspace (R, or x>0), followed by one or more loops in the left halfspace (L, or x<0). (f) The empirical frequencies of different qualitative paths in a very long simulated trajectory (blue) are not power law. (g) A random walk model of the qualitative dynamics with stepping probabilities estimated from the simulated trajectory. (h) The empirical frequencies scale as the square root of rank, with slope very close to that predicted by our theory (red).
© Copyright Policy - open-access
Related In: Results  -  Collection

License
Show All Figures
getmorefigures.php?uid=PMC4214407&req=5

f2: Stretched exponential path distributions explained by random walks on networks: sequences of outs in American baseball and symbolic dynamics of the Lorenz attractor.(a) Outs sequences from the half-innings in the first game of the 2012 season between the Kansas City Athletics and the Anaheim Angels (coordinates perturbed slightly for visibility). (b) The empirical frequencies of outs sequences from all 2012 Major League baseball games (blue) do not conform to a power law, as shown by the poor fit of a least-squares regression line (cyan). (c) A random walk model, with stepping probabilities estimated from the same 2012 data. (d) The empirical path probabilities (blue) scale as the third root of rank, with slope close to that predicted by our theory (red). (e) xy projection of a trajectory of the Lorenz system. Any trajectory can be divided into return paths to the plane x=0 travelling in the direction. Qualitatively, each path comprises one or more loops in the right halfspace (R, or x>0), followed by one or more loops in the left halfspace (L, or x<0). (f) The empirical frequencies of different qualitative paths in a very long simulated trajectory (blue) are not power law. (g) A random walk model of the qualitative dynamics with stepping probabilities estimated from the simulated trajectory. (h) The empirical frequencies scale as the square root of rank, with slope very close to that predicted by our theory (red).
Mentions: To demonstrate the use of our theory in understanding path distributions in real systems, and in particular the largely overlooked case of stretched exponential scaling, we turn first to the game of American baseball. Each baseball game has nine innings, and each inning has two halves: one in which the visiting team is ‘at-bat’ and the home team is in the field, and one in which the home team is at-bat and the visiting team is in the field. Each half-inning begins with the batting team at zero ‘outs’ and concludes when the team reaches three outs. Each time an individual player comes up to bat, his actions, and the actions of the players on the field, result in zero or more outs. For instance, if the first batter generated an out, the second batter did not and the third batter generated two outs, as happened twice during the first 2012-season game between the Kansas City Athletics and the Anaheim Angels, then the sequence of total outs would be 0113 (see Fig. 2a for this and other example trajectories). Reasoning about outs sequences is part of the strategy of the game, including the order in which players are selected to bat and the batting instructions they receive. Thus understanding outs sequences in strategically important.

Bottom Line: The dynamics of many natural and artificial systems are well described as random walks on a network: the stochastic behaviour of molecules, traffic patterns on the internet, fluctuations in stock prices and so on.The vast literature on random walks provides many tools for computing properties such as steady-state probabilities or expected hitting times.The form of the distribution depends only on the structure of the network, while the stepping probabilities control the parameters of the distribution.

View Article: PubMed Central - PubMed

Affiliation: Ottawa Hospital Research Institute, 501 Smyth Road, Ottawa, Ontario, Canada K1H 8L6.

ABSTRACT
The dynamics of many natural and artificial systems are well described as random walks on a network: the stochastic behaviour of molecules, traffic patterns on the internet, fluctuations in stock prices and so on. The vast literature on random walks provides many tools for computing properties such as steady-state probabilities or expected hitting times. Previously, however, there has been no general theory describing the distribution of possible paths followed by a random walk. Here, we show that for any random walk on a finite network, there are precisely three mutually exclusive possibilities for the form of the path distribution: finite, stretched exponential and power law. The form of the distribution depends only on the structure of the network, while the stepping probabilities control the parameters of the distribution. We use our theory to explain path distributions in domains such as sports, music, nonlinear dynamics and stochastic chemical kinetics.

No MeSH data available.


Related in: MedlinePlus