6
$\begingroup$

given a discrete distribution of hitting time probabilities, is it possible to generate a random walk that generates this hitting time distribution? More specifically I am interested in generating a finite graph so that a simple random generates the given hitting time distribution.

I guess it is not possible to generate the exact distribution, but maybe approximate it?

Any hints on papers etc. are welcome!

Thanks, Chris

Improve this question
$\endgroup$
8
  • $\begingroup$ By "simple random", do you mean a random walk on a graph where each neighbor is visited uniformly at random? $\endgroup$
    – mhum
    Commented Feb 17, 2011 at 16:25
  • $\begingroup$ Consider the simplest possible case: you have just two nodes. There are very many discrete probability distributions but very few graphs... $\endgroup$
    – Jukka Suomela
    Commented Feb 17, 2011 at 20:45
  • $\begingroup$ @Jukka But there's a two dimensional parameter space to work with (the transitions from 1-2 and 2-1) $\endgroup$
    – Suresh Venkat
    Commented Feb 17, 2011 at 21:03
  • $\begingroup$ @Suresh: But if you can have arbitrary transition probabilities (i.e., you do not choose a neighbour uniformly at random), isn't the problem trivial (in particular, if you can have self-loops)? $\endgroup$
    – Jukka Suomela
    Commented Feb 17, 2011 at 21:08
  • 3
    $\begingroup$ I think neither the input nor the output of this problem is quite clear yet. $\endgroup$
    – mhum
    Commented Feb 17, 2011 at 21:43

1 Answer 1

Reset to default
6
$\begingroup$

There are lots of different kinds of random walks (discrete vs continuous, weighted vs constant, classical vs quantum) so the exact approach will differ some what in each case, but I will attempt to outline a fairly general approach here.

Usually the evolution of that system will be given by $A^t$ for some matrix $A$, where $t$ is time. The exact nature of $A$ will depend on the type of random walk you have in mind, but in any case, we expect the system to be in a state $A^t v$ after time $t$, where $v$ denotes the starting state. The question then becomes: given a set of hitting times $\{t_i\}$, corresponding states $\{u_i\}$, and hitting overlaps $\{p_i\}$, can we find some matrix $A$ which satisfies $u_i^\dagger A^{t_i} v = p_i$ for all $i$? Certainly this will not always be the case (since we could have conflicts where orthogonal states are required at the same time), so I assume you are really interested in how to find $A$ when there does exist an $A$ satisfying these relations.

EDIT: My previous answer was incorrect beyond this point, so I have replaced that portion.

I am not 100% sure of the most efficient way to find $A$. You have a system of equations in the enteries of $A$, and these can obviously be solved numerically using, for example, Buchberger's algorithm. However, this approach is not computationally efficient, and there may exist a more straight forward approach.

If you simply want find a transition matrix which approximates this, then you can use any number of optimization strategies, though these too may be inefficient.

Note, here I have assumed a very general model which should be true for all random walks, but it makes it hard to say anything concrete about how hard long it will take to numerically find a solution. If you have more information (i.e. is this a discrete time walk? Is it classical (I assume so)? Are weighted transitions probabilities allowed or do they have to be constant? Is this associates with some lattice (1d, 2d, or an arbitrary graph)?) Then you can possibly do much better. In the worst case, though, this problem seems to be NP-hard (since you get an integer programming problem if you restrict the transition probabilities to be multiples of some constant).

Improve this answer
$\endgroup$
8
  • $\begingroup$ @joe: thanks a lot for the explanation. Could you point me to some elementary book/paper that describes $u_i^\dagger A^{t_i} v = p_i$ in detail? For the basic papers on random walks I have read this has never come around. Thanks! $\endgroup$
    – user3881
    Commented Feb 18, 2011 at 6:28
  • $\begingroup$ @Chris: I'm sorry, I have just noticed that the second half of my answer is wrong (servers me right for trying to answer a question after being at the pub!). I'll try to correct it in the next few hours. $\endgroup$
    – Joe Fitzsimons
    Commented Feb 18, 2011 at 12:10
  • $\begingroup$ @Chris: I'm afraid I don't have any good references for you. The equation comes from the following: You can represent the location of the walker by a vector which is zeros everywhere except for one entry which is 1. So, for the walk to have a probability $p_i$ of being at location $u_i$, then we require the overlap between the state of the system $v(t)$ and $u_i$ be equal to $p_i$, leading to the equation $u_i^\dagger v(t) = p_i$ (you can replace this with an inequality if you prefer for your particular setup). But $v(t) = A^t v$ where $v$ is the initial state and $A$ is the transition matrix. $\endgroup$
    – Joe Fitzsimons
    Commented Feb 18, 2011 at 13:22
  • $\begingroup$ @Chris: Do you have a lot of data for each vertex? If so, rewiting the constraints as $u_i^\dagger W6 $\endgroup$
    – Joe Fitzsimons
    Commented Feb 18, 2011 at 13:31
  • $\begingroup$ @Joe: actually I don't have data for vertices directly. I have a behavior of a physical system. What I have of the physical system is the PDF of return times (actually I was wrong in stating hitting times in the question, but I guess the approach would not differ much). To simulate the system directly is complex. So my idea was to find a graph so that the random walk on this graph generates the same return times. This way simulation would be easy. $\endgroup$
    – user3881
    Commented Feb 18, 2011 at 13:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.