I have a list and want to select a random item from the list.
An algorithm which is said to be random:
When you see the first item in the list, you set it as the selected item.
When you see the second item, you pick a random integer in the range [1,2]. If it's 1, then the new item becomes the selected item. Otherwise you skip that item.
For each item you see, you increase the count, and with probability 1/count, you select it. So at the 101st item, you pick a random integer in the range [1,101]. If it's 100, that item is the new selected node.
Is it really uniformly random?
My thoughts are:
As the number of nodes increases, the probability for them being selected decreases, so the best chance of selection is for items 1, 2, 3, ..., not for 20, 21, ..., 101.
Each node will not have equal probability of being selected.
Please clarify, as I have trouble understanding this.