|
|
|
|
|
|
|
if it is too far below what can be attained, it will not be a useful criterion. However, we will see here that such loss rates can be approached quite closely (arbitrarily closely as N increases) by feasible plans, thus verifying L*(N)'susefulness. |
|
|
|
|
|
|
|
|
The source of the difficulty lies in the expression for n*, which was obtained on the assumption that the n* trials were allocated to x(2)(N).However there is no realizable plan (sequential algorithm) which can ''foresee" in all cases which of the two random variables will be x(2)(N)at the end of N trials. No matter what the plan t, there will be some observational sequences for which it allocates n > n* trials to a random variable x (on the assumption that x will be x(1)(N))only to have x turn out to be x(2)(N)after N trials. (For example, the observational sequence may be such that at the end of 2n* trials thas allocated n* trials to each random variable. t must then decide where to allocate the next trial even though each random variable has a positive probability of being x(2)(N).) For these sequences the loss rate will perforce exceed the optimum. Hence L*(N)is not attainable by any realizable tthere will always be payoff sequences which lead t to allocate too many trials to x(2)(N). |
|
|
|
|
|
|
|
|
There is, however, a realizable plan t(~)for which the expected loss per trial L(t(~), N)quickly approaches L*(N),i.e., |
|
|
|
|
|
|
|
|
t(~) proceeds by initially allocating n* trials to each random variable (in any order) and then allocates the remaining N - 2n* trials to the random variable with the highest observed payoff rate at the end of the 2n* trials. It is important to note that n* is not recalculated for t(~); it is the value determined above. |
|
|
|
|
|
|
|
|
COROLLARY 5.2: Given N trials, t(~)'s expected loss L(t(~), N) approaches the optimum L*(N); i.e., L(t(~), N)~ L*(N). |
|
|
|
|
|
|
|
|
Proof: The expected loss per trial L(t(~), N) for t(~) is determined by applying the earlier discussion of sources of loss to the present case. |
|
|
|
|
|
|
|
|
where q is the same function as before, but here the probability of error is irrevocably determined after 2n* trials. That is |
|
|
|
|
|
