Re: Random walks

(Sorry for calling you Roger. :-) )

On Sat, Oct 4, 2008 at 3:41 PM, Michael Rogers <m.rogers-kecf2yCh/[email protected]>wrote:

> Oskar Sandberg wrote:
> > One can weigh it back so that the limit is uniform over the vertices,
> > but all the ways I know of doing it hurt the mixing time also. I would
> > probably want to simulate different methods to see whether such just not
> > terminating at high degree vertices is better than weighting the walk.
>
> I came across a paper yesterday which seems to achieve what we want - it
> selects nodes uniformly at random using short walks. I haven't finished
> reading it yet though, so there may be caveats. The key idea is to
> accept the next step of the walk, from x to y, with probability
> min(deg(x)/deg(y),1); otherwise the walk remains at x for another step:


That is the Metropolis-Hastings chain. I was going to mention that, but I
don't want to sound like a one trick pony suggesting MH as the solution to
everything.

I'm not sure it makes much sense to use one MH chain inside another, though.
We are already doing one "accept if r < min(1, ... )" step, so an option is
to multiply the above accept probability (deg(x)/deg(y)) into that one when
choosing whether or not accept the change.

// oskar

_______________________________________________
Tech mailing list
[email protected]
http://emu.freenetproject.org/cgi-bin/mailman/listinfo/tech