Why is it 1/(1-q)? I think it should be (1-q). For example, if q is 1 (which means the probability of termination is 100%, this should yield 0 rather than Infinity)
ak-47
Maybe it's in the denominator because it's a weight? Like if a path has a very high chance of being terminated in the calculation, we should count it really highly if it isn't terminated.
mchoquet
@PandaX: ak-47 is correct. We terminate before building a path of length i with probability q_i, so in order to count for the fact that these paths sometimes aren't counted they must be over-weighted to compensate.
The 'of length 1' is definitely a typo :)
PandaX
@mchoquet Oh, I see....but are the extra '('s in the equation typo too?
lucida
@PandaX I don't think they are. I think you can think of the q_i's as "probability of going from point i-1 to i" independent of what happened earlier in the path. Therefore the probability of going from point 0 to point i must be the product of probability of going from 0 to 1 times probability of going from 1 to 2 times probability of going from 2 to 3 ... up till i. This is true assuming probabilities of traveling from one point in the path to the next is independent of the number of previous points reached or which previous points were reached.
It should be 'of length i'
Why is it 1/(1-q)? I think it should be (1-q). For example, if q is 1 (which means the probability of termination is 100%, this should yield 0 rather than Infinity)
Maybe it's in the denominator because it's a weight? Like if a path has a very high chance of being terminated in the calculation, we should count it really highly if it isn't terminated.
@PandaX: ak-47 is correct. We terminate before building a path of length i with probability q_i, so in order to count for the fact that these paths sometimes aren't counted they must be over-weighted to compensate.
The 'of length 1' is definitely a typo :)
@mchoquet Oh, I see....but are the extra '('s in the equation typo too?
@PandaX I don't think they are. I think you can think of the q_i's as "probability of going from point i-1 to i" independent of what happened earlier in the path. Therefore the probability of going from point 0 to point i must be the product of probability of going from 0 to 1 times probability of going from 1 to 2 times probability of going from 2 to 3 ... up till i. This is true assuming probabilities of traveling from one point in the path to the next is independent of the number of previous points reached or which previous points were reached.