r/AskComputerScience • u/TheEyebal • 2d ago
How to program weighted random system
I want to make a program where you are controlling the outcomes. For an example with a coin flipping game, I want exactly 4 Heads and 1 Tail, but I want their positions to be random.
I do not want to use the random algorithms that library I want to build my own.
Right now I am learning probability from Youtube and might look at khan academy and coursera, but how can I implement this into programming I do not want to just take courses or watch videos
How do I go about that?
EDIT: I am doing this because I want to start build gambling algorithms and I am starting with a simple project like coin flips
1
u/Mishtle 2d ago
So do you want to write the function that produces a random number from "nothing"?
Or the code that uses those random numbers to make decisions or produce different outcomes?
1
u/TheEyebal 2d ago
I want to start build gambling algorithms and I am starting with a simple project like coin flip
2
u/Mishtle 2d ago
You could just use a built-in (pseudo)random number. It will usually give a fractional number between 0 and 1, with all values equally likely. You can very easily use these to make things happen with some probability 0 ≤ p ≤ 1. Simply generate a random value r and do the thing if r ≤ p.
For a fair coin, you could output heads if r ≤ 0.5, and tails otherwise. If you want the coin to be biased, like land on heads 51% of the time, you'd instead output heads if r ≤ 0.51.
If you wanted to choose among n options, like the index of an array, you could multiply r by n and round down. This gives you a whole number between 0 and n-1, with each value having probability 1/n. If you wanted to make one option more likely you could create multiple copies of it in the list, increasing n and giving the duplicated . You could alternatively divide the range [0,1] into n bins, with bin sizes reflecting the probability you want to assign to each bin.
If you want to randomize an array, you can pick one of the n indices to be the first, one of the n-1 remaining indices to be the second, and so on. Again, you can do this in biased ways.
If you want to randomly traverse a tree or graph structure, you can randomly choose, in a possibly biased way, a branch or edge at each vertex using the above approaches.
You can use this to do more advanced things, such as sampling from arbitrary distributions. You can generate a value that is distributed according to a standard normal distribution, for example. You might learn about methods of doing that in more advanced probability courses.
There are also usually functions in math or standard libraries that will do at least some of that.
Or do you want to implement that underlying function spitting out that value between 0 and 1, the pseudorandom number generator?
1
u/HobartTasmania 2d ago edited 2d ago
For starters, don't bother re-inventing the wheel as it already exists, so in data compression like say Morse code and Huffman Coding then more frequent symbols have shorter bit sequences and infrequent ones have longer ones.
A more generic and mathematical method where probabilities are exactly known like say for every letter in the novel War and Peace, then you assign probabilities for each letter because you would count every one beforehand, and you can then compress the novel using arithmetic coding and you end up with a number between 0 and 1 with a very large amount of digits. To decompress this you simply reverse this process.
So in your case you just start with a large numeric number concatenated from repeated calls to the random number generator, you first place the decimal digit to the left of it, then you assign probabilities of 80% to tails and 20% to heads and then start decompressing it, this will then give you your desired 4 to 1 ratio, as long as you use a good random number generator.
So to simulate perfect dice rolls you would assign probabilities of 1/6 to each number and decompress, in the case of a biased die where you want the number 6 to come up with twice the normal probably you would assign 1/7 each to the first 5 numbers and 2/7 to the 6 number and decompress again.
There's probably no other algorithm which would be simpler than using this method.
1
u/Level-Challenge2759 2d ago
For exactly 4 H and 1 T in random positions, generate a list like [H,H,H,H,T] and randomly shuffle it if you want to understand the probability side calculate how many unique arrangements exist first thats a great little project before getting into more complicated systems,,,,
1
u/donaldhobson 1d ago
Keep track of the number of heads and tails remaining.
Generate a random number r uniform between 0 and 1.
If you have 1 head and 3 tails left, then if r<1/(1+3)=1/4, output heads, otherwise, output tails.
1
u/donaldhobson 1d ago
If you are doing a coin flipping game, efficiency isn't that important. So, in python.
import random
x=["Heads"]*1+["Tails"]*5#change numbers as needed
random.shuffle(x)
print(x)
['Tails', 'Tails', 'Heads', 'Tails', 'Tails', 'Tails']
3
u/nuclear_splines Ph.D Data Science 2d ago
If you already know the set of outcomes and want to randomize the order, then that's a shuffling algorithm. You can find several algorithms for shuffling a list. One trivial one is:
You now have a randomly ordered list from a preset list of outcomes.