# Does this algorithm guarantee equaprobable outcomes?

1. Oct 20, 2015

### Bipolarity

Suppose you have a list of numbers, say ${1, 7, 9, 4, 5, 6}$.
You store the first number, and then iterate through this list.
For each number in the list, you flip a coin. If it is heads, you swap that element in the list with the number you stored. If tails, you do nothing. Either way, you move on to the next number in the list.

When you finish traversing the list, the resulting number is the number you stored. I am curious if all numbers in the list are equaprobably to be the final stored number, and if this is indeed the case, how might one prove this?

Thanks!

BiP

2. Oct 20, 2015

### Orodruin

Staff Emeritus
No, the numbers are not equiprobable. The last number has a 50 % probability.

3. Oct 20, 2015

### Bipolarity

Ah I see, I suppose then that each number has half the probability of its successor?

Also, do you think there might be a way for me to tweak this so that the numbers are indeed equaprobable? This is for an application I'm trying to build.

BiP

Last edited: Oct 20, 2015
4. Oct 20, 2015

### Orodruin

Staff Emeritus
Yes, apart from the first number which has the same.

Yes, but the normal thing to do would be to simply generate a random number k between 1 and N, where N is the number of numbers you have and then select the kth number.

5. Oct 31, 2015

### Isaacsname

Coin flips aren't equiprobable , are they ?