Re: Select a subset of paths

From: Robert Israel (israel_at_math.ubc.ca)
Date: 03/23/05 

Date: 23 Mar 2005 22:35:37 GMT

In article <1111559908.326958.35210@z14g2000cwz.googlegroups.com>,
 <vipin.v.deep@gmail.com> wrote:
>Hello:
>
>In a graph, one node is labeled as "start", and some of the nodes as
>"end". Among all possible paths from start to any of the end node, I
>have to select only a few fration of paths randomly (say 20%). Other
>than brute force, how can I do this.

20% is a lot. You might as well enumerate all the paths and then
randomly choose 20% of them. But for a smaller sample of "random"
paths, you could repeatedly "grow" paths at random, i.e. start at
"start" and at each stage choose a new node that is a neighbour of
the last node and isn't already part of the path, giving equal
probabilities to each of those. When you get to an end node you
can stop. If you get stuck (with no, start again.
Of course this will result in a different probability distribution
on the space of paths than the first method (which gives all paths
equal probability).

Robert Israel israel@math.ubc.ca
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia Vancouver, BC, Canada

Relevant Pages

  • Re: Birthday Problem
    ... > array - reads the array and tries to detect an ... > exact match The problem is that the match is ... unless you were specifically told to use brute force. ... consider a naive way to do it by hand: check the probability if the ...
    (comp.lang.cpp)
  • Re: Collision in SHA-0
    ... >>All hash algorithms produce collisions. ... >>brute force attack, it is perfectly ok for any hash algorithm to ... >>some other kind of attack (other than brute force), ... I suppose the concept of 'probability' plays a role here. ...
    (sci.crypt)
  • Re: what is the probability of getting at least a doubble six in 24 throws?
    ... > Does this mean throwing two dice 24 times and getting ... but we can do this with a state transition matrix easily: ... the the probability of the last state after 24 throws. ... Doing this by brute force gives ...
    (sci.math)
  • RE: calculating probabilty of x number of successes with multiple
    ... I meant AVERAGE instead of HARMEAN for the ballpark calculation. ... You could enumerate them and sum the probability of each. ... the probability that the first 10 trials are successes and the rest ...
    (microsoft.public.excel.worksheet.functions)
  • RE: calculating probabilty of x number of successes with multiple tria
    ... You could enumerate them and sum the probability of each. ... the probability that the first 10 trials are successes and the rest ...
    (microsoft.public.excel.worksheet.functions)