背景画像の取り込み

Introduction

Formulation and Notations

Markov Potential The best choice Problem

Random number of objects

The best choice problem for random number of objects

with a refusal probability

M Horiguchi^{1} M Yasuda^{2}

1Kanagawa University

2Chiba University

July 2009, APS at Cornell

背景画像の取り込み

Introduction

Formulation and Notations

Markov Potential The best choice Problem Random number of objects

Abstract:

The best choice problem by Markov Potential and Differential equation method. Here we dare to try a classical analysis to obtain its optimal value for the problem on Markov processes.

(1) Optimaility equation(Non-linear Differentila equation) with random number object.

(2) Infinitesimal approach(scaling limit).

(3) In generally case, it is hard to solve analitically (Lambert W-function).

背景画像の取り込み

Introduction

Formulation and Notations

Markov Potential The best choice Problem Random number of objects

Abstract:

The best choice problem by Markov Potential and Differential equation method. Here we dare to try a classical analysis to obtain its optimal value for the problem on Markov processes.

(1) Optimaility equation(Non-linear Differentila equation) with random number object.

(2) Infinitesimal approach(scaling limit).

(3) In generally case, it is hard to solve analitically (Lambert W-function).

背景画像の取り込み

Introduction

Formulation and Notations

Markov Potential The best choice Problem Random number of objects

Abstract:

The best choice problem by Markov Potential and Differential equation method. Here we dare to try a classical analysis to obtain its optimal value for the problem on Markov processes.

(1) Optimaility equation(Non-linear Differentila equation) with random number object.

(2) Infinitesimal approach(scaling limit).

(3) In generally case, it is hard to solve analitically (Lambert W-function).

背景画像の取り込み

Introduction

Formulation and Notations

Markov Potential The best choice Problem Random number of objects

• Markov Decision Processes

• One-Look-Ahead Policy

• Markov Potential Theory

• Infinitesimal Analysis(Scaling limit)

• Variations from the classical problem Random Number object, Refusal probability, Zero-sum Game version, etc.

背景画像の取り込み

Introduction

Formulation and Notations

Markov Potential The best choice Problem Random number of objects

• Chow/Robbins/Siegmund(1971), Siryaev(1973), Dynkin/Yushkevitch(1969): monotone stopping problem, the martingale theory, the potential theory,

• Ross(1983); One-Look ahead policy, the optimality principle in the mathematical programming,

• Ferguson(2006), Bruss(2003), Tamaki(2002): the sum-the-odds theorem.

背景画像の取り込み

Introduction

Formulation and Notations

Markov Potential The best choice Problem

Random number of objects

The last thing one knows when writing a book is what to put first. Blaise Pascal(1623-1662) from J.Havil ”Gamma” exploring euler’s constant with a foreword by Freeman Dyson

背景画像の取り込み

Introduction

Formulation and Notations

Markov Potential The best choice Problem

Random number of objects

Let x_{n}, n = 0, 1, 2, ⋯be a Markov Chain with a transition probability P = P(i, j), i, j ∈ S over a state space S in R^{1}.

v(i) = sup_{τ<∞} v(i, τ) = sup_{τ<∞} E [ r(x_{τ}) − ∑_{n=0}^{τ} c(x_{n}) | x_{0} = i]

背景画像の取り込み

Introduction

Formulation and Notations

Markov Potential The best choice Problem Random number of objects

The relation between Markov potential theory and Dynamic Programming or Markov decision processes is well known. The optimality equation* is reduced as follows.

v(i) = max{r(i), Pv(i) − c(i)}, i ∈ S.

Consider the set of states for which stopping immediately is at least as gppd as stopping after exactly one more period. Denote this set by

B = {i ∈ S | r(i) ≥ Pr(i) − c(i)}

where Pr(i) = ∑ _{j∈S} P(i, j)r(j).

背景画像の取り込み

Introduction

Formulation and Notations

Markov Potential The best choice Problem Random number of objects

The policy, defined by hitting time of this set B, is called a One-stage Loog Ahead(abridged as OLA) policy, refer to Ross(1983). It is sufficient that the OLA policy is optimal if B is closed and eventually hits to the set. That the set is closed means if

P(i, j) = 0 for i ∈ B, j ∈ \overline{B}

where \overline{B} denotes the complement of the set B.

背景画像の取り込み

Introduction

Formulation and Notations

Markov Potential The best choice Problem Random number of objects

Markov stopping theory as the excessive function, the martingale theory and so on. However the general framework does not cover for specific solution in the exploit structure or interesting features. The aim of this note is to obtain the explicit optimal value associated with OLA policy and various problems in the asymptotic form.

背景画像の取り込み

Introduction

Formulation and Notations

Markov Potential The best choice Problem Random number of objects

Firstly the motivated case for the classical secreraly choise problem and then for the variation of the case with the refusal probability. Let P_{A} denote the restriction to a subset A of S for the transition probability P, that is,

P_{A}(i, j) = P(i, j)1_{A}(i)

where the indicator of A is

1_{A}(i) = \{ \begin{matrix}1 & (i ∈ A) \\ 0 & (i ∉ A) \end{matrix}

背景画像の取り込み

Introduction

Formulation and Notations

Markov Potential The best choice Problem

Random number of objects

A potential N of P for a function f:

Nf(i) = lim_{n} [{I + P + P^{2} + ⋯+ P^{k}}f] (i) i ∈ S.

Assume that

lim_{k} [(P\overline{B})^{k}r] (i) = 0

[N\overline{B}(P_{B}r − c)] (i) < ∞ for i ∉ B.

背景画像の取り込み

Introduction

Formulation and Notations

Markov Potential The best choice Problem

Random number of objects

Then

(i) the OLA policy τ_{B} is optimal, (ii) the optimal value v(i), i ∈ S is given by

Introduction Formulation and Notations Markov Potential The best choice Problem Random number of objects  Classical Problem Problem with a refusal probability  _{背景画像の取り込み}

v(i) \begin{matrix}= r(i) + N(Pr − r − c)^{+} (i) \\ = \{ \begin{matrix}r(i) & on & B \\ N\overline{B}(P_{B}r − c)(i) & on & \overline{B} \end{matrix} \end{matrix} The secretary problem is an optimal stopping problem based on relative ranks for objects for objects arriving in a random fashion. The objective is to find the stopping rule that maximizes the probability of stopping at the best object among the sequence. The formulation of the problem as Markov processes is given by Dynkin/Yushkevitch(1969).

The state space is S = {1, 2, 3, ⋯, n} and the reward, its win of probability is r(i) = i/n, i ∈ S. The transition probability is

P(i, j) = \frac{i}{j(j − 1)} ,

on 1 ≤ i < j ≤ n, and = 0, otherwise . The optimal value v(i) satisfies, for i = 1, 2, ⋯, n − 1,,

v(i) = max\{ \frac{i}{n}, ∑_{j=i+1}^{n} \frac{i}{j(j − 1)} v(j)\} ,

v(n) = 1.

Introduction Formulation and Notations Markov Potential The best choice Problem Random number of objects  Classical Problem Problem with a refusal probability  _{背景画像の取り込み}

Taking a scale limit of \frac{i}{n} → x as i, n → ∞, it becomes that v(x) = max\{ x, x ∫_{x}^{1} \frac{v(y)}{y^{2}} dy\} , x ∈ S = [0, 1], v(1) = 1.

The solution is well known as

v(x) = \{ \begin{matrix}e^{−1} & on & [0, e^{−1} ], \\ x & on & [e^{−1} , 1]. \end{matrix}

By extending the reward r(x) in general, that is, v(x) = max\{r(x), x ∫_{x}^{1} \frac{v(y)}{y^{2}} dy\}, x ∈ S = [0, 1], v(1) = 1.

It is also the OLA policy is still optimal if the following assumption holds.

Assumption: The function

h(x) = r(x) − x ∫_{x}^{1} \frac{r(y)}{y^{2}} dy

is finite on [0, 1] for a given r(x) and it changes its sign from − to + only once as x increases 0 to 1. So there exists a unique solution α of the equation h(x) = 0, that is,

α = inf{x; h(x) ≥ 0}.

Theorem: Using this solution α, the assumption implies

v(x) = \{ \begin{matrix}r(α) & on & [0, α], \\ r(x) & on & [α, 1]. \end{matrix}

Because of using Markov potential, it is calculated as

P_{B}r(x) = r(α)\frac{x}{α},

(P\overline{B})^{n}P_{B}r(x) = r(α)\frac{x}{α} log^{n} ( \frac{α}{x}) /n!

and

N\overline{B}P_{B}r(x) = r(α)

directly. Here B = [0, α].

The basic idea based on the infinitesimal operator of Markov processes. It is equivalent to,

−x\frac{d v(x)}{dx} = (r(x) − v(x))^{+} , x ∈ [0, 1], v(1) = 1.

This method is derived by Mucci(1973).

A variant for the classical best choice problem is considered by Smith(1975) inducing a refusal probability. A given p (0 < p < 1) means the probability of not refused case and the quality 1 − p is a probability of the refusal. When there occues no refusal(1 − p = 0), that is, the usual standard problem corresponds to p = 1.

The asymptotic form of the transition probability is given as

P(x, dy) = \{ \begin{matrix}\frac{p}{y}( \frac{x}{y})^{p} dy, & 0 < x < y < 1, \\ 0, & otherwise. \end{matrix} Similarly before Assumption: The function

h_{p}(x) = r(x) − p ∫_{x}^{1} \frac{r(y)}{y} (x/y)^{p} dy

is finite on [0, 1] for a given r(x) and it changes its sign from − to + only once as x increases 0 to 1. Its unique solution is denoted by α_{p} of the equation h_{p}(x) = 0, i.e.,

α_{p} = inf{x; h_{p}(x) ≥ 0}.

Theorem: Using this solution α_{p}, the assumption implies that

v(x) = \{ \begin{matrix}r(α_{p}) & on & [0, α_{p}], \\ r(x) & on & [α_{p}, 1]. \end{matrix}

It is also known the technique of using a differential equation by Mucci(1973). Let

V(x) = p ∫_{x}^{1} \frac{r(y)}{y} (x/y)^{p} dy, x ∈ [0, 1]

which means a contditional optimal value. This satisfies

−x\frac{dV(x)}{dx} = p(r(x) − V(x))^{+} ,  x ∈ [0, 1],

V(1) = 0.

The optimal value at the begining

v^{∗} = V(0) = r(α_{p}).

Confirming that the case of r(x) = x, the equation h_{p}(x) = 0 solves

x = α_{p} = p^{1/(1−p)}

which consist with the result by Smith(1975).

Introduction Formulation and Notations Markov Potential The best choice Problem Random number of objects  Formulation for random number of objects Random number of objects with refusal  _{背景画像の取り込み}

The discussion on the stopping choice problem with a random number of objects is firstly by Presman/Sonin(1972). Then Rasmussen/Robbins(1975), Tamaki(1979), Irle(1980), Petruccelli(1983) etc. If we restrict ourselves that the support of distribution for a number of objects is bounded, the technique of the previous scaling limit could be applied. This assumption links to the technique of the scaling limit. It should be noted that Presman/Sonin discussed the number of objects is Poisson distribution, so we could not apply this technique in that case. The next is a fundamental assumption of the discussion in here.

Assumption: A random number of objects N is bounded and let

n = inf{k ≥ 1; P(N > k) = 0}.

By using the notation of p_{i} = P(N = i) and π_{i} = P(N ≥ i) = ∑ _{k≥i} p_{i}, the transition probability matrix for this case is as follows:

p(i, j) = \frac{i π_{j}}{j(j − 1) π_{i}} , 1 ≤ i < j ≤ n,
p(i, n) = ∑_{k=i+1}^{n} \frac{i p_{k}}{k π_{i}} , 1 ≤ i < n, p(n, n) = 1,
r(i) = ∑_{k=i}^{n} \frac{i p_{k}}{k π_{i}} ,  c(i) = 0, ∀i.

If we denote the distribution by Φ(x), x ∈ [0, 1] of its random number for objects, and taking the scale limit of k, n → ∞ with k/n = x, then v(i) → V(x) and p_{k} = P(N = i) → dΦ(x), π_{k} = ∑ _{k≥i} p_{i} → 1 − Φ(x), so

p_{k}/π_{k} → dΦ(x)/(1 − Φ(x)),

r(k + 1) = ∑_{k=i}^{n} \frac{i p_{k}}{k π_{i}} = \frac{i}{π_{i}} ∑_{k=i}^{n} \frac{p_{k}}{k}

→ R(x) = \frac{x}{1 − Φ(x)} ∫_{x}^{1} y^{−1} dΦ(y).

Introduction Formulation and Notations Markov Potential The best choice Problem Random number of objects  Formulation for random number of objects Random number of objects with refusal  _{背景画像の取り込み}

The resulting the differential equation is given as

−x dV(x) + x \frac{V(x)}{1 − Φ(x)} dΦ(x)

= (R(x) − V(x))^{+} dx, x ∈ [0, 1] V(1) = 0

where

R(x) = \frac{x}{1 − Φ(x)} ∫_{x}^{1} y^{−1} dΦ(y).

The details refer to Yasuda(1984).

Assumption: We assume that dΦ satisfies the conditions:

1 (1 − Φ(x))^{−1} ∫_{x}^{1} y^{−1} dΦ(y) → 1 as x → 1,

2 x ∫_{x}^{1} y^{−1} dΦ(y) → 0 as x → 0.

This assumtion implies that R(x) → 0 (x → 0) and → 1(x → 1). In the usual non-random case, R(x) = x, these conditions are

satisfied since \frac{1}{1 − Φ(x)} ∫_{x}^{1} y^{−1} dΦ(y) = 1 for x ≠ 1.

Example: Example of a random number N: Uniformly distributed case on a partial interval

{n − m, n − m + 1, ⋯, n − 1, n} of {1, 2, ⋯, n}

Letting θ = m/n is fixed for n, m → ∞,

Φ(x) = \{ \begin{matrix}0, & (0 < x < 1 − θ), \\ (x − 1 + θ)/θ, & (1 − θ < x < 1) \end{matrix}

case  α: threshold v^{∗}:optimal value

1 − θ ≥ e^{−2}  \sqrt{1 − θ} e^{−1} −\frac{\sqrt{1 − θ}}{θ} log(1 − θ)e^{−1}

1 − θ ≤ e^{−2}  e^{−2}  2e^{−2} /θ

If θ → 1 it tend to 2e^{−2} as discussed in Presman/Sonin(1972) etc. Alternatively, if θ → 0, this reduces to the non-random classical problem and it tend to e^{−1} as is well known. However it is interesting that the threshold α = e^{−2} does not depent on θ in case of 1 − θ ≈ 0, that is, case of the ambiguity is being in spread.

Here we would like to impose a refusal probability for the model. Instead of V(x) in the optimality equation consider

dv(x) = dV(x) − \frac{V(x)}{1 − Φ(x)} dΦ(x). Then, it holds that

v(x) = max\{ R(x), \frac{x}{1 − Φ(x)} ∫_{x}^{1}(1 − Φ(y))y^{−2} v(y) dy\} The optimality equation of stopping problem:

v(x) = max{R(x), Pv(x)}, 0 ≤ x ≤ 1

have a modification with a refusal probability p(x), 0 ≤ x ≤ 1 becomes

v(x) = max{p(x) R(x) + (1 − p(x)) Pv(x), Pv(x)}.

By letting Pv(x) = \frac{x}{1 − Φ(x)} ∫_{x}^{1}(1 − Φ(y))y^{−2} v(y) dy, q(x) = exp ( ∫_{x}^{1} y^{−1} (1 − p(x)) dy) and h(x) = ∫_{x}^{1} y^{−1} dΦ(y), Assumption: Assume that

H_{p}(x) = h(x) − q(x) ∫_{x}^{1} \frac{h(y) p(y)}{y q(y)} dy

changes its sign once from − to + as x increase.

Theorem: The solution is given as the value

α_{p}^{∗} = \{ \begin{matrix}inf\{x; H_{p}(x) ≥ 0\} \\ 1 if empty \end{matrix}

determine its threshold policy and so the optimal value v(0+).

However in order to display the above assertion or explicit form, it is not easy for us. Even the simplest case of

p(x) = p (0 < p < 1)

and

Φ(x) = x (0 ≤ x ≤ 1),

it needs the discussion on Lambert W function.