In decision theory, the odds algorithm (or Bruss algorithm) is a mathematical method for computing optimal strategies for a class of problems that belong to the domain of optimal stopping problems. Their solution follows from 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 in these problems is to maximize the probability of identifying in a sequence of sequentially observed independent events the last event satisfying a specific criterion (a "specific event"). This identification must be done at the time of observation. No revisiting of preceding observations is permitted. Usually, a specific event is defined by the decision maker as an event that is of true interest in the view of "stopping" to take a well-defined action. Such problems are encountered in several situations.
Examples Two different situations exemplify the interest in maximizing the probability to stop on a last specific event.
Suppose a car is advertised for sale to the highest bidder (best "offer"). Let n {\displaystyle n} potential buyers respond and ask to see the car. Each insists upon an immediate decision from the seller to accept the bid, or not. Define a bid as interesting, and coded 1 if it is better than all preceding bids, and coded 0 otherwise. The bids will form a random sequence of 0s and 1s. Only 1s interest the seller, who may fear that each successive 1 might be the last. It follows from the definition that the very last 1 is the highest bid. Maximizing the probability of selling on the last 1 therefore means maximizing the probability of selling best. A physician, using a special treatment, may use the code 1 for a successful treatment, 0 otherwise. The physician treats a sequence of n {\displaystyle n} patients the same way, and wants to minimize any suffering, and to treat every responsive patient in the sequence. Stopping on the last 1 in such a random sequence of 0s and 1s would achieve this objective. Since the physician is no prophet, the objective is to maximize the probability of stopping on the last 1. (See Compassionate use.)
Definitions Consider a sequence of n {\displaystyle n} independent events. Associate with this sequence another sequence of independent events I 1 , I 2 , … , I n {\displaystyle I_{1},\,I_{2},\,\dots ,\,I_{n}} with values 1 or 0. Here I k = 1 {\displaystyle \,I_{k}=1} , called a success, stands for the event that the kth observation is interesting (as defined by the decision maker), and I k = 0 {\displaystyle \,I_{k}=0} for non-interesting. These random variables I 1 , I 2 , … , I n {\displaystyle I_{1},\,I_{2},\,\dots ,\,I_{n}} are observed sequentially and the goal is to correctly select the last success when it is observed. Let p k = P ( I k = 1 ) {\displaystyle \,p_{k}=P(\,I_{k}\,=1)} be the probability that the kth event is interesting. Further let
q k = 1 − p k {\displaystyle \,q_{k}=\,1-p_{k}} and r k = p k / q k {\displaystyle \,r_{k}=p_{k}/q_{k}} . Note that r k {\displaystyle \,r_{k}} represents the odds of the kth event turning out to be interesting, explaining the name of the odds algorithm.
Algorithmic procedure The odds algorithm sums up the odds in reverse order
r n + r n − 1 + r n − 2 + ⋯ , {\displaystyle r_{n}+r_{n-1}+r_{n-2}\,+\cdots ,\,}
until this sum reaches or exceeds the value 1 for the first time. If this happens at index s, it saves s and the corresponding sum
R s = r n + r n − 1 + r n − 2 + ⋯ + r s . {\displaystyle R_{s}=\,r_{n}+r_{n-1}+r_{n-2}+\cdots +r_{s}.\,}
If the sum of the odds does not reach 1, it sets s = 1. At the same time it computes
… excerpt ends here. Continue reading the full article.
