Algorithm with more than 100% probability
I need an algorithm (in Java, but the theory should be pretty general) for some sort of probability ... thing. I don't even know what to call it, so I haven't had any luck with Google.
To describe it a little better, I have a task that needs to be done X times when a function is called. Sometimes there is only 1 in 10 chances of this, which means that (roughly) every tenth time this function is called the task that will actually be done - easy enough to do with random (). Sometimes it will be 2 in 10 or maybe even 10 in 10. Still easy enough, just conditional, even if it's not always "X in 10"
The problem is that it might have a better 1 in 1. It might be 15 in 10 - half the time it works once, otherwise it works twice. Or 10 to 5, where it runs twice (approximately) every time it is called. As you can see, this has now ventured into a simple inequality test.
So I'm looking for some kind of algorithm that will randomly return the execution count based on how often (1 in 10, 200%, 0.75, whatever the format) something needs to happen. If anyone can provide any conclusions on this - for example maybe an actual search term - that would be very helpful!
EDIT: Unsurprisingly I can't find many results, everyone is as confusing as I am!
First of all, no real "maximum" value. Not formally defined. If the algorithm can extract this from the resulting probability value, then that's great.
It also definitely needs to be random, which makes it inherently imperfect. If you unfold the coin 10 times, you may well end up with 8 heads, although in theory it should be absolutely! And this is good. In fact, that's the point.
I could tell you why I need it ... but that would be a violation of good object-oriented modularity practice :) Outside parties only need to know the interface; it takes a value (maybe a float, "0.75" looks like it will work best) and returns an int. If you call it 100 times, with a probability of 1 in 5, the sum of its return values should be up to 20.
source to share
If the number of executions for a given probability X should be limited floor(X)
and ceil(X)
(and never floor(X)-1
or less or ceil(X)+1
or more): (so 1.5 is 50% 1 and 50% 2 and 0.7 is 70% 1 and 30% 0)
int runCount = (int)probability;
if (randomGen.nextDouble() < probability - runCount)
runCount++;
EDIT: Compressed as suggested by DigitalMan.
EDIT 2: Admittedly, this solution focuses on "15 at 10 - half the time when it runs once and the rest is twice" in the question, and can be considered a substitute for "about" at "10 at 5 where it runs twice ( approximately) every time it is “asked” in the question “exactly.” The limitations are somewhat unclear.
source to share
From what you said, you can choose the number of repetitions using just about any discrete probability distribution that has a mean X
.
I would recommend the Poisson distribution [*]
with the mean X
, as it simulates the number of events in any given window, where events are uniformly distributed independently over a longer time frame. Therefore, it is "scalable" [**]
: you can divide X
by 2, run your operation twice as often, and you still have essentially the same event pattern.
If you don't really care about allocation, you just need the correct rate of events, and in the opposite extreme, you can use a completely non-random algorithm. Store the cumulative carry value starting at 0. Then, at each iteration, add X
carry to the carry value, return the integer part, and move the fractional part. Of course, this makes 8/10 heads impossible.
[*]
Unfortunately, the name is not related to the distribution of the amount of fish that the angler catches per unit of time.
[**]
Also not related to fish.
source to share
Well ... it might not really be a probability.
As far as I can see, you want to be able to run your task multiple times (0 ... n) on every function call, keeping the randomness in those calls.
The easiest way I can see is to use 2 randomizations:
- Using random (), select whether you are doing your task or not (let's say pick a random int between 0 and 100 and if that triggers some N-task it needs to be run). By changing these Ns, you can adjust your probabilities;
- If in the first step you decide to run your problem, run random () again. Let's say a random int between 100 and 500. Suppose it returned the number R. Then R% 100 will be the number of times you have to do your task.
Another case is random () 0 to 700 (for example) and using random ()% 100 to determine the number of times you should run your task. If you want to change your "probabilities" for other values, just use your own function instead of "%".
source to share
Let's reformulate the problem a bit to clarify what's going on. At each step, you want to complete the task multiple times. You describe the number of times to complete a problem with a probability distribution. Your probability distribution is chosen so that it performs the correct expected number of tasks.
When you describe performing a task 1 time in 10, your distribution is that you have a 90% chance of completing the task 0 times and a 10% chance of completing it once. This gives the expected value of one tenth of the number of steps. Summarize this in your "more than 100% of the time" by saying that you want the expected value for the number of times you are equal, for example 1.5 times the number of steps. Choose a probability distribution that gives this expectation value, whether it's half the time when you do the task once and half the time twice, or 3/4 of the time when you don't do the task and 1/4 of the time when you do it 6 time. You usually have more than one probability distribution that works.
source to share