151 resultados para Random-Walk Hypothesis
Resumo:
The stochasticity of domain-wall (DW) motion in magnetic nanowires has been probed by measuring slow fluctuations, or noise, in electrical resistance at small magnetic fields. By controlled injection of DWs into isolated cylindrical nanowires of nickel, we have been able to track the motion of the DWs between the electrical leads by discrete steps in the resistance. Closer inspection of the time dependence of noise reveals a diffusive random walk of the DWs with a universal kinetic exponent. Our experiments outline a method with which electrical resistance is able to detect the kinetic state of the DWs inside the nanowires, which can be useful in DW-based memory designs.
Resumo:
Random walks describe diffusion processes, where movement at every time step is restricted to only the neighboring locations. We construct a quantum random walk algorithm, based on discretization of the Dirac evolution operator inspired by staggered lattice fermions. We use it to investigate the spatial search problem, that is, to find a marked vertex on a d-dimensional hypercubic lattice. The restriction on movement hardly matters for d > 2, and scaling behavior close to Grover's optimal algorithm (which has no restriction on movement) can be achieved. Using numerical simulations, we optimize the proportionality constants of the scaling behavior, and demonstrate the approach to that for Grover's algorithm (equivalent to the mean-field theory or the d -> infinity limit). In particular, the scaling behavior for d = 3 is only about 25% higher than the optimal d -> infinity value.
Resumo:
We investigate the spatial search problem on the two-dimensional square lattice, using the Dirac evolution operator discretized according to the staggered lattice fermion formalism. d = 2 is the critical dimension for the spatial search problem, where infrared divergence of the evolution operator leads to logarithmic factors in the scaling behavior. As a result, the construction used in our accompanying article A. Patel and M. A. Rahaman, Phys. Rev. A 82, 032330 (2010)] provides an O(root N ln N) algorithm, which is not optimal. The scaling behavior can be improved to O(root N ln N) by cleverly controlling the massless Dirac evolution operator by an ancilla qubit, as proposed by Tulsi Phys. Rev. A 78, 012310 (2008)]. We reinterpret the ancilla control as introduction of an effective mass at the marked vertex, and optimize the proportionality constants of the scaling behavior of the algorithm by numerically tuning the parameters.
Resumo:
Sampling based planners have been successful in path planning of robots with many degrees of freedom, but still remains ineffective when the configuration space has a narrow passage. We present a new technique based on a random walk strategy to generate samples in narrow regions quickly, thus improving efficiency of Probabilistic Roadmap Planners. The algorithm substantially reduces instances of collision checking and thereby decreases computational time. The method is powerful even for cases where the structure of the narrow passage is not known, thus giving significant improvement over other known methods.
Resumo:
We investigate the spatial search problem on the two-dimensional square lattice, using the Dirac evolution operator discretized according to the staggered lattice fermion formalism. d=2 is the critical dimension for the spatial search problem, where infrared divergence of the evolution operator leads to logarithmic factors in the scaling behavior. As a result, the construction used in our accompanying article [ A. Patel and M. A. Rahaman Phys. Rev. A 82 032330 (2010)] provides an O(√NlnN) algorithm, which is not optimal. The scaling behavior can be improved to O(√NlnN) by cleverly controlling the massless Dirac evolution operator by an ancilla qubit, as proposed by Tulsi Phys. Rev. A 78 012310 (2008). We reinterpret the ancilla control as introduction of an effective mass at the marked vertex, and optimize the proportionality constants of the scaling behavior of the algorithm by numerically tuning the parameters.
Resumo:
The spatial search problem on regular lattice structures in integer number of dimensions d >= 2 has been studied extensively, using both coined and coinless quantum walks. The relativistic Dirac operator has been a crucial ingredient in these studies. Here, we investigate the spatial search problem on fractals of noninteger dimensions. Although the Dirac operator cannot be defined on a fractal, we construct the quantum walk on a fractal using the flip-flop operator that incorporates a Klein-Gordon mode. We find that the scaling behavior of the spatial search is determined by the spectral (and not the fractal) dimension. Our numerical results have been obtained on the well-known Sierpinski gaskets in two and three dimensions.
Resumo:
A discrete-time dynamics of a non-Markovian random walker is analyzed using a minimal model where memory of the past drives the present dynamics. In recent work N. Kumar et al., Phys. Rev. E 82, 021101 (2010)] we proposed a model that exhibits asymptotic superdiffusion, normal diffusion, and subdiffusion with the sweep of a single parameter. Here we propose an even simpler model, with minimal options for the walker: either move forward or stay at rest. We show that this model can also give rise to diffusive, subdiffusive, and superdiffusive dynamics at long times as a single parameter is varied. We show that in order to have subdiffusive dynamics, the memory of the rest states must be perfectly correlated with the present dynamics. We show explicitly that if this condition is not satisfied in a unidirectional walk, the dynamics is only either diffusive or superdiffusive (but not subdiffusive) at long times.
Resumo:
We study the probability distribution of the angle by which the tangent to the trajectory rotates in the course of a plane random walk. It is shown that the determination of this distribution function can be reduced to an integral equation, which can be rigorously transformed into a differential equation of Hill's type. We derive the asymptotic distribution for very long walks.
Resumo:
We construct a quantum random walk algorithm, based on the Dirac operator instead of the Laplacian. The algorithm explores multiple evolutionary branches by superposition of states, and does not require the coin toss instruction of classical randomised algorithms. We use this algorithm to search for a marked vertex on a hypercubic lattice in arbitrary dimensions. Our numerical and analytical results match the scaling behaviour of earlier algorithms that use a coin toss instruction.
Resumo:
We demonstrate the phenomenon of self-organized criticality (SOC) in a simple random walk model described by a random walk of a myopic ant, i.e., a walker who can see only nearest neighbors. The ant acts on the underlying lattice aiming at uniform digging, i.e., reduction of the height profile of the surface but is unaffected by the underlying lattice. In one, two, and three dimensions we have explored this model and have obtained power laws in the time intervals between consecutive events of "digging." Being a simple random walk, the power laws in space translate to power laws in time. We also study the finite size scaling of asymptotic scale invariant process as well as dynamic scaling in this system. This model differs qualitatively from the cascade models of SOC.
Resumo:
We study by means of experiments and Monte Carlo simulations, the scattering of light in random media, to determine the distance up to which photons travel along almost undeviated paths within a scattering medium, and are therefore capable of casting a shadow of an opaque inclusion embedded within the medium. Such photons are isolated by polarisation discrimination wherein the plane of linear polarisation of the input light is continuously rotated and the polarisation preserving component of the emerging light is extracted by means of a Fourier transform. This technique is a software implementation of lock-in detection. We find that images may be recovered to a depth far in excess of that predicted by the diffusion theory of photon propagation. To understand our experimental results, we perform Monte Carlo simulations to model the random walk behaviour of the multiply scattered photons. We present a. new definition of a diffusing photon in terms of the memory of its initial direction of propagation, which we then quantify in terms of an angular correlation function. This redefinition yields the penetration depth of the polarisation preserving photons. Based on these results, we have formulated a model to understand shadow formation in a turbid medium, the predictions of which are in good agreement with our experimental results.
Resumo:
Background: A genetic network can be represented as a directed graph in which a node corresponds to a gene and a directed edge specifies the direction of influence of one gene on another. The reconstruction of such networks from transcript profiling data remains an important yet challenging endeavor. A transcript profile specifies the abundances of many genes in a biological sample of interest. Prevailing strategies for learning the structure of a genetic network from high-dimensional transcript profiling data assume sparsity and linearity. Many methods consider relatively small directed graphs, inferring graphs with up to a few hundred nodes. This work examines large undirected graphs representations of genetic networks, graphs with many thousands of nodes where an undirected edge between two nodes does not indicate the direction of influence, and the problem of estimating the structure of such a sparse linear genetic network (SLGN) from transcript profiling data. Results: The structure learning task is cast as a sparse linear regression problem which is then posed as a LASSO (l1-constrained fitting) problem and solved finally by formulating a Linear Program (LP). A bound on the Generalization Error of this approach is given in terms of the Leave-One-Out Error. The accuracy and utility of LP-SLGNs is assessed quantitatively and qualitatively using simulated and real data. The Dialogue for Reverse Engineering Assessments and Methods (DREAM) initiative provides gold standard data sets and evaluation metrics that enable and facilitate the comparison of algorithms for deducing the structure of networks. The structures of LP-SLGNs estimated from the INSILICO1, INSILICO2 and INSILICO3 simulated DREAM2 data sets are comparable to those proposed by the first and/or second ranked teams in the DREAM2 competition. The structures of LP-SLGNs estimated from two published Saccharomyces cerevisae cell cycle transcript profiling data sets capture known regulatory associations. In each S. cerevisiae LP-SLGN, the number of nodes with a particular degree follows an approximate power law suggesting that its degree distributions is similar to that observed in real-world networks. Inspection of these LP-SLGNs suggests biological hypotheses amenable to experimental verification. Conclusion: A statistically robust and computationally efficient LP-based method for estimating the topology of a large sparse undirected graph from high-dimensional data yields representations of genetic networks that are biologically plausible and useful abstractions of the structures of real genetic networks. Analysis of the statistical and topological properties of learned LP-SLGNs may have practical value; for example, genes with high random walk betweenness, a measure of the centrality of a node in a graph, are good candidates for intervention studies and hence integrated computational – experimental investigations designed to infer more realistic and sophisticated probabilistic directed graphical model representations of genetic networks. The LP-based solutions of the sparse linear regression problem described here may provide a method for learning the structure of transcription factor networks from transcript profiling and transcription factor binding motif data.
Resumo:
We have investigated the impact of dissipationless minor galaxy mergers on the angular momentum of the remnant. Our simulations cover a range of initial orbital characteristics, and the system consists of a massive galaxy with a bulge and disk merging with a much less massive (one-tenth or one-twentieth) gasless companion that has a variety of morphologies (disk-or elliptical-like) and central baryonic mass concentrations. During the process of merging, the orbital angular momentum is redistributed into the internal angular momentum of the final system; the internal angular momentum of the primary galaxy can increase or decrease depending on the relative orientation of the orbital spin vectors (direct or retrograde), while the initially nonrotating dark matter halo always gains angular momentum. The specific angular momentum of the stellar component always decreases independently of the orbital parameters or morphology of the satellite, the decrease in the rotation velocity of the primary galaxy is accompanied by a change in the anisotropy of the orbits, and the ratio of rotation speed to velocity dispersion of the merger remnant is lower than the initial value, not only because of an increase in the dispersion but also of the slowing-down of the disk rotation. We briefly discuss several astrophysical implications of these results, suggesting that minor mergers do not cause a "random walk" process of the angular momentum of the stellar disk component of galaxies, but rather a steady decrease. Minor mergers may play a role in producing the large scatter observed in the Tully-Fisher relation for S0 galaxies, as well as in the increase of the velocity dispersion and the decrease in upsilon/sigma at large radii as observed in S0 galaxies.
Resumo:
The statistical properties of fractional Brownian walks are used to construct a path integral representation of the conformations of polymers with different degrees of bond correlation. We specifically derive an expression for the distribution function of the chains’ end‐to‐end distance, and evaluate it by several independent methods, including direct evaluation of the discrete limit of the path integral, decomposition into normal modes, and solution of a partial differential equation. The distribution function is found to be Gaussian in the spatial coordinates of the monomer positions, as in the random walk description of the chain, but the contour variables, which specify the location of the monomer along the chain backbone, now depend on an index h, the degree of correlation of the fractional Brownian walk. The special case of h=1/2 corresponds to the random walk. In constructing the normal mode picture of the chain, we conjecture the existence of a theorem regarding the zeros of the Bessel function.
Resumo:
In this paper, we report an analysis of the protein sequence length distribution for 13 bacteria, four archaea and one eukaryote whose genomes have been completely sequenced, The frequency distribution of protein sequence length for all the 18 organisms are remarkably similar, independent of genome size and can be described in terms of a lognormal probability distribution function. A simple stochastic model based on multiplicative processes has been proposed to explain the sequence length distribution. The stochastic model supports the random-origin hypothesis of protein sequences in genomes. Distributions of large proteins deviate from the overall lognormal behavior. Their cumulative distribution follows a power-law analogous to Pareto's law used to describe the income distribution of the wealthy. The protein sequence length distribution in genomes of organisms has important implications for microbial evolution and applications. (C) 1999 Elsevier Science B.V. All rights reserved.