Mis Cosas

This shows that u = 0 minimizes Jk (x, u), for all x ≥ Sk . Now let x ∈ [Sk − n, Sk − n +1), n ∈ {1, 2, . . .}.
Using Eq. (1), we have
Jk (x, n + m) − Jk (x, n) = Jk (x + n, m) − Jk (x + n, 0) ≥ 0∀ m in {0, 1, . . .}.

(3)

However, if u < n then x + u < Sk and
Jk (x + u + 1, 0) − Jk (x + u, 0) < Jk (Sk + 1, 0) − Jk (Sk , 0) = −c.
Therefore,
Jk (x, u + 1) = Jk (x + u + 1, 0) + (u +1)c < Jk (x + u, 0) + uc = Jk (x, u)

∀ u ∈ {0, 1, . . .}, n < n. (4)

Inequalities (3) and (4) show that u = n minimizes Jk (x, u) whenever x ∈ [Sk − n, Sk − n + 1).
4.18

www

Let the statexk be defined as

 T, if the selection has already terminated
xk = 1, if the kth object observed has rank 1

0, if the kth object observed has rank < 1

The system evolves according toxk+1 =

T,
if uk = stop or xk = T
wk , if uk = continue

The cost function is given by
gk (xk , uk , wk ) =

k
N,

0,

gN (xN ) =

if xk = 1 and uk = stop
otherwise
1, if xN = 1
0,otherwise

Note that if termination is selected at stage k and xk = 1 then the probability of success is 0. Thus, if
xk = 0 it is always optimal to continue.
△
To complete the model we have todetermine P (wk | xk , uk ) = P (wk ) when the control uk = continue.
At stage k , we have already selected k objects from a sorted set. Since we know nothing else about these
objects the new elementcan, with equal probability, be in any relation with the already observed objects
aj
· · · < ai1 < · · · < ai2 < · · ·
· · · < aik · · ·
k+1

possible positions for
17

ak+1

Thus,
P (wk =1) =
△

Proposition: If k ∈ SN = {i |

1
N −1

Jk (0) =

1
,
k+1

+ ··· +

k
N

1
i

P (wk = 0) =

≤ 1}, then

1
1
+ ···+
N −1
k

Proof: For k = N − 1
JN −1 (0) = maxk
k+1

,

Jk (1) =

k
.
N

1
0 , E {wN −1 } =
N
stop continue

and µ∗ −1 (0) = continue. Also,
N
JN −1 (1) = max

N −1
N −1
, E {wN −1 } =
N
N
continue
stop

and µ∗ −1...