Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Does this algorithm guarantee equaprobable outcomes?

  1. Oct 20, 2015 #1
    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. jcsd
  3. Oct 20, 2015 #2

    Orodruin

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    No, the numbers are not equiprobable. The last number has a 50 % probability.
     
  4. Oct 20, 2015 #3
    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
  5. Oct 20, 2015 #4

    Orodruin

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    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.
     
  6. Oct 31, 2015 #5
    Coin flips aren't equiprobable , are they ?

    ETA: never mind, I see the thread already :P
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Does this algorithm guarantee equaprobable outcomes?
Loading...