[OT] Algorithm question

[H. S. Teoh via Digitalmars-d]

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...