Derek Jones from The Shape of Code
In the following code, how often will the variable
b be incremented, compared to
If we assume that the variables
y have values drawn from the same distribution, then the condition
(x < y) will be true 50% of the time (ignoring the situation where both values are equal), i.e.,
b will be incremented half as often as
if (x < y)
if (x < z)
If the value of
z is drawn from the same distribution as
y, how often will
c be incremented compared to
(x < y) reduces the possible values that
x can take, which means that in the comparison
(x < z), the value of
x is no longer drawn from the same distribution as
Since we are assuming that
y are drawn from the same distribution, there is a 50% chance that
(z < y).
If we assume that
(z < y), then the values of
z are drawn from the same distribution, and in this case there is a 50% change that
(x < z) is true.
Combining these two cases, we deduce that, given the statement
a++; is executed, there is a 25% probability that the statement
c++; is executed.
If the condition
(x < z) is replaced by
(x > z), the expected probability remains unchanged.
If the values of
z are not drawn from the same distribution, things get complicated.
Let's assume that the probability of particular values of
y occurring are and , respectively. The constants and are needed to ensure that both probabilities sum to one; the exponents and control the distribution of values. What is the probability that
(x < y) is true?
Probability theory tells us that , where: is the probability distribution function for (in this case: ), and the the cumulative probability distribution for (in this case: ).
Doing the maths gives the probability of
(x < y) being true as: .
(x < z) case can be similarly derived, and combining everything is just a matter of getting the algebra right; it is left as an exercise to the reader :-)