Title: The best choice problem for random number of objects with a refusal probability

Masayuki Horiguchi, Kanagawa University, Japan, horiguchi@kanagawa-u.ac.jp Masami Yasuda, yasuda@math.s.chiba-u.ac.jp Abstract: In this note, we will consider the best choice problem for random number of objects with a refusal probability. There are many papers and books on this subject from Chow/Robbibs/Siegmund(1971), Siryaev(1973) downward. These problems has been close relations with the martingale theory, the potential theory, the optimality principle in the mathematical programming. And now it is derived the optimal rule by using the sum-the-odds theorem. Refer to Ferguson(2006), Bruss(2003), Tamaki(2001), Hsiau/Yang(2000) etc. It would be preferes to call it the odds-theorem rather than the secretary problem or the best choice nowdays. Here we adapt a classical analysis to obtain its optimal value for the problem on Markov processes.

Firstly the formulation of stopping problem for Markov processes are given and its optimal equation of the value are designated. Since the secretary problem has a special transition probability, we show the optimal value is calculated as One-Look ahead policy or monotone stopping problem. Then it is treated asymptotically and solve the value in the explicitly form by a differential equation. Some equivalence relation is shown between the decision-theoretic form of the optimal equation and the transition probability with refusal.

In the last, by a translation from the case of random number of objects to the standard form of optimal stopping problem, we could obtain the optimal value in the cited case of title. Also a variation for the selection is considered.

1 Formulation and Notations 2 Markov Potential 3 The best choice Problem

3.1 Classical Problem 3.2 Problem with a refusal probability 3.3 Random number of objects

4 Random number of objects with refusal References

[1] aa.

[2] R.E. Bellman, Dynamic Programming, Princeton Univ. Press, NJ, 1957.