Odds algorithm: Difference between revisions

Revision as of 22:31, 23 February 2009

Revision as of 00:29, 16 March 2009

Line 1:

The '''odds-algorithm''' is a mathematical method to compute optimal

strategies for a class of problems which belong to the ___domain of [[optimal stopping]]. Its solution determines the '''odds-strategy''', and the importance of the

odds-strategy lies in its optimality, as explained below.

The odds-algorithm applies to a class of problems called '''last-success'''- problems. Formally the objective is to maximize the probability of identifying in a

sequence of sequentially observed independent events a last specific event. This identification must be done on-line, that is, at the time of observation. No recall on preceding observations is permitted. Usually a specific

event is defined by the decision maker as an event which is of true interest to her/him in the view of "stopping"

Line 15:

1. Suppose a car is advertised for sale (best offer). n people respond and ask to see the car. They all insist

that they would need the immediate decision whether their offer is accepted or not. Define an offer ''interesting'', coded '''1''' say, if it is better than all preceding offers, and coded '''0''' otherwise. The offers will form a random sequence of 0's and 1's. Only 1's are of interest to the seller, and with each 1 he/she may fear that there will be no further 1's. It follows from the definition that the very last 1 is the highest offer. Maximizing the probability of selling on the last 1 therefore means maximizing the probability of selling '''best.''' .

2. A physician, using a special treatment, may use the code 1

for a successful treatment, 0 otherwise. Treating a sequence of n patients with the same treatment

he/she wants to minimize unnecessary sufferings, and, at the same time, obtain '''all ''' successes in the sequence of patients.

Stopping on the last 1 in such a random sequence of 0's and 1's means to realize this objective. Since

the physician has no prophetical power, his/her objective translates into the goal of finding a strategy maximizing the probability

Line 53:

== Odds-Strategy==

The odds-strategy is the rule to observe the events one after the other and to stop

on the first interesting event from index '''s''' onwards (if any), where '''s''' is the stopping threshold of output a).

The importance of the odds-strategy, and hence of the odds-algorithm, lies in the following Odds-Theorem.

Line 60:

The Odds-theorem states that

# The odds-strategy is '''optimal''', that is, it maximizes the probability of stopping on the last 1.

# The win probability of the odds-strategy equals <math>\,w= Q_s R_s </math>

# If <math>\, R_s \ge \,1 </math>, the win probability <math>\, w</math> is always at least <math> \,1/e = 0.378\dots</math>, and this lower bound is '''best possible.'''.

==Features of the odds-algorithm==

The odds-algorithm computes the optimal '''strategy''' and the optimal '''optimal win probability''' at the same time. Also, the number of operations of the odds-algorithm is (sub)linear in n. Hence no quicker algorithm can possibly

exist for all sequences, so that the odds-algorithm is, at the same time, [[optimal]] as an algorithm.