Confusion about an algorithm making a choice between two options, with probabilities.

Question

I am totally puzzled at grasping the meaning of "we move to B with probability P1 OR we move to C with probability P2" in the following scenario.

A,B,C are points in a 64-dimensional space. Reading an algorithm in a paper, and the step is:

 We are at point A and we have to move to one of it nearest neighbours B and C  
       we move to B with probability P1 OR we move to C with probability P2

The given info about probabilities is:

 P1 = X*exp[-distance_between_A_and_B/E]
 P2 = X*exp[-distance_between_A_and_C/E]

where 
X is a design parameter chosen to make P1+P2=1
E is another design parameter chosen by authors at 10^6
distances are (squared euclidean distance)/64.

Thanks for reading my silly question!

Answer 1

I'll work through an example, which might help make it more clear.

$A = (1, 2, 3,\ldots, 63, 64)$

$B = (2, 4, 6,\ldots,126, 128)$

$C = (3, 6, 9,\ldots,189,192)$

Euclidean $\overline{AB} = \sqrt{(1-2)^2 + (2-4)^2 + (3-6)^2 + \ldots + (63 - 126)^2 + (64 - 128)^2} = \sqrt{89440}$

Euclidean $\overline{AC} = \sqrt{(1-3)^2 + (2-6)^2 + (3-9)^2 + \ldots + (63 - 189)^2 + (64 - 192)^2} = \sqrt{357760}$

Distance used in probability = Euclidean distance squared / 64

$$\overline{AB} = \frac{\sqrt{89440}^2}{64} = 1397.5$$

$$\overline{AC} = \frac{\sqrt{357760}^2}{64} = 5590$$

$$P1 = X\cdot e^{\frac{-1397.5}{10^6}} = X\cdot e^{-0.0013975} \approx 0.9986X$$

$$P2 = X\cdot e^{\frac{-5590}{10^6}} = X\cdot e^{-0.00559} \approx 0.9944X$$

I'm going to be rounding here, so the answer might be slightly off. But the idea of how it works carries through.

Now to solve for $X$, $X(P1+P2) = 1$

$X(0.9986+0.9944) = 1$

$1.993X = 1$

$X = 0.5018$

$P1 = 0.5018\cdot0.9986 \approx 0.501$

$P2 = 0.5018\cdot0.9944 \approx 0.499$

So my example ended up having probabilities that are only very slightly different. Anyway, now you have to pick P1 50.1% of the time and P2 49.9% of the time. Since it sounds like you're doing this through some sort of programming language, you would now generate a random number from 0 to 1. It would look like this.

RandomNumber = GenerateRandomNumberFromZeroToOne() if(RandomNumber <= P1) go to B else go to C

Sorry if you only needed that last bit, but I figured I'd go through a whole example for completeness.

What you posted in the comment results in you going to the more likely location every time, when what you want is a chance to go to each.