Search NASA⌕ Search

SEARCH · Search NASA

Results for “random walks”

Search indexed NASA NTRS and DOE OSTI research on propulsion, heat transfer, battery materials and energy systems. Follow report and document links to the original sources.

Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.

At least 19 records
All sourcesNASA NTRSDOE OSTI
NASA NTRS1995

Is walking a random walk? Evidence for long-range correlations in stride interval of human gait

Complex fluctuation of unknown origin appear in the normal gait pattern. These fluctuations might be described as being (1) uncorrelated white noise, (2) short-range correlations, or (3) long-range correlations with power-law scaling. To test these possibilities, the stride interval of 10 healthy young men was measured as they walked for 9 min at their usual rate. From these time series we calculated scaling indexes by using a modified random walk analysis and power spectral analysis. Both indexes indicated the presence of long-range self-similar correlations extending over hundreds of steps; the stride interval at any time depended on the stride interval at remote previous times, and this dependence decayed in a scale-free (fractallike) power-law fashion. These scaling indexes were significantly different from those obtained after random shuffling of the original time series, indicating the importance of the sequential ordering of the stride interval. We demonstrate that conventional models of gait generation fail to reproduce the observed scaling behavior and introduce a new type of central pattern generator model that sucessfully accounts for the experimentally observed long-range correlations.

Hausdorff, Jeffrey M.↗
NASA NTRS1973

Monte-Carlo analysis of rarefied-gas diffusion including variance reduction using the theory of Markov random walks

Molecular diffusion through a rarefied gas is analyzed by using the theory of Markov random walks. The Markov walk is simulated on the computer by using random numbers to find the new states from the appropriate transition probabilities. As the sample molecule during its random walk passes a scoring position, which is a location at which the macroscopic diffusing flow variables such as molecular flux and molecular density are desired, an appropriate payoff is scored. The payoff is a function of the sample molecule velocity. For example, in obtaining the molecular flux across a scoring position, the random walk payoff is the net number of times the scoring position has been crossed in the positive direction. Similarly, when the molecular density is required, the payoff is the sum of the inverse velocity of the sample molecule passing the scoring position. The macroscopic diffusing flow variables are then found from the expected payoff of the random walks.

Perlmutter, M.↗
NASA NTRS1972

Random walk study of electron motion in helium in crossed electromagnetic fields

Random walk theory, previously adapted to electron motion in the presence of an electric field, is extended to include a transverse magnetic field. In principle, the random walk approach avoids mathematical complexity and concomitant simplifying assumptions and permits determination of energy distributions and transport coefficients within the accuracy of available collisional cross section data. Application is made to a weakly ionized helium gas. Time of relaxation of electron energy distribution, determined by the random walk, is described by simple expressions based on energy exchange between the electron and an effective electric field. The restrictive effect of the magnetic field on electron motion, which increases the required number of collisions per walk to reach a terminal steady state condition, as well as the effect of the magnetic field on electron transport coefficients and mean energy can be quite adequately described by expressions involving only the Hall parameter.

Englert, G. W.↗
DOE OSTI2021

Dimensional Interpolation for Random Walk

In this work, we employ a simple and accurate dimensional interpolation formula for the shapes of random walks at D = 3 and D = 2 based on the analytically known solutions at both limits D = ∞ and D = 1. The results obtained for the radius of gyration of an arbitrary shaped object have about 2% error compared with accurate numerical results at D = 3 and D = 2. We also calculated the asphericity for a three-dimensional random walk using the dimensional interpolation formula. The results agree very well with the numerically simulated results. The method is general and can be used to estimate other properties of random walks.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗
DOE OSTI2020

C-SAW: a framework for graph sampling and random walk on GPUs

Many applications require to learn, mine, analyze and visualize large-scale graphs. These graphs are often too large to be addressed efficiently using conventional graph processing technologies. Fortunately, recent research efforts find out graph sampling and random walk, which significantly reduce the size of original graphs, can benefit the tasks of learning, mining, analyzing and visualizing large graphs by capturing the desirable graph properties. This paper introduces C-SAW, the first framework that accelerates Sampling and Random Walk framework on GPUs. Particularly, C-SAW makes three contributions: First, our framework provides a generic API which allows users to implement a wide range of sampling and random walk algorithms with ease. Second, offloading this framework on GPU, we introduce warp-centric parallel selection, and two novel optimizations for collision migration. Third, towards supporting graphs that exceed the GPU memory capacity, we introduce efficient data transfer optimizations for out-of-memory and multi-GPU sampling, such as workload-aware scheduling and batched multi-instance sampling. Taken together, our framework constantly outperforms the state of the art projects in addition to the capability of supporting a wide range of sampling and random walk algorithms.

97 MATHEMATICS AND COMPUTING↗
NASA NTRS1974

Random walk theory applied to electron avalanche formation

Use of microscopic detail in random walk theory describing the initial formations of a large number of avalanches shows that concomitant electron transport coefficients quickly relax to equilibrium values. This enables the use of random walks having step sizes and probabilities based only on local electric field strengths and densities. A self-consistent avalanche solution which accounts for collective long range Coulomb interactions as well as short range elastic and inelastic collisions between electrons and background atoms is demonstrated for helium. Avalanche growth retardation followed by an abrupt growth augmentation as time proceeds is shown to be associated with the formation of regions of charge density extrema near the avalanche axis and within the axial distance covered by the electron swarm.

Englert, G. W.↗
DOE OSTI2022

Neuromorphic scaling advantages for energy-efficient random walk computations

Neuromorphic computing, which aims to replicate the computational structure and architecture of the brain in synthetic hardware, has typically focused on artificial intelligence applications. What is less explored is whether such brain-inspired hardware can provide value beyond cognitive tasks. Here we show that the high degree of parallelism and configurability of spiking neuromorphic architectures makes them well suited to implement random walks via discrete-time Markov chains. Overall, these random walks are useful in Monte Carlo methods, which represent a fundamental computational tool for solving a wide range of numerical computing tasks. Using IBM’s TrueNorth and Intel’s Loihi neuromorphic computing platforms, we show that our neuromorphic computing algorithm for generating random walk approximations of diffusion offers advantages in energy-efficient computation compared with conventional approaches. We also show that our neuromorphic computing algorithm can be extended to more sophisticated jump-diffusion processes that are useful in a range of applications, including financial economics, particle physics and machine learning.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2022

Statistical properties of sites visited by independent random walks

The set of visited sites and the number of visited sites are two basic properties of the random walk trajectory. Here, we consider two independent random walks on hyper-cubic lattices and study ordering probabilities associated with these characteristics. The first is the probability that during the time interval (0, t), the number of sites visited by a walker never exceeds that of another walker. The second is the probability that the sites visited by a walker remain a subset of the sites visited by another walker. Using numerical simulations, we investigate the leading asymptotic behaviors of the ordering probabilities in spatial dimensions d = 1, 2, 3, 4. We also study the time evolution of the number of ties between the number of visited sites. We show analytically that the average number of ties increases as a 1 ln t with a 1 = 0.970 508 in one dimension and as (ln t) 2 in two dimensions.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2024

Understanding random-walk dynamical phase coexistence through waiting times

We study the appearance of first-order dynamical phase transitions (DPTs) as “intermittent” coexisting phases in the fluctuations of random walks on graphs. We show that the diverging timescale leading to critical behavior is the waiting time to jump from one phase to another. This timescale is crucial for observing the system's relaxation to stationarity and demonstrate ergodicity of the system at criticality. We illustrate these results through three analytical examples which provide insights into random walks exploring random graphs. Published by the American Physical Society 2024

Stuhrmann, David C. (ORCID:0009000726916649)↗
DOE OSTI2020

Hypergraph Random Walks, Laplacians, and Clustering

We propose a flexible framework for clustering hypergraph-structured data based on recently proposed random walks utilizing edge-dependent vertex weights. When incorporating edge-dependent vertex weights (EDVW), a weight is associated with each vertex-hyperedge pair, yielding a weighted incidence matrix of the hypergraph. Such weightings have been utilized in term-document representations of text data sets. We explain how random walks with EDVW serve to construct different hypergraph Laplacian matrices, and then develop a suite of clustering methods that use these incidence matrices and Laplacians for hypergraph clustering. Using 20Newsgroup, U.S. patent, Reuters' Corpus Volume 1, and genetics data sets, we compare the performance of these clustering algorithms experimentally against a variety of existing hypergraph clustering methods. We show that the proposed methods produce higher-quality clusters.

hypergraphs, clustering, laplacian, random walk, M↗
DOE OSTI2024

Quantum Random Walk Simulator Using Ultrafast Optical Switches

Quantum random walk processes have many intriguing applications in high energy physics including the simulation of parton shower evolution. We will present the design and initial results of a fiber loop time-bin quantum walk architecture using the hardware platform already in operation at the Fermilab Quantum Network in which the state of the photon is defined by its time-of-arrival. The fiber loop consists of an unbalanced Mach-Zehnder interferometer implemented using an ultrafast electro-optical switch. The input switch controls the photon path within the interferometer, while the output switch will direct the photon back into the interferometer or to single photon detectors to measure the probability distribution of arrival times. Depending on which path the photon takes each pass through the loop, its wave function will interfere on these optical switches similar to quantum interference on a beam splitter. This work is an important step towards utilizing real-world advantages of quantum information protocols to solve problems in high energy physics.

Cameron, Andrew [Fermilab]↗
NASA NTRS2002

Random Walk Method for Potential Problems

A local Random Walk Method (RWM) for potential problems governed by Lapalace's and Paragon's equations is developed for two- and three-dimensional problems. The RWM is implemented and demonstrated in a multiprocessor parallel environment on a Beowulf cluster of computers. A speed gain of 16 is achieved as the number of processors is increased from 1 to 23.

Krishnamurthy, T.↗
DOE OSTI2024

A Finite Difference informed Random Walk solver for simulating radiation defect evolution in polycrystalline structures with strongly inhomogeneous diffusivity

Diffusivity of species and defects on grain boundaries is usually several orders of magnitude larger than that inside grains. Such strongly inhomogeneous diffusivity requires prohibitively high computational demands for modeling microstructural evolution. Here, this paper presents a highly-efficient numerical solver, combining the Finite Difference method and Random Walk model, designed for accurately modeling strongly inhomogeneous diffusion within polycrystalline structures. The proposed solver, termed Finite Difference informed Random Walk (FDiRW), integrates a customized Finite Difference (cFD) scheme tailored for fast diffusion along thin grain boundaries represented by a single-layer of nodes. Numerical experiments demonstrate that the FDiRW solver achieves an impressive efficiency gain of 1560x compared to traditional Finite Difference methods while maintaining accuracy, making it feasible for personal computer machines to handle diffusional systems with strongly inhomogeneous diffusivity across static polycrystalline microstructures. The model has been successfully applied to simulate radiation defect evolution, showcasing its scalability to engineering scales in both length and time dimensions.

36 MATERIALS SCIENCE↗
DOE OSTI2020

Neuromorphic scaling advantages for energy-efficient random walk computations

Computing stands to be radically improved by neuromorphic computing (NMC) approaches inspired by the brain's incredible efficiency and capabilities. Most NMC research, which aims to replicate the brain's computational structure and architecture in man-made hardware, has focused on artificial intelligence; however, less explored is whether this brain-inspired hardware can provide value beyond cognitive tasks. We demonstrate that high-degree parallelism and configurability of spiking neuromorphic architectures makes them well-suited to implement random walks via discrete time Markov chains. Such random walks are useful in Monte Carlo methods, which represent a fundamental computational tool for solving a wide range of numerical computing tasks. Additionally, we show how the mathematical basis for a probabilistic solution involving a class of stochastic differential equations can leverage those simulations to provide solutions for a range of broadly applicable computational tasks. Despite being in an early development stage, we find that NMC platforms, at a sufficient scale, can drastically reduce the energy demands of high-performance computing platforms.

59 BASIC BIOLOGICAL SCIENCES↗