I guess it's called Standard Deviation?

[tjankus]

Hey all,

this isn't a question for a school, but a practical one, hopefully you can help me with.

If I have an average of "1 in an average 100, on average".
Is it the same as just 1/100?

Or do we have to put into account the probability that this exact "100" *isn't avarage* (because there's a chance we're on a streak, or smt like that)... ?

Not sure if I made my question clear, please ask me to clarify if needed.

 

[tjankus]

Basically if we have 500 red balls and 500 green balls.
Let's say, there are 10 "lucky balls" among them in total. But 8 "lucky" balls are red, and only 2 "lucky" are green.

What is the optimal way to pick balls?

To start you only know that there are 500/500 green/red, and there are 10 "lucky" in total. And that the distribution might be uneven, but you don't know how or if at all (might be 5/5).

Is it reasonable to alternate colors at first, and then continue with the one you find a "lucky" ball first? (because at that pont this color seems like more probable to have more lucky balls, right?) Or what is the most optimal way to do this?

 

[Romsek]

What you want to do is compute the probability of picking a lucky ball given you pick green, or red, at each turn, and pick
from the barrel that yields the higher probability.

At the start P[lucky|red] = 8/500, P[lucky|green] = 2/500
Thus we would pick from the red barrel.
Let's say we didn't get a lucky ball.
Now P[lucky|red] = 8/499, P[lucky|green] = 2/500
Thus we again pick red.
Now this time lets say we did pick a lucky ball. Then for the next pick we have
P[lucky|red] = 7/498, P[lucky|green]=2/500

As you can see we're going to end up picking from the red barrel until P[lucky|red] < 2/500.
At that point we would switch to the green barrel.

Without having an actual data sequence to work with it's a bit difficult to go any further with the demo but the
idea remains. Calculate the conditional probabilities at each step and choose from the barrel yielding the larger one.

 

[tjankus]

As you can see we're going to end up picking from the red barrel until P[lucky|red] < 2/500.

Very nice. Thank you.

At the start P[lucky|red] = 8/500, P[lucky|green] = 2/500

What if we don't know that? We only know there might be uneven distribution, but we have no proof, untill we actually go through all the balls.
(in reality there still are 8 lucky reds and only 2 lucky greens, but we don't know that in advance, might be the other way around).

Thus we would pick from the red barrel.

But if we don't have this information, we pick randomly first, until we hit the first "lucky", I suppose?

How do we continue then?

 

[Romsek]

If you have no idea about the distribution of lucky balls then there really isn't any optimal strategy. You may as well just flip a coin.

 

[tjankus]

If you have no idea about the distribution of lucky balls then there really isn't any optimal strategy. You may as well just flip a coin.

What if we don't know "until we know"?

Let me paraphrase the problem.

Let's say we have 500 red candies and 500 green candies. We want to make as many people satisfied with a candy, as possible; while giving out as little candies, as possible.

The probablity of people liking red candies, more than green ones, is .5. They are different, we just don't know which will they prefer, if any at all (maybe they dont like these candies at all, or they like both equally).

We go out to give 1000 people a free candy and ask if they like it.

SOLUTION:
we start giving any candy, randomly.
if they seem to like reds more (the first response was "i like it" for a red candy) - we give more reds, and v.v. Or else we continue alternating/random if they don't like any of these, until someone says they like a particular kind of candy?.

Right?

Sounds right to me, but then if we started with an assumption of P=.5 why would that ever change?

 

[Romsek]

If you know ahead of time that the number of lucky balls is definitely some N, then you can maintain a running
estimate of the number of red and green balls. It won't be accurate until you've sampled quite a few of them.

You can incorporate your distribution estimate into the algorithm selecting the next color choice.

Google parametric estimation if you want more details.