Here is the scenario:

I am iteratively seeking a goal state by selecting from one of a set of sets of options. The set of sets defines the possible routes to the goal state, and each inner set defines the probability I will succeed, and what the failure penalties and probabilities are. A failure costs me a variable amount of score, which is also a given.

My objective is not only to achieve the goal state, but to do so with minimum score.

For example, say I can select from two groups:

In group 1, I have a 25% chance of success. However, I have a 50% chance of failing and adding 5 to my score, and a 25% chance of failing and adding 10 to my score.

In group 2, I have a 50% chance of success. However, I have a 10% chance of failing and adding 5 to my score, a 30% chance of failing and adding 15 to my score, and a 10% chance of failing and adding 25 to my score.

If I wish to succeed while minimizing my score, which of these two groups should I repeatedly select from?

I'm looking for a general solution to this problem, where there may be an arbitrary number of groups, and each group has an arbitrary number of outcomes. As in the example, for each group, their relative probabilities of success and failure are known, along with the points added for failing.

I think I want to optimize for "mean score for success" in the group in order to minimize my overall score. However, I'm a bit confused because it seems to me that if the distribution of possible final scores is flat enough, I may be better off accepting a higher mean score from my selected group.

  • $\begingroup$ Your final score is a random variable. As such, you need to optimize something to do with the distribution of the random variable. Do you seek to minimize expected score, or some other quantity? $\endgroup$ – Glen_b -Reinstate Monica Feb 24 '13 at 2:08
  • $\begingroup$ @Glen_b, I'll take any advice on the best axis to optimize on. I think minimizing expected score is probably good, but I'll admit I don't know for certain that's the best that can be done. $\endgroup$ – agent86 Feb 24 '13 at 3:22
  • $\begingroup$ "Best" is really a matter of what you want to optimize. $\endgroup$ – Glen_b -Reinstate Monica Feb 24 '13 at 3:39
  • $\begingroup$ @Glen_b, I understand that. "Lowest final score" is really what I wish to optimize. As you've noted, however, that's not really something I can pick. Therefore, I'm searching for a secondary characteristic that gets me as close to that as possible. $\endgroup$ – agent86 Feb 24 '13 at 12:42

If we're talking minimize expected score, you are in effect comparing a multiple of the means of two geometric distributions.

In each case you keep failing until you succeed, with constant probability of success, and the number of rounds you fail before you succeed determines the expected score.


For group 1, when you fail, you add on average $\frac{0.5\times 5+0.25\times 10}{0.5+0.25}=\frac{20}{3}$ to the score.

For group 2, when you fail, you add on average $\frac{0.1\times 5+0.3\times 15+0.1\times 25}{0.1+0.3+0.1}=15$ to the score.

For group 1, on average you fail $\frac{1-p_1}{p_1} = \frac{.75}{.25} = 3$ times before you succeed.

For group 2, on average you fail $\frac{1-p_2}{p_2} = \frac{.5}{.5} = 1$ times before you succeed.

So your expected score at success for group 1 is 20.

Your expected score at success for group 2 is 15.

Similar calculations can be done for other setups.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.