Does this algorithm guarantee equaprobable outcomes?

  • Context: Undergrad 
  • Thread starter Thread starter Bipolarity
  • Start date Start date
  • Tags Tags
    Algorithm
Click For Summary
SUMMARY

The algorithm discussed does not guarantee equaprobable outcomes when selecting a final number from a list, as the last number retains a 50% probability of being chosen. Each preceding number has a diminishing probability based on coin flips, leading to unequal chances of selection. To achieve equaprobability, a more effective method is to generate a random index k between 1 and N, where N is the total number of elements in the list, and select the kth number directly. This approach eliminates the bias introduced by the coin flip mechanism.

PREREQUISITES
  • Understanding of basic probability theory
  • Familiarity with random number generation techniques
  • Knowledge of algorithm design principles
  • Experience with programming concepts for implementing algorithms
NEXT STEPS
  • Research random number generation algorithms in programming languages
  • Explore the concept of equiprobability in statistical sampling
  • Learn about algorithm optimization techniques for selection problems
  • Investigate alternative methods for random selection, such as reservoir sampling
USEFUL FOR

Mathematicians, computer scientists, and software developers interested in probability theory, algorithm design, and random selection methods.

Bipolarity
Messages
773
Reaction score
2
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
 
Physics news on Phys.org
No, the numbers are not equiprobable. The last number has a 50 % probability.
 
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:
Bipolarity said:
Ah I see, I suppose then that each number has half the probability of its successor?

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

Bipolarity said:
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.
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.
 
Coin flips aren't equiprobable , are they ?

ETA: never mind, I see the thread already :P
 

Similar threads

Undergrad The Actual Sleeping beauty Problem
  • · Replies 45 ·
2
Replies
45
Views
6K
Graduate Probability of Outcomes in Merge Shuffle
  • · Replies 1 ·
Replies
1
Views
2K
Undergrad Probability Modeling for Coin Flips
  • · Replies 5 ·
Replies
5
Views
2K
MHB Algorithm for Ordering Odds & Evens in Linked List L
  • · Replies 2 ·
Replies
2
Views
2K
Python Algorithm Optimization [Python]
  • · Replies 2 ·
Replies
2
Views
2K
Python Shifting an array one postion to the left -- Non Function Vs Function
  • · Replies 17 ·
Replies
17
Views
3K
Studying Skipping Chapters in Stewart’s Calculus? (Pearson's Edexcel IAL Background)
  • · Replies 2 ·
Replies
2
Views
774
Assistance needed writing a C program
  • · Replies 7 ·
Replies
7
Views
2K
Undergrad How Can You Calculate the Probability of Winning with an Unfair Coin?
  • · Replies 2 ·
Replies
2
Views
4K
Undergrad A Sequence T based on the Rule of Three
  • · Replies 15 ·
Replies
15
Views
2K