On Mon, May 01, 2017 at 05:03:17AM +0000, Jack Stouffer via Digitalmars-d wrote: > On Monday, 1 May 2017 at 04:15:35 UTC, H. S. Teoh wrote: > > 2) "Turtle walk": > > I'd just like to point out that this algorithm doesn't satisfy > > > such that elements that satisfy P(x) have equal probability of being > > chosen > > as the first element found in A will be chosen, and then each > subsequent element has a decreasing probability of replacing the first > element of P = 1/nSatisfy.
Actually, this is exactly why it *does* satisfy the requirement. If there is exactly 1 element that satisfies P(x), then the probability of it being picked is 1. If there are 2 elements, the first element is picked with probability 1 initially, but the 2nd element has a 1/2 chance of replacing it, meaning the overall probability distribution is 1/2 and 1/2. If there are 3 elements, then by the time the 2nd element is processed, the first 2 elements are equally likely to be currently chosen (with probability 1/2 for each); when the 3rd element is found, it has 1/3 chance of replacing the previous choice, meaning there is a 2/3 chance the previous choice prevails. In that case, the 2/3 chance is equally distributed between the first two elements (they were picked with 1/2 and 1/2 probability), so the effective probability is 1/3 each after the 3rd element is processed. In general, by the time you process the n'th element, the previous elements would have had been picked with 1/(n-1) chance each, and the n'th element would be picked with 1/n chance, meaning there is a (n-1)/n chance the previous choice prevails. That (n-1)/n chance is equally distributed among the previous (n-1) elements, so effectively they are picked with 1/n chance each. The key here is that the probability that the n'th element is *not* picked is exactly (n-1)/n, which, by inductive hypothesis, must be evenly distributed among the previous (n-1) candidates, thereby making their *eventual* probability of remaining as the chosen element exactly 1/n. T -- Two wrongs don't make a right; but three rights do make a left...