3 ms·

But a random walk is precisely a stochastic process for which the _next state_ depends only on the _current state_. In terms of graphs (where _random walk_ com

But a random walk is precisely a stochastic process for which the _next state_ depends only on the _current state_. In terms of graphs (where _random walk_ comes from), the next node is decided by randomly selecting a neighbor of the current node.

deleted 2y ago
[deleted]
seanhunter 2y ago
That's not true for random walks in general I don't think. A random walk is a process derived from taking random steps in some mathematical space. It can include jumps and it can include memory. Take a "path-avoiding" random walk. At time t the distribution of the next step depends on whether or not I have at some point hit any of the adjacent nodes in the current path. That's not the current state, that's memory.
- JohnKemeny 2y ago
  A random walk on a graph is a stochastic process that starts at a vertex and, at each step, moves to a randomly chosen neighboring vertex. Formally: Given a graph, a random walk is a sequence of vertices [v1, v2, ..., vk] such that each v{i+1} is selected uniformly at random from the neighbors of vi. In weighted graphs, the next vertex is chosen with probability proportional to edge weights.
  - seanhunter 2y ago
    I’m pretty sure it’s not a requirement that the distribution is uniform and also not path-dependent as per the example I gave - a random walk where you’re not allowed to visit a node more than once.
    - JohnKemeny 2y ago
      Here's a reference for the definition I'm using: https://www.cs.yale.edu/homes/spielman/561/lect10-18.pdf https://www.cs.yale.edu/homes/spielman/561/lect10-18.pdf It's from lecture notes (pdf) from a course in Spectral Graph Theory by Professor Daniel Spielman at Yale.
      - seanhunter 2y ago
        Those notes look interesting thanks. I’ve really never heard of someone saying you have to have uniform probability for a random walk on a graph. In fact the context where I’m most familiar with them (lattice/grid pricers) it’s always specified something like “the probability of branch a is p and b is 1-p” (ie explicitly not uniform) and they aren’t a weighted graph in the normal sense.
        srean 2y ago
        It doesn't have to be uniform or memory less. However, in general when people mention random walks without further qualifications they are usually talking about the uniform and memoryless case. That vanilla case can be generalized extensively, on kinds of state spaces, kinds of index sets, kinds of dependence and so on.
        seanhunter 2y ago
        That makes sense. THanks.
- vladimirralev 2y ago
  But also "the memory" of the random walk can be encoded in a state itself. In your example you can just keep accumulating the visited nodes, so your state space will be now the space of tuples of nodes from your initial space.

deleted 2y ago

[deleted]

seanhunter 2y ago

That's not true for random walks in general I don't think. A random walk is a process derived from taking random steps in some mathematical space. It can include jumps and it can include memory. Take a "path-avoiding" random walk. At time t the distribution of the next step depends on whether or not I have at some point hit any of the adjacent nodes in the current path. That's not the current state, that's memory.

JohnKemeny 2y ago
A random walk on a graph is a stochastic process that starts at a vertex and, at each step, moves to a randomly chosen neighboring vertex. Formally: Given a graph, a random walk is a sequence of vertices [v1, v2, ..., vk] such that each v{i+1} is selected uniformly at random from the neighbors of vi. In weighted graphs, the next vertex is chosen with probability proportional to edge weights.
- seanhunter 2y ago
  I’m pretty sure it’s not a requirement that the distribution is uniform and also not path-dependent as per the example I gave - a random walk where you’re not allowed to visit a node more than once.
  - JohnKemeny 2y ago
    Here's a reference for the definition I'm using: https://www.cs.yale.edu/homes/spielman/561/lect10-18.pdf https://www.cs.yale.edu/homes/spielman/561/lect10-18.pdf It's from lecture notes (pdf) from a course in Spectral Graph Theory by Professor Daniel Spielman at Yale.
    - seanhunter 2y ago
      Those notes look interesting thanks. I’ve really never heard of someone saying you have to have uniform probability for a random walk on a graph. In fact the context where I’m most familiar with them (lattice/grid pricers) it’s always specified something like “the probability of branch a is p and b is 1-p” (ie explicitly not uniform) and they aren’t a weighted graph in the normal sense.
      - srean 2y ago
        It doesn't have to be uniform or memory less. However, in general when people mention random walks without further qualifications they are usually talking about the uniform and memoryless case. That vanilla case can be generalized extensively, on kinds of state spaces, kinds of index sets, kinds of dependence and so on.
        seanhunter 2y ago
        That makes sense. THanks.
vladimirralev 2y ago
But also "the memory" of the random walk can be encoded in a state itself. In your example you can just keep accumulating the visited nodes, so your state space will be now the space of tuples of nodes from your initial space.