Random Walk

[wicky786]

hi everyone.....can any one please briefly explain how random walk works if i want to move from one node to another?

[mathematic]

I'm not sure what you mean by "how random walk works". A discrete random walk (which is what you seem to be asking about) consists of a series of steps by a particle, starting someplace. Each node has a set of neighboring nodes (the number depends on the dimension - for one-d, it is two; for higher dimensions it depends on the problem definition). In any case, the choice of the next node depends on some probability. One-d example: p is the prob of moving to the right, q is the probability of moving to the left. p+q = 1 (ignoring possibility of not moving). Also p and q could depend on the current position and could also change with the step count.

[khaled]

hi everyone.....can any one please briefly explain how random walk works if i want to move from one node to another?

 

In general, Random Walk is an algorithm that progress stochastically ...

 

First, the stochastic part can be modeled either by using a statistical distribution over a PRNG if it's linked to a real-system, otherwise you use PRNG directly ...

 

Second, how you model progress in your system, using the stochastic resource ...

 

Third, how you constraint your random walks in your system ...

 

Finally, you make tests, and analysis ...

 

The most simple example of random walks is random walking in the coordinate system, you simply have this

recursive function: [math]X_i = X_{i-1} + Random(X) \; , \;\; Y_i = Y_{i-1} + Random(Y)[/math]

 

Now since you mentioned, "if i want to move from one node to another", you might want to know how to use Random Walks in a Linear Search,

given a problem [math]P = \langle \; S, \; F, \;\; f_i \; \rangle[/math] where [math]S[/math] is the state-space (a graph which vertices are states) of the problem P,

[math]F[/math] is the set of final-states (solutions of the problem), and [math]f_i[/math] is a function over state i (node i) where [math]S_i \in S[/math] known

as the expansion function, [math]f_i = G[/math] such that there is an edge from state [math]S_i[/math] to [math]S_j[/math], [math]\forall S_j \in G[/math].

 

In linear search, you only keep 1 node, you search path is linear .. and so to make a Random Walk in a Linear Search, you can use the following algorithm,

 

 

Transition Algorithm:

___________________________

Input: Node i

Output: Node j

 

1. Use Expansion Function to Obtain Neighbor States: [math]G \leftarrow f_i[/math]

 

2. Obtain a Random number using a PRNG: [math]r \leftarrow Random() \;\;\; {\bf mod} \;\;\; |G|[/math], where [math]|G|[/math] is number of elements in G

 

3. Return a Randomly chosen neighbor state: [math]G_r[/math]

___________________________

 

 

good luck,

Edited September 15, 2011 by khaled