Odds algorithm

Odds strategy (derived from odds ) or Bruss algorithm or strategy Bruss (after the developer of the process Franz Thomas Bruss ) is a mathematical method of decision theory, which allows likely optimal "opportunity" select one of a sequence of events.

The strategy can be used if a temporal sequence of independent events is present, some of which are as " opportunities," and it is not known upon the occurrence of an opportunity, if later follows a better opportunity. An example is the situation of a used car dealer or a real estate agent who does not know if there is an offer to purchase, if later, another prospective buyer makes a better offer.

A special case for the application of the odds - strategy is the secretary problem, in which the or the best candidate / candidate should be selected. The odds strategy is much more generally applicable because it allows arbitrary definitions " interesting events ". The algorithm for calculating the strategy itself is also optimal.

Definitions

To apply the odds strategy, the reality has to be modeled mathematically. For this purpose, a sequence of events is assumed, for example, could each event be an offer to purchase. The events are numbered with the index up. Each event has a certain probability an "opportunity".

If the probability is that is the desired opportunity, then

The probability that it is not. Your name, the strategy on the quotient

The English is called odds.

Algorithm

The strategy is, from a certain index, the so-called "Stop Index" to perceive the first opportunity that is better than all previous occasions.

The stop index is determined by the odds are written backwards: ,, etc. They are summed up, and until such time as the sum is 1 reached or exceeded. We define the sum to

And one in which the value of this sum for the first time reached the value of 1 or exceed, forms the stop index.

Probability of success

The odds strategy is optimal under the criterion to select from all opportunities with the highest probability the last opportunity. In the application, it is understood as an opportunity often an event that is better than all previous events by one criterion, for example, a better deal than all previous offers. In this context, the odds - strategy selects in comparison to other strategies the best deal with the highest probability.

The probability of success for the odds - strategy, which is the probability that the last or best opportunity is used is: . This is

The sum of the odds and

The probability that, in the event in question is not an occasion.

Examples

Secretaries problem

Suppose that the used car salesman knows that an average of 16 customers are interested in a month for a car, and of course he wants to sell to that customer who offers the highest price. An event is for the used car dealer so then an "opportunity" if it is better than all previous.

The following applies to the first experience with security, so. For the second offer, if any arrival order is assumed to be equally likely, then generally applies. It follows and.

As the used car dealer has an average of 16 customers per month, is. The adjacent table shows that the stopping index is because when the sum of the backward summed odds value of 1 for the first time reaches or exceeds. Thus, the used car dealer has to wait until the seventh offer, and then accept the first one that is better than all previous.

The probability of success would have been about 39%. In other words, the used car dealer sold the car in 39 % of cases at the best price.

Generalizations

The previous example is the " secretary problem ". The solution is less interesting once the used car dealer has additional information. Here is where the advantage of the general definition of the odds - strategy. Let us take the simple example, the used car dealer know three of the last potential customer and think I know from experience that each of these three the previous record price surpasses independently with probability. If at least has the value ( or the corresponding value of at least ), so now is the odds - strategy that is optimal, at least put on a further increase in supply. Generalizations for an unknown number of potential customers, are also possible by means of an integral version ( Bruss 2000), the odds strategy.