Optimal Stopping in an Urn

An urn contains N objects, labelled with the integers 1, ⋯, N. One object is removed at a time, without replacement. If after n draws the largest number which has been observed is mₙ, and the process is terminated, we receive a payoff f(n, mₙ). For payoff functions f in a certain class, the optimal time to stop is with draw τf = inf 0: mₙ - n jₙ\ where the jₙ are computable from a simple algorithm, which permits also exact computation of the value Vf = E(τf, mτf)\. We also study the behavior of Vf when N is large in special cases.