Introduction
A lot of research concerning the optimal stopping of processes with discrete time involves generalizations or extensions of the so called secretary problem. In the classical secretary problem [8] a decision maker (DM) sequentially observes a set of N N N objects whose values are comparable according to a linear ordering. The DM is allowed to select only one object and selection can only occur at the moment when that object appears. The goal of the DM is to maximize the probability of accepting the absolute best object (of absolute rank one). The objects appear in random order. From the definition of the problem, at moment n n n the DM only observes the rank of the current object relative to the first n n n objects to appear. The sequence of absolute ranks is a random permutation of the integers from 1 to N N N . The sequence of the relative ranks of the first n n n objects is the corresponding permutation based on comparing the first n n n objects. Hence, these relative ranks form a random permutation of the integers from 1 to n n n . The DM should only consider objects that have a relative rank of 1 and given that the current object has relative rank one, the probability that it is the best of all the objects (has absolute rank one) is equal to the proportion of objects that have already appeared. Since decisions are made sequentially, it is natural to apply dynamic programming to solve such a problem [16].
Key words and phrases. Secretary problem, optimal stopping, dynamic programming, partial order, discrete time stochastic processes.
The authors acknowledge support from the NCN grant: DEC-2015/17/B/ST6/01868.
Some authors have considered analogous problems in which the DM has greater room for manoeuvre, for example the DM could return to a previously observed object, which is still available with some probability [25 , 28 ] . Some authors have considered similar problems with different objectives, for instance the DM wishes to maximize the expected value of the chosen number, or to choose one of the best k k k objects [24 , 26 ] . In other cases, the DM has a richer source of information, for example she can observe the precise values of objects from a known distribution, rather than just comparing values [21]. Game theoretic versions of the secretary problem have also been considered [18], [20].
Another direction of research considers sequential decision problems in which the DM can only compare objects according to a partial ordering and the aim of the DM is to choose one of the maximal elements. In such problems one might consider the optimal policy for specific types of partial orders (e.g. binary trees [11], [12], [17]) or efficient universal algorithms for more general partial orders [4], [6], [7], [13], [19], [23]. Similar problems can be defined by assuming that objects have multivariate attributes [9], [10].
A natural extension of the classical secretary problem is to consider two linearly ordered pools of objects of the same cardinality, equal to N N N . Thus we deal here with a partial ordering consisting of two independent linear orders. It is assumed that these 2 N 2N 2 N objects appear in random order. The DM can only accept an object at the moment of its appearance. The goal of the DM is to choose either of the two best ranked objects. This problem has turned out to be much more difficult that the original secretary problem and it seems that its full solution has been an open problem for a long time. A number of similar problems have been solved. According to one such model, the pools are interpreted as copies of each other. For example, when there are two pools of N N N objects, these objects can be interpreted as N N N sets of identical twins. In such problems, each object is comparable to all of the other objects and only its twin is seen to be equivalent. If the DM has not previously seen a copy of the current object, then she knows that a copy of that object will appear later. Hence, the DM should only ever accept the second copy of an object to appear. Such an object should also be the best of those to have appeared so far [5]. This model has been extended to problems in which there are k k k copies of each object [1]. According to another such model, there are k k k such pools of objects. First, the objects from pool one all appear in random order, before the objects from successive pools appear [14], [15]. The model considered in this paper differs from those according to which copies of objects appear, since according to the model presented here an object from one pool cannot be compared with any object from the other pool. It differs from models according to which the pools appear in sequence, since according to the model presented here the probability that the next object to appear is from a given pool equals the proportion of the objects that have not appeared so far which come from that pool. In this paper we give the form of the solution to this problem for finite N N N , a procedure to derive this solution and the asymptotic form of the solution as N → ∞ N \to\infty N → ∞ . A (perhaps surprisingly) strong result is presented defining whether an object of relative rank one should be accepted when the same number of objects of both types have been seen.
§ 2 presents the model. A procedure for deriving the optimal strategy based on dynamic programming is given in § 3 . This section also gives intuitive arguments regarding the general form of the optimal strategy. § 4 presents the concept of a one step look ahead rule (OSLAR), see [22], in the framework of the model presented. The general form of the optimal solution, a threshold rule, is derived in § 5 , which includes a (perhaps surprisingly) strong result regarding the threshold rule for all N ≥ 3 N \ge3 N ≥ 3 . The asymptotic form of the solution is presented in § 6 . Conclusions and directions for future research are presented in § 7 . A number of the proofs and lemmas are technical. For this reason they are presented in an appendix. The appendix also contains a table describing the notation used throughout the paper.
A Mathematical Description of the Model
A decision maker (DM) observes a sequence of objects of two types, such that there are N N N objects of both types. These objects appear in random order and the n n n -th object appears at moment n n n , n = 1 , 2 , … , 2 N n = 1,2,\ldots,2N n = 1 , 2 , … , 2 N . The current object can be ranked in comparison to all of the previous objects of the same type, but cannot be compared to any of the objects of the other type.
The DM can only accept one object and an object can only be accepted at the moment of its appearance. Suppose that the DM is still searching at moment n n n , she can either reject that object (and continue observing the sequence) or accept that object (and thus stop searching). The goal of the DM is to accept one of the two objects that is the absolute best of its type. Hence, we define the reward of the DM to be 1 when such an object is chosen and 0 otherwise. The absolute rank of an object is defined to be its rank in comparison to all the objects of its type (the best has absolute rank 1, the worst has absolute rank N N N ). The relative rank of an object is defined to be its rank in comparison to the objects of its type that have already appeared. It follows that the DM should only consider objects that have relative rank 1. Such objects will be referred to as candidates.
Suppose that i i i objects of type 1 and j j j objects of type 2 have appeared by moment n n n , where i + j = n i+j=n i + j = n . Let α i , j \alpha_{i,j} α i , j denote the probability that the next object is of type 1. From the assumption that the objects appear in random order, it follows that α i , j = N − i 2 N − i − j \alpha_{i,j}=\frac{N-i}{2N-i-j} α i , j = 2 N − i − j N − i , i.e. the number of remaining objects of type 1 divided by the total number of objects remaining. Given that the next object is of type 1 (2), then the probability that it has relative rank 1 is 1 i + 1 \frac{1}{i+1} i + 1 1 (1 j + 1 \frac{1}{j+1} j + 1 1 , respectively). Define a sequence of 2 N + 1 2N+1 2 N + 1 four-tuples T n = ( U n , V n , K n , R n ) T_n=(U_n,V_n,K_n,R_n) T n = ( U n , V n , K n , R n ) , such that
i: T 0 = ( 0 , 0 , 0 , 0 ) T_0=(0,0,0,0) T 0 = ( 0 , 0 , 0 , 0 ) ,
ii: P [ ( U n + 1 , V n + 1 , K n + 1 ) = ( U n + 1 , V n , 1 ) ] = α U n , V n P[(U_{n+1},V_{n+1},K_{n+1})=(U_n+1,V_n,1)]=\alpha_{U_n,V_n} P [( U n + 1 , V n + 1 , K n + 1 ) = ( U n + 1 , V n , 1 )] = α U n , V n ,
iii: P [ ( U n + 1 , V n + 1 , K n + 1 ) = ( U n , V n + 1 , 2 ) ] = 1 − α U n , V n P[(U_{n+1},V_{n+1},K_{n+1})=(U_n,V_n+1,2)]=1-\alpha_{U_n,V_n} P [( U n + 1 , V n + 1 , K n + 1 ) = ( U n , V n + 1 , 2 )] = 1 − α U n , V n .
iv: P ( R n = r ∣ U n = i , K n = 1 ) = 1 i P(R_n=r\mid U_n=i,K_n=1)=\frac{1}{i} P ( R n = r ∣ U n = i , K n = 1 ) = i 1 , r = 1 , 2 , … , i r=1,2,\ldots,i r = 1 , 2 , … , i .
v: P ( R n = r ∣ V n = j , K n = 2 ) = 1 j P(R_n=r\mid V_n=j,K_n=2)=\frac{1}{j} P ( R n = r ∣ V n = j , K n = 2 ) = j 1 , r = 1 , 2 , … , j r=1,2,\ldots,j r = 1 , 2 , … , j .
Hence, K n K_n K n denotes the type of the n n n -th object to appear, while U n U_n U n and V n V_n V n denote the number of type 1 and type 2 objects, respectively, to have appeared among the first n n n objects. Analogously, R n R_n R n denotes the relative rank of this object with respect to the objects of the same type that have already appeared. By definition U 2 N = V 2 N = N U_{2N}=V_{2N}=N U 2 N = V 2 N = N . A realization of the sequence of 4-tuples ( U n , V n , K n , R n ) (U_n,V_n,K_n,R_n) ( U n , V n , K n , R n ) , 0 ≤ n ≤ 2 N 0\leq n\leq2N 0 ≤ n ≤ 2 N , will be referred to as a trajectory of the search process.
Given U n = i U_n=i U n = i and V n = j V_n=j V n = j , the relative ranks of future objects are independent of the remaining information from the trajectory. Hence, it suffices to define the current state of the process at moment n n n to be S ( n ) = ( i , j , k ) S(n)=(i,j,k) S ( n ) = ( i , j , k ) where i = i ( n ) i=i(n) i = i ( n ) and j = j ( n ) j=j(n) j = j ( n ) are the numbers of objects that have appeared of type 1 and 2, respectively. Define k k k such that k = k ( n ) = 0 k=k(n)=0 k = k ( n ) = 0 if the current object is not the best of its type seen so far, k = k ( n ) = w k=k(n)=w k = k ( n ) = w if the current object is the best seen so far (a candidate) of type w w w , w = 1 , 2 w=1,2 w = 1 , 2 . We may assume that when the DM rejects a candidate in state ( i , j , k ) (i,j,k) ( i , j , k ) , k = 1 , 2 k=1,2 k = 1 , 2 , then the state immediately switches to ( i , j , 0 ) (i,j,0) ( i , j , 0 ) before the next object appears.
Denote by τ m \tau_m τ m the moment at which the m m m -th candidate appears, i.e. this is the m m m -th smallest value of n n n for which k ( n ) ≠ 0 k(n)\neq0 k ( n ) = 0 . Let X m = 1 X_m=1 X m = 1 when the object observed at time τ m \tau_m τ m is the best of all objects of its type, otherwise X m = 0 X_m=0 X m = 0 . Let Y m = E ( X m ∣ F τ m ) Y_m=E(X_m\mid\mathcal{F}_{\tau_m}) Y m = E ( X m ∣ F τ m ) , where F τ m \mathcal{F}_{\tau_m} F τ m represents the information given by the states observed at moments τ 1 , τ 2 , … , τ m \tau_1,\tau_2,\ldots,\tau_m τ 1 , τ 2 , … , τ m . The sequence Y m Y_m Y m is adapted to the filtration $(\mathcal{F})_m and is not affected by additional information, e.g. the relative rank of other objects that have appeared so far. Note that when S ( τ m ) = ( i , j , k ) S(\tau_m)=(i,j,k) S ( τ m ) = ( i , j , k ) , then Y m = i / N Y_m=i/N Y m = i / N if k = 1 k=1 k = 1 and Y m = j / N Y_m=j/N Y m = j / N if k = 2 k=2 k = 2 . If τ M \tau_M τ M is the time of the appearance of the final candidate, we formally define that k ( τ M + 1 ) = k ( τ M + 2 ) = ⋯ = 0 k(\tau_{M+1})=k(\tau_{M+2})=\cdots=0 k ( τ M + 1 ) = k ( τ M + 2 ) = ⋯ = 0 and Y M + 1 = Y M + 2 = ⋯ = 0 Y_{M+1}=Y_{M+2}=\cdots=0 Y M + 1 = Y M + 2 = ⋯ = 0 . Thus ( Y m ) m (Y_m)_m ( Y m ) m may be considered as a process with infinite time horizon and absorbing state 0. Based on this formulation, the DM obtains a reward of 1 by stopping at either the last decision point at which K τ m = 1 K_{\tau_m}=1 K τ m = 1 or the last decision point at which K τ m = 2 K_{\tau_m}=2 K τ m = 2 .
Derivation of the Optimal Strategy by Dynamic Programming
Dynamic programming is a well-known method of solving sequential decision problems when the total reward can be written as a linear combination of intermediate payoffs, see [2]. This approach can be used to derive the optimal reward and strategy for any particular realization of the problem considered. It will also be useful in the derivation of general results regarding the general form of the optimal strategy and its asymptotic form. Intuitively, given that j j j objects of type 2 have been seen, then a candidate of type 1 should be accepted if and only if the number of type 1 objects to have appeared is equal to or exceeds some threshold i N ∗ ( j ) i_N^*(j) i N ∗ ( j ) , i.e. a candidate should be accepted in state ( i , j , 1 ) (i,j,1) ( i , j , 1 ) if and only if i ≥ i N ∗ ( j ) i \ge i_N^*(j) i ≥ i N ∗ ( j ) . It is expected that this threshold is non-increasing in j j j . This result will be proved in § 5 . By symmetry, a candidate should be accepted in state ( i , j , 2 ) (i,j,2) ( i , j , 2 ) if and only if j ≥ i N ∗ ( i ) j \ge i_N^*(i) j ≥ i N ∗ ( i ) .
Let v i , j v_{i,j} v i , j denote the optimal probability of choosing one of the maximal elements when i i i objects of type 1 and j j j objects of type 2 have already been rejected, 0 ≤ i , j ≤ N 0 \le i,j \le N 0 ≤ i , j ≤ N . This will be called the value function. From the symmetry between the two types, v i , j = v j , i v_{i,j}=v_{j,i} v i , j = v j , i . By definition v N , N = 0 v_{N,N}=0 v N , N = 0 .
Given that the present state is ( i , j , 0 ) (i,j,0) ( i , j , 0 ) , the next observation is of type 1 with probability α i , j = N − i 2 N − i − j \alpha_{i,j}=\frac{N-i}{2N-i-j} α i , j = 2 N − i − j N − i . In this case, it will be a candidate with probability 1 i + 1 \frac{1}{i+1} i + 1 1 and should be accepted if and only if the probability of such a candidate being the best of all objects of type 1, i + 1 N \frac{i+1}{N} N i + 1 , is greater than the expected reward from future search v i + 1 , j v_{i+1,j} v i + 1 , j . Analogously, the next observation is of type 2 with probability 1 − α i , j 1-\alpha_{i,j} 1 − α i , j . In this case, it will be a candidate with probability 1 j + 1 \frac{1}{j+1} j + 1 1 and should be accepted if and only if the probability of such a candidate being the best of all objects of type 2, j + 1 N \frac{j+1}{N} N j + 1 , is greater than the expected reward from future search v i , j + 1 v_{i,j+1} v i , j + 1 . If an object does not have relative rank 1, then the DM continues searching. Hence, the recursion equation for the value function is given by
v i , j = α i , j [ i v i + 1 , j i + 1 + max { 1 N , v i + 1 , j i + 1 } ] + ( 1 − α i , j ) [ j v i , j + 1 j + 1 + max { 1 N , v i , j + 1 j + 1 } ] . (1) v_{i,j}=\alpha_{i,j}\left[\frac{i v_{i+1,j}}{i+1}+\max\left\{\frac{1}{N},\frac{v_{i+1,j}}{i+1}\right\}\right]+(1-\alpha_{i,j})\left[\frac{j v_{i,j+1}}{j+1}+\max\left\{\frac{1}{N},\frac{v_{i,j+1}}{j+1}\right\}\right]. \tag*{(1)} v i , j = α i , j [ i + 1 i v i + 1 , j + max { N 1 , i + 1 v i + 1 , j } ] + ( 1 − α i , j ) [ j + 1 j v i , j + 1 + max { N 1 , j + 1 v i , j + 1 } ] . (1)
Using this equation, the optimal strategy for a given N N N can be derived recursively. When the present state is ( i , j , 1 ) (i,j,1) ( i , j , 1 ) , the current object should be accepted if and only if i N ≥ v i , j \frac{i}{N}\ge v_{i,j} N i ≥ v i , j . Similarly, when the present state is ( i , j , 2 ) (i,j,2) ( i , j , 2 ) , the current object should be accepted if and only if j N ≥ v i , j \frac{j}{N}\ge v_{i,j} N j ≥ v i , j . Note that, by symmetry, if the current object should be accepted in state ( i , j , 1 ) (i,j,1) ( i , j , 1 ) , then the current object should be accepted in state ( j , i , 2 ) (j,i,2) ( j , i , 2 ) . Also, when i ≥ j i\ge j i ≥ j , if a candidate should be accepted in state ( i , j , 2 ) (i,j,2) ( i , j , 2 ) , then it should be accepted in state ( i , j , 1 ) (i,j,1) ( i , j , 1 ) .
Example
Consider a simple example where N = 4 N=4 N = 4 . We have v 4 , 4 = 0 v_{4,4}=0 v 4 , 4 = 0 , thus the last object to be seen should be accepted. From the state ( i , 4 , 0 ) (i,4,0) ( i , 4 , 0 ) , i ∈ { 0 , 1 , 2 , 3 } i\in\{0,1,2,3\} i ∈ { 0 , 1 , 2 , 3 } , the next object to appear must be of type 1 and applying Equation (1) , it follows that
v i , 4 = i i + 1 v i + 1 , 4 + max { 1 4 , v i + 1 , 4 i + 1 } . (2) v_{i,4}=\frac{i}{i+1}v_{i+1,4}+\max\left\{\frac{1}{4},\frac{v_{i+1,4}}{i+1}\right\}. \tag*{(2)} v i , 4 = i + 1 i v i + 1 , 4 + max { 4 1 , i + 1 v i + 1 , 4 } . (2)
This is analogous to the recursion equation for the classical secretary problem with N = 4 N=4 N = 4 . It follows that v 3 , 4 = 1 4 v_{3,4}=\frac{1}{4} v 3 , 4 = 4 1 , v 2 , 4 = 11 12 v_{2,4}=\frac{11}{12} v 2 , 4 = 12 11 and v 1 , 4 = v 0 , 4 = 11 24 v_{1,4}=v_{0,4}=\frac{11}{24} v 1 , 4 = v 0 , 4 = 24 11 . Comparing v i , j v_{i,j} v i , j and i N \frac{i}{N} N i , it can be seen that when all the objects of type 2 have been rejected, a candidate of type 1 should be accepted if and only if i ≥ i N ∗ ( 4 ) = 2 i\ge i_N^*(4)=2 i ≥ i N ∗ ( 4 ) = 2 . In general, the threshold i N ∗ ( N ) i_N^*(N) i N ∗ ( N ) will be equal to the optimal threshold in the classical secretary problem.
Comparing v i , j v_{i,j} v i , j and j N \frac{j}{N} N j , we obtain the intuitively clear fact that when the last object of type 2 to appear is a candidate, then it should always be acceptable (it is the best of all the type 2 objects with probability 1).
In a similar way, we can derive the value function and optimal decisions when j = 3 , 2 , 1 , 0 j=3,2,1,0 j = 3 , 2 , 1 , 0 and i ≤ j i\le j i ≤ j using the recursion equation
v i , j = 4 − i 8 − i − j [ i v i + 1 , j i + 1 + max { 1 4 , v i + 1 , j i + 1 } ] + 4 − j 8 − i − j [ j v i , j + 1 j + 1 + max { 1 4 , v i , j + 1 j + 1 } ] . (3) v_{i,j}=\frac{4-i}{8-i-j}\left[\frac{i v_{i+1,j}}{i+1}+\max\left\{\frac{1}{4},\frac{v_{i+1,j}}{i+1}\right\}\right]+\frac{4-j}{8-i-j}\left[\frac{j v_{i,j+1}}{j+1}+\max\left\{\frac{1}{4},\frac{v_{i,j+1}}{j+1}\right\}\right]. \tag*{(3)} v i , j = 8 − i − j 4 − i [ i + 1 i v i + 1 , j + max { 4 1 , i + 1 v i + 1 , j } ] + 8 − i − j 4 − j [ j + 1 j v i , j + 1 + max { 4 1 , j + 1 v i , j + 1 } ] . (3)
The value function and the optimal strategy for this problem are described in Table 1 . The optimal strategy for N = 4 N = 4 N = 4 can be described by the set of thresholds i 4 ∗ ( j ) = 3 i_4^*(j) = 3 i 4 ∗ ( j ) = 3 for j = 0 , 1 , 2 , 3 j = 0, 1, 2, 3 j = 0 , 1 , 2 , 3 and i 4 ∗ ( 4 ) = 2 i_4^*(4) = 2 i 4 ∗ ( 4 ) = 2 . A candidate should be rejected in state ( i , i , 1 ) (i,i,1) ( i , i , 1 ) when i ∈ { 1 , 2 } i \in\{1,2\} i ∈ { 1 , 2 } , but accepted when i ∈ { 3 , 4 } i \in\{3,4\} i ∈ { 3 , 4 } . Define i N ∗ i_N^* i N ∗ such that i N ∗ = min { i : v i , i ≤ i N } i_N^* = \min\{i : v_{i,i} \le\frac{i}{N}\} i N ∗ = min { i : v i , i ≤ N i } . Hence, i 4 ∗ = 3 i_4^* = 3 i 4 ∗ = 3 . Note that this is the unique solution of i i ∗ ( i ) = i i_i^*(i) = i i i ∗ ( i ) = i .
Table 1. Value function and optimal strategy (in brackets) for the problem with N = 4 N=4 N = 4 : 0 denotes that a candidate of type 1 should be rejected in state ( i , j , 1 ) (i,j,1) ( i , j , 1 ) , 1 denotes that such a candidate should be accepted, n.a. denotes that no such decision is applicable. The appropriate actions when a candidate of type 2 appears can be derived from the symmetry of the problem.
A program was written in the R language to derive the optimal value function and strategy for a given N N N . By inspection, for 2 ≤ N ≤ 20 2 \le N \le20 2 ≤ N ≤ 20 , i N ∗ = ⌈ N + 1 2 ⌉ i_N^* = \left\lceil\frac{N+1}{2}\right\rceil i N ∗ = ⌈ 2 N + 1 ⌉ , where ⌈ x ⌉ \lceil x\rceil ⌈ x ⌉ denotes the smallest integer that is not exceeded by x x x (see also Table 2). It seems that v 0 , 0 v_{0,0} v 0 , 0 is decreasing in N N N and for n ≥ 100 n \ge100 n ≥ 100 , v 0 , 0 ≈ 0.5 + 1 2 N v_{0,0} \approx0.5 + \frac{1}{2N} v 0 , 0 ≈ 0.5 + 2 N 1 . These results will be further explored in Sections 5 and 6.
Considering the possible trajectories of the search process when N = 4 N = 4 N = 4 , as long as the DM has not yet accepted a candidate, the process will pass into a region in which the DM should never reject the next candidate of the type that has appeared more often. For example, starting in state ( 2 , 0 , 0 ) (2,0,0) ( 2 , 0 , 0 ) or ( 2 , 1 , 0 ) (2,1,0) ( 2 , 1 , 0 ) , then the DM should never reject the next candidate of type 1 to appear. By symmetry, starting in state ( 0 , 2 , 0 ) (0,2,0) ( 0 , 2 , 0 ) or ( 1 , 2 , 0 ) (1,2,0) ( 1 , 2 , 0 ) , then the DM should never reject the next candidate of type 2 to appear. Moreover, it will eventually become optimal to always accept the next candidate to appear, regardless of its type. For example, starting in the state ( 2 , 2 , 0 ) (2,2,0) ( 2 , 2 , 0 ) , the DM should always accept the next candidate to appear. We will prove that these results hold for any N N N in Section 5.
We now give a simple result, which will be useful in deriving the general form of the optimal solution.
Lemma 1. For N ≥ 3 N \ge3 N ≥ 3 , it is always optimal to reject the first object of either type.
Proof. We can derive a lower bound on the optimal reward from the search procedure by considering the expected reward under the following strategy: ignore any object of type 2 and accept the first object of type 1 that is better than the initial object of type 1 to be seen. The probability that the second object of type 1 to be observed is better than the first is 0.5 0.5 0.5 . Given that the second object is better than the first, the probability that it is the best of all the objects of type 1 is 2 / N 2/N 2/ N . For the third object of type 1 to be accepted under such a strategy, it must be the first object to appear that is better than the first object of type 1, i.e. the second object of type 1 must be worse than the first and then the third must be better than the first two. The probability of this is 1 / 2 × 1 / 3 = 1 / 6 1/2 \times1/3 = 1/6 1/2 × 1/3 = 1/6 . Given that this is true, the probability that the third object of type 1 is the best of all the objects of type 1 is 3 / N 3/N 3/ N . Let u u u be the expected payoff from using this strategy. Using the law of total probability,
u ≥ 1 2 × 2 N + 1 6 × 3 N > 1 N . u \ge\frac{1}{2} \times\frac{2}{N} + \frac{1}{6} \times\frac{3}{N} > \frac{1}{N}. u ≥ 2 1 × N 2 + 6 1 × N 3 > N 1 .
Since the probability of the first object of type 1 being the best of all objects of class 1 is 1 / N 1/N 1/ N , it follows from the symmetry between the two types that the first object of a given type should never be accepted for N ≥ 3 N \ge3 N ≥ 3 .
On the other hand, as argued above, when the last object of a given type is a candidate, then it should always be accepted.
The One-Step Look-Ahead Rule
The concept of a one-step look-ahead rule (OSLAR) is often very useful in deriving the general form of the optimal strategy in a wide range of stopping problems. An OSLAR stops at a particular decision point τ m \tau_m τ m , if the expected reward from stopping in the current state is greater than the expected reward from waiting and stopping at the next decision point, τ m + 1 \tau_{m+1} τ m + 1 (if there is such a decision point). In general, such a rule is not necessarily optimal. However, suppose that whenever the condition for stopping according to an OSLAR is satisfied at time τ m \tau_m τ m , then it is satisfied at time τ m + 1 \tau_{m+1} τ m + 1 . In such a case, the optimal policy is an OSLAR (see Sonin [22]). In our problem, such an OSLAR would compare the expected reward from accepting a candidate that has just appeared to the expected reward from accepting the next candidate to appear (if no such candidate appears, then the reward is defined to be 0).
Table 2. Optimal value and i N † i_N^\dagger i N † for various values of N N N .
The following example shows that such an approach should be used with care in the problem we are considering. Consider a situation in which a candidate of type 1 appears when a number of objects of type 1 have already appeared, but none of type 2 have appeared. In this case, it is very likely that the next candidate to appear will be the first object of type 2 to appear. Intuitively, the expected reward from accepting the current candidate (say the m m m -th) will be greater than the expected reward from accepting the m + 1 m+1 m + 1 -th. However, in this case it is likely that the expected reward from waiting for the m + 2 m+2 m + 2 -th candidate to appear will be greater than the expected reward from accepting the m + 1 m+1 m + 1 -th to appear. Hence, the optimal strategy is not an OSLAR.
Let w i , j w_{i,j} w i , j be the expected reward obtained when i i i objects of type 1 and j j j objects of type 2 have been already rejected and the DM accepts the next candidate to appear. It should be noted that whenever the next candidate should be accepted, then w i , j = v i , j w_{i,j}=v_{i,j} w i , j = v i , j . By symmetry, w j , i = w i , j w_{j,i}=w_{i,j} w j , i = w i , j . In addition, using dynamic programming, as in Equation (1) , we obtain
w i , j = α i , j [ 1 N + i w i + 1 , j i + 1 ] + ( 1 − α i , j ) [ 1 N + j w i , j + 1 j + 1 ] = 1 N + α i , j i w i + 1 , j i + 1 + ( 1 − α i , j ) j w i , j + 1 j + 1 . (4) \begin{aligned}
w_{i,j}&=\alpha_{i,j}\left[\frac{1}{N}+\frac{i w_{i+1,j}}{i+1}\right]+(1-\alpha_{i,j})\left[\frac{1}{N}+\frac{j w_{i,j+1}}{j+1}\right]\\
&=\frac{1}{N}+\frac{\alpha_{i,j}i w_{i+1,j}}{i+1}+\frac{(1-\alpha_{i,j})j w_{i,j+1}}{j+1}. \tag*{(4)}
\end{aligned} w i , j = α i , j [ N 1 + i + 1 i w i + 1 , j ] + ( 1 − α i , j ) [ N 1 + j + 1 j w i , j + 1 ] = N 1 + i + 1 α i , j i w i + 1 , j + j + 1 ( 1 − α i , j ) j w i , j + 1 . (4)
Note that by definition w 0 , 0 = 1 N w_{0,0}=\frac{1}{N} w 0 , 0 = N 1 , since the first object to appear is always a candidate and is the best of its type with probability 1 N \frac{1}{N} N 1 . Similarly, w N , 0 = w 0 , N = 1 N w_{N,0}=w_{0,N}=\frac{1}{N} w N , 0 = w 0 , N = N 1 . Define i N † i_N^\dagger i N † such that i N † = min { i : w i , i ≤ i N } i_N^\dagger=\min\{i:w_{i,i}\le\frac{i}{N}\} i N † = min { i : w i , i ≤ N i } .
Lemma 2. For N ≥ 3 N\ge3 N ≥ 3 , w 1 , 1 > 1 N w_{1,1}>\frac{1}{N} w 1 , 1 > N 1 , i.e. i N † ≥ 2 i_N^\dagger\ge2 i N † ≥ 2 .
Proof. Assume that the DM starts in state ( 1 , 1 , 0 ) (1,1,0) ( 1 , 1 , 0 ) , i.e. one object of both types has appeared and the second object to appear has just been rejected. The next object to appear will be a candidate with probability 0.5 0.5 0.5 . If it is a candidate, it will be the best of its type with probability 2 N \frac{2}{N} N 2 . Suppose that the next object to appear is not a candidate. Without loss of generality, we may assume that this object was of type 1. The fourth object to appear will be type 1 with probability N − 2 2 N − 3 \frac{N-2}{2N-3} 2 N − 3 N − 2 . Given it is of type 1, it will be a candidate with probability 1 / 3 1/3 1/3 and given it is a candidate, it will be the best of type 1 with probability 3 N \frac{3}{N} N 3 . The fourth object to appear will be type 2 with probability N − 1 2 N − 3 \frac{N-1}{2N-3} 2 N − 3 N − 1 . Given it is of type 2, it will be a candidate with probability 1 / 2 1/2 1/2 and given it is a candidate, it will be the best of type 2 with probability 2 N \frac{2}{N} N 2 . Using the law of total probability, it follows that
w 1 , 1 ≥ 1 2 × 2 N + 1 2 [ N − 2 2 N − 3 × 1 3 × 3 N + N − 1 2 N − 3 × 1 2 × 2 N ] > 1 N . w_{1,1} \ge\frac{1}{2}\times\frac{2}{N}+\frac{1}{2}\left[\frac{N-2}{2N-3}\times\frac{1}{3}\times\frac{3}{N}+\frac{N-1}{2N-3}\times\frac{1}{2}\times\frac{2}{N}\right]>\frac{1}{N}. w 1 , 1 ≥ 2 1 × N 2 + 2 1 [ 2 N − 3 N − 2 × 3 1 × N 3 + 2 N − 3 N − 1 × 2 1 × N 2 ] > N 1 .
We can find a direct expression for w i , j w_{i,j} w i , j by considering the probability that the next object to appear is the absolute best of its type. We may assume that i + j = τ m i+j=\tau_m i + j = τ m , i.e. the current moment is a decision point, as the distribution of the state at which the next decision is made depends only on i i i and j j j . Let Y m Y_m Y m be the expected reward from stopping at the m m m -th decision point. Assume that the state at the m m m -th decision point is ( i , j , k ) (i,j,k) ( i , j , k ) . From an extension of the law of total probability for any two events A 1 A_1 A 1 , A 2 A_2 A 2 such that P ( A k ) > 0 P(A_k)>0 P ( A k ) > 0 for k = 1 , 2 k=1,2 k = 1 , 2
w i , j = E ( Y m + 1 ) = E ( Y m + 1 ∣ A 1 ) P ( A 1 ) + E ( Y m + 1 ∣ A 2 ) P ( A 2 ) + E ( Y m + 1 ∣ A 1 c ∩ A 2 c ) P ( A 1 c ∩ A 2 c ) − E ( Y m + 1 ∣ A 1 ∩ A 2 ) P ( A 1 ∩ A 2 ) . (5) \begin{aligned}
w_{i,j}=E(Y_{m+1})={}&E(Y_{m+1}\mid A_1)P(A_1)+E(Y_{m+1}\mid A_2)P(A_2)\\
&+E(Y_{m+1}\mid A_1^c\cap A_2^c)P(A_1^c\cap A_2^c)-E(Y_{m+1}\mid A_1\cap A_2)P(A_1\cap A_2). \tag*{(5)}
\end{aligned} w i , j = E ( Y m + 1 ) = E ( Y m + 1 ∣ A 1 ) P ( A 1 ) + E ( Y m + 1 ∣ A 2 ) P ( A 2 ) + E ( Y m + 1 ∣ A 1 c ∩ A 2 c ) P ( A 1 c ∩ A 2 c ) − E ( Y m + 1 ∣ A 1 ∩ A 2 ) P ( A 1 ∩ A 2 ) . (5)
Let A k A_k A k be the event that the overall best object of type k k k has already appeared, k = 1 , 2 k=1,2 k = 1 , 2 and assume that i , j ≥ 1 i,j\ge1 i , j ≥ 1 . Hence, P ( A 1 ) = i N > 0 P(A_1)=\frac{i}{N}>0 P ( A 1 ) = N i > 0 , P ( A 2 ) = j N > 0 P(A_2)=\frac{j}{N}>0 P ( A 2 ) = N j > 0 and E ( Y m + 1 ∣ A 1 ∩ A 2 ) = 0 E(Y_{m+1}\mid A_1\cap A_2)=0 E ( Y m + 1 ∣ A 1 ∩ A 2 ) = 0 . Now consider the probability that the first candidate of type 1 to appear after the i i i -th object of type 1 is the best of all the objects of type 1. Denote this probability by P ( Z i ) P(Z_i) P ( Z i ) . Suppose that the next candidate of type 1 to appear is the l l l -th object of type 1 and this is the best of all objects of type 1. For this to occur, then none of the objects i + 1 , i + 2 , … , l − 1 i+1,i+2,\ldots,l-1 i + 1 , i + 2 , … , l − 1 of type 1 were candidates and the l l l -th is the best overall. The probability of the first set of events is simply the probability that the best of the first l − 1 l-1 l − 1 objects of type 1 appeared amongst the first i i i , i.e. i l − 1 \frac{i}{l-1} l − 1 i . The probability that the l l l -th is the best object overall from an ordering is simply 1 / N 1/N 1/ N . Note that the best object overall from an ordering has to be a candidate. Summing over the possible values of l l l , i.e. i + 1 ≤ l ≤ N i+1\le l\le N i + 1 ≤ l ≤ N ,
P ( Z i ) = 1 N ( 1 + i i + 1 + i i + 2 + … + i N − 1 ) . (6) P(Z_i)=\frac{1}{N}\left(1+\frac{i}{i+1}+\frac{i}{i+2}+\ldots+\frac{i}{N-1}\right). \tag*{(6)} P ( Z i ) = N 1 ( 1 + i + 1 i + i + 2 i + … + N − 1 i ) . (6)
Given A 1 A_1 A 1 , if a candidate appears, it must be of type 2. Arguing as in the derivation of Equation (6) ,
E ( Y m + 1 ∣ A 1 ) P ( A 1 ) = i P ( Z j ) N = 1 N ( 1 + j j + 1 + j j + 2 + … + j N − 1 ) i N . (7) E(Y_{m+1}\mid A_1)P(A_1)=\frac{iP(Z_j)}{N}=\frac{1}{N}\left(1+\frac{j}{j+1}+\frac{j}{j+2}+\ldots+\frac{j}{N-1}\right)\frac{i}{N}. \tag*{(7)} E ( Y m + 1 ∣ A 1 ) P ( A 1 ) = N i P ( Z j ) = N 1 ( 1 + j + 1 j + j + 2 j + … + N − 1 j ) N i . (7)
Analogously,
E ( Y m + 1 ∣ A 2 ) P ( A 2 ) = j P ( Z i ) N = 1 N ( 1 + i i + 1 + i i + 2 + … + i N − 1 ) j N . (8) E(Y_{m+1}\mid A_2)P(A_2)=\frac{jP(Z_i)}{N}=\frac{1}{N}\left(1+\frac{i}{i+1}+\frac{i}{i+2}+\ldots+\frac{i}{N-1}\right)\frac{j}{N}. \tag*{(8)} E ( Y m + 1 ∣ A 2 ) P ( A 2 ) = N j P ( Z i ) = N 1 ( 1 + i + 1 i + i + 2 i + … + N − 1 i ) N j . (8)
Let S k S_k S k be the absolute rank of the best object seen so far of type k k k , k = 1 , 2 k=1,2 k = 1 , 2 . We have
E ( Y m + 1 ∣ A 1 c ∩ A 2 c ) P ( A 1 c ∩ A 2 c ) = ∑ u = 2 N − i + 1 ∑ v = 2 N − j + 1 E ( Y m + 1 ∣ S 1 = u , S 2 = v ) P [ S 1 = u , S 2 = v ] . E(Y_{m+1}\mid A_1^c\cap A_2^c)P(A_1^c\cap A_2^c)=\sum_{u=2}^{N-i+1}\sum_{v=2}^{N-j+1}E(Y_{m+1}\mid S_1=u,S_2=v)P[S_1=u,S_2=v]. E ( Y m + 1 ∣ A 1 c ∩ A 2 c ) P ( A 1 c ∩ A 2 c ) = u = 2 ∑ N − i + 1 v = 2 ∑ N − j + 1 E ( Y m + 1 ∣ S 1 = u , S 2 = v ) P [ S 1 = u , S 2 = v ] .
Note that
P [ S 1 = u ] = i N ( N − u i − 1 ) ( N − 1 i − 1 ) , 1 ≤ u ≤ N − i + 1 , P[S_1=u]=\frac{i}{N}\frac{\binom{N-u}{i-1}}{\binom{N-1}{i-1}},\qquad1\le u\le N-i+1, P [ S 1 = u ] = N i ( i − 1 N − 1 ) ( i − 1 N − u ) , 1 ≤ u ≤ N − i + 1 ,
Let S_k be the absolute rank of the best object … since for S 1 S_1 S 1 to be equal to u u u , then the object of type 1 with absolute rank u u u must appear amongst the first i i i objects and the remaining i − 1 i-1 i − 1 objects of type 1 seen so far must be chosen from the N − u N-u N − u objects of type 1 of absolute rank greater than u u u . Analogously,
P [ S 2 = v ] = j N ( N − v j − 1 ) ( N − 1 j − 1 ) , 1 ≤ v ≤ N − j + 1. P[S_2=v]=\frac{j}{N}\frac{\binom{N-v}{j-1}}{\binom{N-1}{j-1}},\qquad1\leq v\leq N-j+1. P [ S 2 = v ] = N j ( j − 1 N − 1 ) ( j − 1 N − v ) , 1 ≤ v ≤ N − j + 1.
The next candidate to appear is chosen at random from the u + v − 2 u+v-2 u + v − 2 possible candidates and two of them are the absolute best from their ordering. From the independence of the ranks of objects of different types, it follows that
E ( Y m + 1 ∣ A 1 c ∩ A 2 c ) P ( A 1 c ∩ A 2 c ) = i j N 2 ∑ u = 2 N − i + 1 ∑ v = 2 N − j + 1 ( N − u i − 1 ) ( N − 1 i − 1 ) ( N − v j − 1 ) ( N − 1 j − 1 ) 2 u + v − 2 . (9) E(Y_{m+1}\mid A_1^c\cap A_2^c)P(A_1^c\cap A_2^c)=\frac{ij}{N^2}\sum_{u=2}^{N-i+1}\sum_{v=2}^{N-j+1}\frac{\binom{N-u}{i-1}}{\binom{N-1}{i-1}}\frac{\binom{N-v}{j-1}}{\binom{N-1}{j-1}}\frac{2}{u+v-2}. \tag*{(9)} E ( Y m + 1 ∣ A 1 c ∩ A 2 c ) P ( A 1 c ∩ A 2 c ) = N 2 ij u = 2 ∑ N − i + 1 v = 2 ∑ N − j + 1 ( i − 1 N − 1 ) ( i − 1 N − u ) ( j − 1 N − 1 ) ( j − 1 N − v ) u + v − 2 2 . (9)
It follows from Equations (5) –(9) that
w i , j = i N 2 ∑ r = 0 N − j − 1 j j + r + j N 2 ∑ r = 0 N − i − 1 i i + r + i j N 2 ∑ u = 2 N − i + 1 ∑ v = 2 N − j + 1 ( N − u i − 1 ) ( N − 1 i − 1 ) ( N − v j − 1 ) ( N − 1 j − 1 ) 2 u + v − 2 . (10) w_{i,j}=\frac{i}{N^2}\sum_{r=0}^{N-j-1}\frac{j}{j+r}+\frac{j}{N^2}\sum_{r=0}^{N-i-1}\frac{i}{i+r}+\frac{ij}{N^2}\sum_{u=2}^{N-i+1}\sum_{v=2}^{N-j+1}\frac{\binom{N-u}{i-1}}{\binom{N-1}{i-1}}\frac{\binom{N-v}{j-1}}{\binom{N-1}{j-1}}\frac{2}{u+v-2}. \tag*{(10)} w i , j = N 2 i r = 0 ∑ N − j − 1 j + r j + N 2 j r = 0 ∑ N − i − 1 i + r i + N 2 ij u = 2 ∑ N − i + 1 v = 2 ∑ N − j + 1 ( i − 1 N − 1 ) ( i − 1 N − u ) ( j − 1 N − 1 ) ( j − 1 N − v ) u + v − 2 2 . (10)
For completeness, we also derive a formula for w i , 0 w_{i,0} w i , 0 using an analogous approach. Note that w 0 , 0 = 1 N w_{0,0}=\frac{1}{N} w 0 , 0 = N 1 . For i ≥ 1 i\geq1 i ≥ 1 , we have
w i , 0 = E [ Y m + 1 ∣ A 1 ] P ( A 1 ) + E [ Y m + 1 ∣ A 1 c ] P ( A 1 c ) . (11) w_{i,0}=E[Y_{m+1}\mid A_1]P(A_1)+E[Y_{m+1}\mid A_1^c]P(A_1^c). \tag*{(11)} w i , 0 = E [ Y m + 1 ∣ A 1 ] P ( A 1 ) + E [ Y m + 1 ∣ A 1 c ] P ( A 1 c ) . (11)
Given A 1 A_1 A 1 , the next candidate to appear must be the first object of type 2 to appear, i.e.
E [ Y m + 1 ∣ A 1 ] P ( A 1 ) = 1 N × i N = i N 2 . (12) E[Y_{m+1}\mid A_1]P(A_1)=\frac{1}{N}\times\frac{i}{N}=\frac{i}{N^2}. \tag*{(12)} E [ Y m + 1 ∣ A 1 ] P ( A 1 ) = N 1 × N i = N 2 i . (12)
Arguing analogously to the derivation of Equation (9) ,
E [ Y m + 1 ∣ A 1 c ] P ( A 1 c ) = ∑ u = 2 N − i + 1 E [ Y m + 1 ∣ S 1 = u ] P ( S 1 = u ) = i N ∑ u = 2 N − i + 1 ( N − u i − 1 ) ( N − 1 i − 1 ) 2 u + N − 1 . (13) \begin{aligned}
E[Y_{m+1}\mid A_1^c]P(A_1^c)=\sum_{u=2}^{N-i+1}E[Y_{m+1}\mid S_1=u]P(S_1=u) \\
&=\frac{i}{N}\sum_{u=2}^{N-i+1}\frac{\binom{N-u}{i-1}}{\binom{N-1}{i-1}}\frac{2}{u+N-1}. \tag*{(13)}
\end{aligned} E [ Y m + 1 ∣ A 1 c ] P ( A 1 c ) = u = 2 ∑ N − i + 1 E [ Y m + 1 ∣ S 1 = u ] P ( S 1 = u ) = N i u = 2 ∑ N − i + 1 ( i − 1 N − 1 ) ( i − 1 N − u ) u + N − 1 2 . (13)
It follows from Equations (12) and (13) that
w i , 0 = i N 2 + i N ∑ u = 2 N − i + 1 ( N − u i − 1 ) ( N − 1 i − 1 ) 2 u + N − 1 . (14) w_{i,0}=\frac{i}{N^2}+\frac{i}{N}\sum_{u=2}^{N-i+1}\frac{\binom{N-u}{i-1}}{\binom{N-1}{i-1}}\frac{2}{u+N-1}. \tag*{(14)} w i , 0 = N 2 i + N i u = 2 ∑ N − i + 1 ( i − 1 N − 1 ) ( i − 1 N − u ) u + N − 1 2 . (14)
Lemma 3. Suppose that w i , j ≤ i N w_{i,j}\leq\frac{i}{N} w i , j ≤ N i and j ≥ 1 j\geq1 j ≥ 1 . It follows that for i ′ ≥ i i'\geq i i ′ ≥ i , w i ′ , j ≤ i ′ N w_{i',j}\leq\frac{i'}{N} w i ′ , j ≤ N i ′ .
Proof. Suppose that w i , j N ≤ i N w_{i,j}^N\leq\frac{i}{N} w i , j N ≤ N i , i.e.
i N ≥ i N 2 ∑ r = 0 N − j − 1 j j + r + j N 2 ∑ r = 0 N − i − 1 i i + r + i j N 2 ∑ u = 2 N − i + 1 ∑ v = 2 N − j + 1 ( N − u i − 1 ) ( N − 1 i − 1 ) ( N − v j − 1 ) ( N − 1 j − 1 ) 2 u + v − 2 . \frac{i}{N}\geq\frac{i}{N^2}\sum_{r=0}^{N-j-1}\frac{j}{j+r}+\frac{j}{N^2}\sum_{r=0}^{N-i-1}\frac{i}{i+r}+\frac{ij}{N^2}\sum_{u=2}^{N-i+1}\sum_{v=2}^{N-j+1}\frac{\binom{N-u}{i-1}}{\binom{N-1}{i-1}}\frac{\binom{N-v}{j-1}}{\binom{N-1}{j-1}}\frac{2}{u+v-2}. N i ≥ N 2 i r = 0 ∑ N − j − 1 j + r j + N 2 j r = 0 ∑ N − i − 1 i + r i + N 2 ij u = 2 ∑ N − i + 1 v = 2 ∑ N − j + 1 ( i − 1 N − 1 ) ( i − 1 N − u ) ( j − 1 N − 1 ) ( j − 1 N − v ) u + v − 2 2 . Equivalently,
1 ≥ j N [ ∑ r = 0 N − j − 1 1 j + r + ∑ r = 0 N − i − 1 1 i + r + ∑ u = 2 N − i + 1 ∑ v = 2 N − j + 1 ( N − u i − 1 ) ( N − 1 i − 1 ) ( N − v j − 1 ) ( N − 1 j − 1 ) 2 u + v − 2 ] . (15) 1\geq\frac{j}{N}\left[\sum_{r=0}^{N-j-1}\frac{1}{j+r}+\sum_{r=0}^{N-i-1}\frac{1}{i+r}+\sum_{u=2}^{N-i+1}\sum_{v=2}^{N-j+1}\frac{\binom{N-u}{i-1}}{\binom{N-1}{i-1}}\frac{\binom{N-v}{j-1}}{\binom{N-1}{j-1}}\frac{2}{u+v-2}\right]. \tag*{(15)} 1 ≥ N j [ r = 0 ∑ N − j − 1 j + r 1 + r = 0 ∑ N − i − 1 i + r 1 + u = 2 ∑ N − i + 1 v = 2 ∑ N − j + 1 ( i − 1 N − 1 ) ( i − 1 N − u ) ( j − 1 N − 1 ) ( j − 1 N − v ) u + v − 2 2 ] . (15)
The first sum on the right hand side is independent of i i i . The second sum is clearly decreasing in i i i . Note that the number of terms in the third sum is decreasing in i i i . Fixing u u u , v v v and j j j , the term in this sum is decreasing in i i i if and only if ( N − u i − 1 ) ( N − 1 i − 1 ) \frac{\binom{N-u}{i-1}}{\binom{N-1}{i-1}} ( i − 1 N − 1 ) ( i − 1 N − u ) is decreasing in i i i . We have
( N − u i − 1 ) ( N − 1 i − 1 ) = N − u N − 1 × N − u − 1 N − 2 × ⋯ × N − u − i + 2 N − i + 1 . \frac{\binom{N-u}{i-1}}{\binom{N-1}{i-1}} = \frac{N-u}{N-1} \times\frac{N-u-1}{N-2} \times\cdots\times\frac{N-u-i+2}{N-i+1}. ( i − 1 N − 1 ) ( i − 1 N − u ) = N − 1 N − u × N − 2 N − u − 1 × ⋯ × N − i + 1 N − u − i + 2 .
Since each term in this product is less than 1 1 1 , the product is decreasing in i i i . Hence, the conclusion follows.
Lemma 4. For i ≥ i N ∗ i \ge i_N^* i ≥ i N ∗ , w i , i ≤ i / N w_{i,i} \le i/N w i , i ≤ i / N . Also, w i , i + 1 < i N w_{i,i+1} < \frac{i}{N} w i , i + 1 < N i .
Proof. From (4) , we have
w i , i = 1 N + i w i , i + 1 i + 1 . w_{i,i} = \frac{1}{N} + \frac{i w_{i,i+1}}{i+1}. w i , i = N 1 + i + 1 i w i , i + 1 . Assume that w i , i ≤ i / N w_{i,i} \le i/N w i , i ≤ i / N . Rearranging the above equation, we obtain
w i , i + 1 = i + 1 i [ w i , i − 1 N ] ≤ i 2 − 1 i N < i N . w_{i,i+1} = \frac{i+1}{i}\left[w_{i,i} - \frac{1}{N}\right] \le\frac{i^2-1}{iN} < \frac{i}{N}. w i , i + 1 = i i + 1 [ w i , i − N 1 ] ≤ i N i 2 − 1 < N i . It follows from Lemma 3 that w i + 1 , i + 1 < i + 1 N w_{i+1,i+1} < \frac{i+1}{N} w i + 1 , i + 1 < N i + 1 and Lemma 4 then follows by induction.
General Form of the Optimal Strategy
In this section the form of the optimal strategy will be derived using a set of recursion arguments. A number of the lemmas are both technical and used as stepping stones to prove the main theorem of the paper, which presents the general form of the optimal strategy for any N N N . The proofs of these lemmas are given in the appendix. The proofs of theorems are given in this section.
Intuitively, whenever a sufficiently large number of objects of both types have appeared, then the DM should accept a candidate of either type. Hence, we start by deriving the region in which a candidate of either type should be accepted. The following lemma states that when n n n objects in total have already appeared and the DM accepts the next candidate to appear, then the expected payoff of the DM is greatest when the difference between the number of objects of each type to have appeared is minimized.
Lemma 5. Let $0 \le a \le b \le c \le d \le N$, such that a + d = b + c = n a+d=b+c=n a + d = b + c = n and ( a , d ) ≠ ( b , c ) (a,d) \ne(b,c) ( a , d ) = ( b , c ) . Then w a , d ≤ w b , c w_{a,d} \le w_{b,c} w a , d ≤ w b , c .
The second technical lemma is critical in proving that when it is optimal to accept the next candidate to appear, then the function v i , j v_{i,j} v i , j is decreasing in both i i i and j j j .
Lemma 6. Suppose that j ≤ i < N j \le i < N j ≤ i < N . It follows that
i w i + 1 , j i + 1 ≥ j w i , j + 1 j + 1 , \frac{i w_{i+1,j}}{i+1} \ge\frac{j w_{i,j+1}}{j+1}, i + 1 i w i + 1 , j ≥ j + 1 j w i , j + 1 , i.e.
1 N + i w i + 1 , j i + 1 ≥ 1 N + j w i , j + 1 j + 1 . \frac{1}{N}+\frac{i w_{i+1,j}}{i+1} \ge\frac{1}{N}+\frac{j w_{i,j+1}}{j+1}. N 1 + i + 1 i w i + 1 , j ≥ N 1 + j + 1 j w i , j + 1 .
Remark 1. Suppose that the DM accepts the next candidate to appear. Lemma 5 can be interpreted as stating that given that the next object is not a candidate, then the DM prefers the object to be of the type that has appeared less often. Lemma 6 states that when there is no information about the next object, then the DM prefers the object to be of the type that has appeared more often.
Theorem 1. Suppose that w i , j ≤ min { i N , j N } w_{i,j} \le\min\left\{\frac{i}{N},\frac{j}{N}\right\} w i , j ≤ min { N i , N j } . For i ′ ≥ i i' \ge i i ′ ≥ i , j ′ ≥ j j' \ge j j ′ ≥ j , the function w i ′ , j ′ w_{i',j'} w i ′ , j ′ is decreasing in both of its arguments.
Proof. Note that from symmetry, we may assume that i ≥ j i \ge j i ≥ j . It follows from Lemma 3 that
1 N ≥ w i + 1 , j i + 1 ; 1 N ≥ w i , j + 1 j + 1 . \frac{1}{N} \ge\frac{w_{i+1,j}}{i+1}; \qquad\frac{1}{N} \ge\frac{w_{i,j+1}}{j+1}. N 1 ≥ i + 1 w i + 1 , j ; N 1 ≥ j + 1 w i , j + 1 .
From Equation (4) , we obtain
w i , i = 1 N + i w i + 1 , i i + 1 ≥ w i + 1 , i i + 1 + i w i + 1 , i i + 1 = w i + 1 , i = w i , i + 1 . \begin{aligned}
w_{i,i} &= \frac{1}{N}+\frac{i w_{i+1,i}}{i+1}\\
&\ge\frac{w_{i+1,i}}{i+1}+\frac{i w_{i+1,i}}{i+1}=w_{i+1,i}=w_{i,i+1}.
\end{aligned} w i , i = N 1 + i + 1 i w i + 1 , i ≥ i + 1 w i + 1 , i + i + 1 i w i + 1 , i = w i + 1 , i = w i , i + 1 .
Suppose that i > j i>j i > j . From Equation (4) , we obtain
w i , j = 1 N + i α i , j w i + 1 , j i + 1 + j ( 1 − α i , j ) w i , j + 1 j + 1 . w_{i,j}=\frac{1}{N}+\frac{i\alpha_{i,j}w_{i+1,j}}{i+1}+\frac{j(1-\alpha_{i,j})w_{i,j+1}}{j+1}. w i , j = N 1 + i + 1 i α i , j w i + 1 , j + j + 1 j ( 1 − α i , j ) w i , j + 1 .
From Lemma 6 and the assumptions of the theorem
w i , j ≥ w i , j + 1 j + 1 + j α i , j w i , j + 1 j + 1 + j ( 1 − α i , j ) w i , j + 1 j + 1 = w i , j + 1 . w_{i,j}\ge\frac{w_{i,j+1}}{j+1}+\frac{j\alpha_{i,j}w_{i,j+1}}{j+1}+\frac{j(1-\alpha_{i,j})w_{i,j+1}}{j+1}=w_{i,j+1}. w i , j ≥ j + 1 w i , j + 1 + j + 1 j α i , j w i , j + 1 + j + 1 j ( 1 − α i , j ) w i , j + 1 = w i , j + 1 .
Note that from Lemma 5, w i + 1 , j ≤ w i , j + 1 w_{i+1,j}\le w_{i,j+1} w i + 1 , j ≤ w i , j + 1 and thus w i + 1 , j ≤ w i , j w_{i+1,j}\le w_{i,j} w i + 1 , j ≤ w i , j . It follows that w i + 1 , j ≤ min { i + 1 N , j N } w_{i+1,j}\le\min\left\{\frac{i+1}{N},\frac{j}{N}\right\} w i + 1 , j ≤ min { N i + 1 , N j } and w i , j + 1 ≤ min { i N , j + 1 N } w_{i,j+1}\le\min\left\{\frac{i}{N},\frac{j+1}{N}\right\} w i , j + 1 ≤ min { N i , N j + 1 } . Hence, the theorem follows from induction on the number of objects to appear.
Corollary to Theorem 1: Suppose that w i , j ≤ min { i N , j N } w_{i,j}\le\min\left\{\frac{i}{N},\frac{j}{N}\right\} w i , j ≤ min { N i , N j } . Then it is optimal to accept a candidate in state ( i , j , k ) (i,j,k) ( i , j , k ) , k = 1 , 2 k=1,2 k = 1 , 2 . It is also optimal to accept any candidate that appears at a later moment. It follows that v i , j = w i , j v_{i,j}=w_{i,j} v i , j = w i , j . Since i N w = min { i : w i , i ≤ i N } i_N^w=\min\{i:w_{i,i}\le\frac{i}{N}\} i N w = min { i : w i , i ≤ N i } and i N v = min { i : v i , i ≤ i N } i_N^v=\min\{i:v_{i,i}\le\frac{i}{N}\} i N v = min { i : v i , i ≤ N i } , then i N w = i N v i_N^w=i_N^v i N w = i N v .
The condition in the corollary states that it is better to accept a candidate in state ( i , j , k ) (i,j,k) ( i , j , k ) , k = 1 , 2 k=1,2 k = 1 , 2 than to accept the next candidate to appear, regardless of the type of the next candidate. Theorem 1 guarantees that when the next candidate appears, it is better to accept such a candidate than to wait for the following candidate to appear. Hence, the corollary follows from the OSLAR property. It follows that there exists a set, B 3 N B_3^N B 3 N , of pairs ( i , j ) (i,j) ( i , j ) such that the first candidate to appear after a state ( i , j , 0 ) (i,j,0) ( i , j , 0 ) has been reached should always be accepted.
Note that if, for example, w i , j > j N w_{i,j}>\frac{j}{N} w i , j > N j , then in state ( i , j , 2 ) (i,j,2) ( i , j , 2 ) it is better to reject such a candidate and accept the next candidate to appear than accept the current candidate. It follows that if the inequality w i , j ≤ min { i N , j N } w_{i,j}\le\min\left\{\frac{i}{N},\frac{j}{N}\right\} w i , j ≤ min { N i , N j } is not satisfied, then for i ≥ j i\ge j i ≥ j it cannot be optimal to accept a candidate in state ( i , j , 2 ) (i,j,2) ( i , j , 2 ) . Similarly, for j ≥ i j\ge i j ≥ i it cannot be optimal to accept a candidate in state ( i , j , 1 ) (i,j,1) ( i , j , 1 ) .
Intuitively, there will be a set of pairs ( i , j ) (i,j) ( i , j ) such that i > j i>j i > j and j N < v i , j ≤ i N \frac{j}{N}<v_{i,j}\le\frac{i}{N} N j < v i , j ≤ N i . Thus a candidate should be accepted in state ( i , j , 1 ) (i,j,1) ( i , j , 1 ) , but rejected in state ( i , j , 2 ) (i,j,2) ( i , j , 2 ) . By symmetry, there will be an analogous set of pairs ( j , i ) (j,i) ( j , i ) such that a candidate should be accepted in state ( j , i , 2 ) (j,i,2) ( j , i , 2 ) , but rejected in state ( j , i , 1 ) (j,i,1) ( j , i , 1 ) . Lemma 7 is useful in both describing the boundary of the region B 3 B_3 B 3 with such pairs and showing that if it is optimal to stop in state ( i , j , 1 ) (i,j,1) ( i , j , 1 ) , then it is optimal to stop in state ( i + 1 , j , 1 ) (i+1,j,1) ( i + 1 , j , 1 ) . The proof of this lemma is given in the appendix.
Lemma 7. For 1 ≤ i , j ≤ N − 1 1\le i,j\le N-1 1 ≤ i , j ≤ N − 1 , ∣ v i + 1 , j − v i , j + 1 ∣ ≤ 1 N \lvert v_{i+1,j}-v_{i,j+1}\rvert\le\frac{1}{N} ∣ v i + 1 , j − v i , j + 1 ∣ ≤ N 1 .
Corollary to Lemma 7: If a candidate should be accepted in state ( i , j , 1 ) (i,j,1) ( i , j , 1 ) , then a candidate should be accepted in state ( i + 1 , j , 1 ) (i+1,j,1) ( i + 1 , j , 1 ) .
Proof. Assume that a candidate should be accepted in state ( i , j , 1 ) (i,j,1) ( i , j , 1 ) , i.e. v i , j ≤ i N v_{i,j} \le\frac{i}{N} v i , j ≤ N i . We have
v i , j ≥ α i , j v i + 1 , j + ( 1 − α i , j ) v i , j + 1 ≥ α i , j v i + 1 , j + ( 1 − α i , j ) ( v i + 1 , j − 1 N ) ≥ v i + 1 , j − 1 − α i , j N . \begin{aligned}
v_{i,j} &\ge\alpha_{i,j}v_{i+1,j}+(1-\alpha_{i,j})v_{i,j+1}\\
&\ge\alpha_{i,j}v_{i+1,j}+(1-\alpha_{i,j})\left(v_{i+1,j}-\frac{1}{N}\right)\\
&\ge v_{i+1,j}-\frac{1-\alpha_{i,j}}{N}.
\end{aligned} v i , j ≥ α i , j v i + 1 , j + ( 1 − α i , j ) v i , j + 1 ≥ α i , j v i + 1 , j + ( 1 − α i , j ) ( v i + 1 , j − N 1 ) ≥ v i + 1 , j − N 1 − α i , j .
Hence,
v i + 1 , j ≤ v i , j + 1 − α i , j N ≤ i + 1 − α i , j N ≤ i + 1 N . v_{i+1,j}\le v_{i,j}+\frac{1-\alpha_{i,j}}{N}\le\frac{i+1-\alpha_{i,j}}{N}\le\frac{i+1}{N}. v i + 1 , j ≤ v i , j + N 1 − α i , j ≤ N i + 1 − α i , j ≤ N i + 1 .
It follows that a candidate should be accepted in state ( i + 1 , j , 1 ) (i+1,j,1) ( i + 1 , j , 1 ) .
We now consider the form of the boundary of the set B 3 N B_3^N B 3 N . Assume i ≥ j i\ge j i ≥ j . For a fixed i i i , define j ∘ ( i ) j^\circ(i) j ∘ ( i ) to be the smallest value of j j j such that ( i , j ∘ ( i ) ) ∈ B 3 N (i,j^\circ(i))\in B_3^N ( i , j ∘ ( i )) ∈ B 3 N . Note that from the Corollary to Theorem 1, for all j ≥ j ∘ ( i ) j\ge j^\circ(i) j ≥ j ∘ ( i ) , ( i , j ) ∈ B 3 N (i,j)\in B_3^N ( i , j ) ∈ B 3 N . When i = N i=N i = N , the problem reduces to the classical secretary problem (CSP). Starting from the state ( N , j , 0 ) (N,j,0) ( N , j , 0 ) the DM should accept a candidate at moment j ′ j' j ′ if and only if j ′ ≥ j ∗ ( N ) j'\ge j^*(N) j ′ ≥ j ∗ ( N ) , where j ∗ ( N ) j^*(N) j ∗ ( N ) is the optimal threshold for the CSP. Note that j ∗ ( N ) j^*(N) j ∗ ( N ) is non-decreasing in N N N , j ∗ ( 3 ) = 2 j^*(3)=2 j ∗ ( 3 ) = 2 , j ∗ ( N ) > N exp ( − 1 ) j^*(N)>N\exp(-1) j ∗ ( N ) > N exp ( − 1 ) and lim N → ∞ j ∗ ( N ) N = exp ( − 1 ) \lim_{N\to\infty}\frac{j^*(N)}{N}=\exp(-1) lim N → ∞ N j ∗ ( N ) = exp ( − 1 ) . It follows that ( N , j ∗ ( N ) − 1 ) ∈ B 3 (N,j^*(N)-1)\in B_3 ( N , j ∗ ( N ) − 1 ) ∈ B 3 , but ( N , j ∗ ( N ) − 2 ) ∉ B 3 (N,j^*(N)-2)\notin B_3 ( N , j ∗ ( N ) − 2 ) ∈ / B 3 . Hence, j ∘ ( N ) = j ∗ ( N ) − 1 j^\circ(N)=j^*(N)-1 j ∘ ( N ) = j ∗ ( N ) − 1 .
Suppose that i ≥ i N ∘ i\ge i_N^\circ i ≥ i N ∘ . From the form of v i , j v_{i,j} v i , j , j ∘ ( i ) j^\circ(i) j ∘ ( i ) is the smallest value of j j j to satisfy v i , j + 1 ≤ j + 1 N v_{i,j+1}\le\frac{j+1}{N} v i , j + 1 ≤ N j + 1 , i.e. if the next object to appear after state ( i , j , 0 ) (i,j,0) ( i , j , 0 ) is a candidate of type two, then it should be accepted. Note that if ( i , j ) ∈ B 3 (i,j)\in B_3 ( i , j ) ∈ B 3 , then ( i + 1 , j ) ∈ B 3 (i+1,j)\in B_3 ( i + 1 , j ) ∈ B 3 . It follows that j ∘ ( i ) j^\circ(i) j ∘ ( i ) is non-increasing in i i i . In addition, when v i , j ≤ j N v_{i,j}\le\frac{j}{N} v i , j ≤ N j from Lemma 7 it follows that v i − 1 , j + 1 ≤ j + 1 N v_{i-1,j+1}\le\frac{j+1}{N} v i − 1 , j + 1 ≤ N j + 1 . Hence, whenever i ≥ j + 1 i\ge j+1 i ≥ j + 1 and ( i , j − 1 ) ∈ B 3 (i,j-1)\in B_3 ( i , j − 1 ) ∈ B 3 , then ( i − 1 , j ) ∈ B 3 (i-1,j)\in B_3 ( i − 1 , j ) ∈ B 3 . By symmetry, ( i , i − 1 ) ∈ B 3 (i,i-1)\in B_3 ( i , i − 1 ) ∈ B 3 , if and only if ( i − 1 , i ) ∈ B 3 (i-1,i)\in B_3 ( i − 1 , i ) ∈ B 3 . It follows from these facts that for i ≥ i N ∘ i\ge i_N^\circ i ≥ i N ∘ , 0 ≤ j ∘ ( i − 1 ) − j ∘ ( i ) ≤ 1 0\le j^\circ(i-1)-j^\circ(i)\le1 0 ≤ j ∘ ( i − 1 ) − j ∘ ( i ) ≤ 1 . Note that for i N ∘ ≤ i ≤ N i_N^\circ\le i\le N i N ∘ ≤ i ≤ N , we have that j ∘ ( N ) ≤ j ∘ ( i ) ≤ j ∘ ( i N ∘ ) j^\circ(N)\le j^\circ(i)\le j^\circ(i_N^\circ) j ∘ ( N ) ≤ j ∘ ( i ) ≤ j ∘ ( i N ∘ ) . From the definition of i N ∘ i_N^\circ i N ∘ and the corollary to Theorem 1, ( i N ∘ , i N ∘ − 1 ) ∈ B 3 (i_N^\circ,i_N^\circ-1)\in B_3 ( i N ∘ , i N ∘ − 1 ) ∈ B 3 . It follows that ( i N ∘ − 1 , i N ∘ ) ∈ B 3 (i_N^\circ-1,i_N^\circ)\in B_3 ( i N ∘ − 1 , i N ∘ ) ∈ B 3 . Hence, j ∘ ( i N ∘ ) ≤ i N ∘ − 1 j^\circ(i_N^\circ)\le i_N^\circ-1 j ∘ ( i N ∘ ) ≤ i N ∘ − 1 . Since v i N ∘ − 1 , i N ∘ − 1 > i N ∘ − 1 N v_{i_N^\circ-1,i_N^\circ-1}>\frac{i_N^\circ-1}{N} v i N ∘ − 1 , i N ∘ − 1 > N i N ∘ − 1 , it follows from Lemma 7 that v i N ∘ , i N ∘ − 2 > i N ∘ − 2 N v_{i_N^\circ,i_N^\circ-2}>\frac{i_N^\circ-2}{N} v i N ∘ , i N ∘ − 2 > N i N ∘ − 2 . Hence, ( i N ∘ , i N ∘ − 3 ) ∉ B 3 (i_N^\circ,i_N^\circ-3)\notin B_3 ( i N ∘ , i N ∘ − 3 ) ∈ / B 3 . It follows that j ∘ ( i N ∘ ) ≥ i N ∘ − 2 j^\circ(i_N^\circ)\ge i_N^\circ-2 j ∘ ( i N ∘ ) ≥ i N ∘ − 2 .
The following lemma is useful in proving the hypothesis that if a candidate should be accepted in state ( i , j , 1 ) (i,j,1) ( i , j , 1 ) , then a candidate should be accepted in state ( i , j + 1 , 1 ) (i,j+1,1) ( i , j + 1 , 1 ) . The proof of this lemma is given in the appendix.
Lemma 8. Assume that it is optimal to accept an offer in state ( i + 1 , j , 1 ) (i+1,j,1) ( i + 1 , j , 1 ) , where j ≤ i < N j\le i<N j ≤ i < N . It follows that
1 N + i v i + 1 , j i + 1 ≥ v i , j + 1 . \frac{1}{N}+\frac{i v_{i+1,j}}{i+1}\ge v_{i,j+1}. N 1 + i + 1 i v i + 1 , j ≥ v i , j + 1 .
Remark 2. Lemma 8 states that when a candidate of type 1 should be accepted it is better for the searcher that the next object to appear is of type 1 rather than an object of type 2 (given that such an object is rejected).
Corollary to Lemma 8 and Theorem 1: Assume that it is optimal to accept an offer in state ( i + 1 , j , 1 ) (i+1,j,1) ( i + 1 , j , 1 ) , where i > j i>j i > j . It follows that v i , j ≥ v i , j + 1 v_{i,j}\ge v_{i,j+1} v i , j ≥ v i , j + 1 . Hence, if it is optimal to stop in state ( i , j , 1 ) (i,j,1) ( i , j , 1 ) , it is also optimal to stop in state ( i , j + 1 , 1 ) (i,j+1,1) ( i , j + 1 , 1 ) .
This corollary results from the facts that
i: whenever the next candidate of either type should be accepted, then v i , j v_{i,j} v i , j is decreasing in both i i i and j j j .
ii: whenever a candidate should be accepted in state ( i + 1 , j , 1 ) (i+1,j,1) ( i + 1 , j , 1 ) , but rejected in state ( i , j + 1 , 2 ) (i,j+1,2) ( i , j + 1 , 2 ) , then v i , j v_{i,j} v i , j is a weighted average of 1 N + v i + 1 , j \frac{1}{N}+v_{i+1,j} N 1 + v i + 1 , j and v i , j + 1 v_{i,j+1} v i , j + 1 , where 1 N + v i + 1 , j ≥ v i , j + 1 \frac{1}{N}+v_{i+1,j}\ge v_{i,j+1} N 1 + v i + 1 , j ≥ v i , j + 1 .
Suppose that it is optimal to stop in state ( i , j , 1 ) (i,j,1) ( i , j , 1 ) . From the corollaries to Lemmas 7 and 8 , together with Theorem 1, it follows that it is optimal to stop in both of the states ( i + 1 , j , 1 ) (i+1,j,1) ( i + 1 , j , 1 ) and ( i , j + 1 , 1 ) (i,j+1,1) ( i , j + 1 , 1 ) . It follows by induction that it is optimal to stop in any future state ( i ′ , j ′ , 1 ) (i',j',1) ( i ′ , j ′ , 1 ) , where i ≤ i ′ i \leq i' i ≤ i ′ and j ≤ j ′ j \leq j' j ≤ j ′ . By symmetry, if it is optimal to stop in state ( i , j , 2 ) (i,j,2) ( i , j , 2 ) , then it is optimal to stop in any future state ( i ′ , j ′ , 2 ) (i',j',2) ( i ′ , j ′ , 2 ) , where i ≤ i ′ i \leq i' i ≤ i ′ and j ≤ j ′ j \leq j' j ≤ j ′ .
In summary, the DM should initially reject any candidate, until the trajectory of the search process enters a region in which a candidate of the most often observed type should be accepted. Eventually, the trajectory enters a region in which the first candidate of either type should be accepted. Before giving the general form of the solution, we address the question of the value of i N ∙ i_N^\bullet i N ∙ and whether it is possible that the trajectory passes directly from the region in which all objects are rejected to the region in which any candidate is accepted. Intuitively, this might occur when the number of objects of both type that have been observed is close to i N ∙ i_N^\bullet i N ∙ .
Since v i N ∙ , i N ∙ ≤ i N ∙ N v_{i_N^\bullet,i_N^\bullet} \leq\frac{i_N^\bullet}{N} v i N ∙ , i N ∙ ≤ N i N ∙ , a candidate should be accepted in state ( i N ∙ , i N ∙ , k ) (i_N^\bullet,i_N^\bullet,k) ( i N ∙ , i N ∙ , k ) , where k ∈ { 1 , 2 } k \in\{1,2\} k ∈ { 1 , 2 } and, from the form of the optimal strategy, at any future decision point. Also, v i N ∙ − 1 , i N ∙ − 1 > i N ∙ − 1 N v_{i_N^\bullet-1,i_N^\bullet-1} > \frac{i_N^\bullet-1}{N} v i N ∙ − 1 , i N ∙ − 1 > N i N ∙ − 1 . Hence, a candidate should be rejected in state ( i N ∙ − 1 , i N ∙ − 1 , k ) (i_N^\bullet-1,i_N^\bullet-1,k) ( i N ∙ − 1 , i N ∙ − 1 , k ) , where k ∈ { 1 , 2 } k \in\{1,2\} k ∈ { 1 , 2 } and, from the form of the optimal strategy, at any earlier decision points.
It follows from Lemma 7 that when i ≥ j i \geq j i ≥ j , i + j = 2 i N ∙ i+j=2i_N^\bullet i + j = 2 i N ∙ , then v i , j ≤ i N v_{i,j} \leq\frac{i}{N} v i , j ≤ N i . Hence, a candidate of type 1 should always be accepted in state ( i , j , 1 ) (i,j,1) ( i , j , 1 ) . Analogously, when i ≥ j i \geq j i ≥ j , i + j = 2 ( i N ∙ − 1 ) i+j=2(i_N^\bullet-1) i + j = 2 ( i N ∙ − 1 ) , then a candidate of type 2 should always be rejected in state ( i , j , 2 ) (i,j,2) ( i , j , 2 ) .
We now consider the optimal actions in state ( i N ∙ , i N ∙ − 1 , k ) (i_N^\bullet,i_N^\bullet-1,k) ( i N ∙ , i N ∙ − 1 , k ) , where k ∈ { 1 , 2 } k \in\{1,2\} k ∈ { 1 , 2 } . The following three cases are possible:
i: A candidate should be accepted in states ( i N ∙ , i N ∙ − 1 , 1 ) (i_N^\bullet,i_N^\bullet-1,1) ( i N ∙ , i N ∙ − 1 , 1 ) and ( i N ∙ , i N ∙ − 1 , 2 ) (i_N^\bullet,i_N^\bullet-1,2) ( i N ∙ , i N ∙ − 1 , 2 ) .
It follows that v i N ∙ , i N ∙ − 1 ≤ i N ∙ − 1 N v_{i_N^\bullet,i_N^\bullet-1} \leq\frac{i_N^\bullet-1}{N} v i N ∙ , i N ∙ − 1 ≤ N i N ∙ − 1 .
ii: A candidate should be accepted in state ( i N ∙ , i N ∙ − 1 , 1 ) (i_N^\bullet,i_N^\bullet-1,1) ( i N ∙ , i N ∙ − 1 , 1 ) , but rejected in state ( i N ∙ , i N ∙ − 1 , 2 ) (i_N^\bullet,i_N^\bullet-1,2) ( i N ∙ , i N ∙ − 1 , 2 ) .
It follows that i N ∙ − 1 N < v i N ∙ , i N ∙ − 1 ≤ i N ∙ N \frac{i_N^\bullet-1}{N} < v_{i_N^\bullet,i_N^\bullet-1} \leq\frac{i_N^\bullet}{N} N i N ∙ − 1 < v i N ∙ , i N ∙ − 1 ≤ N i N ∙ .
iii: A candidate should be rejected in states ( i N ∙ , i N ∙ − 1 , 1 ) (i_N^\bullet,i_N^\bullet-1,1) ( i N ∙ , i N ∙ − 1 , 1 ) and ( i N ∙ , i N ∙ − 1 , 2 ) (i_N^\bullet,i_N^\bullet-1,2) ( i N ∙ , i N ∙ − 1 , 2 ) .
It follows that v i N ∙ , i N ∙ − 1 > i N ∙ N v_{i_N^\bullet,i_N^\bullet-1} > \frac{i_N^\bullet}{N} v i N ∙ , i N ∙ − 1 > N i N ∙ .
In the first two cases
v i N ∙ − 1 , i N ∙ − 1 = 1 N + ( i N ∙ − 1 ) v i N ∙ , i N ∙ − 1 i N ∙ . (16) v_{i_N^\bullet-1,i_N^\bullet-1}=\frac{1}{N}+\frac{(i_N^\bullet-1)v_{i_N^\bullet,i_N^\bullet-1}}{i_N^\bullet}. \tag*{(16)} v i N ∙ − 1 , i N ∙ − 1 = N 1 + i N ∙ ( i N ∙ − 1 ) v i N ∙ , i N ∙ − 1 . (16)
Hence, in the first case
i N ∙ − 1 N < v i N ∙ − 1 , i N ∙ − 1 ≤ 1 N + ( i N ∙ − 1 ) 2 N i N ∙ = i N ∙ − 1 N + 1 N i N ∙ ≤ i N ∙ N . (17) \frac{i_N^\bullet-1}{N}<v_{i_N^\bullet-1,i_N^\bullet-1}\leq\frac{1}{N}+\frac{(i_N^\bullet-1)^2}{Ni_N^\bullet}=\frac{i_N^\bullet-1}{N}+\frac{1}{Ni_N^\bullet}\leq\frac{i_N^\bullet}{N}. \tag*{(17)} N i N ∙ − 1 < v i N ∙ − 1 , i N ∙ − 1 ≤ N 1 + N i N ∙ ( i N ∙ − 1 ) 2 = N i N ∙ − 1 + N i N ∙ 1 ≤ N i N ∙ . (17)
Analogously, in the second case
i N ∙ − 1 N + 1 N i N ∙ < v i N ∙ − 1 , i N ∙ − 1 ≤ i N ∙ N . \frac{i_N^\bullet-1}{N}+\frac{1}{Ni_N^\bullet}<v_{i_N^\bullet-1,i_N^\bullet-1}\leq\frac{i_N^\bullet}{N}. N i N ∙ − 1 + N i N ∙ 1 < v i N ∙ − 1 , i N ∙ − 1 ≤ N i N ∙ .
In both of these cases, it follows from Lemma 7 that given i ≥ j i \geq j i ≥ j , i + j = 2 i N ∙ − 1 i+j=2i_N^\bullet-1 i + j = 2 i N ∙ − 1 , then the DM should stop in state ( i , j , 1 ) (i,j,1) ( i , j , 1 ) . Assume that the second case holds. The DM should reject a candidate in state ( i , j , 2 ) (i,j,2) ( i , j , 2 ) . It follows from the symmetry between i i i and j j j , that for i + j = 2 i N ∙ − 1 i+j=2i_N^\bullet-1 i + j = 2 i N ∙ − 1 the DM should accept a candidate of the type that has been more often observed, but reject a candidate of the type that has been observed less often. It follows that in the second case the trajectory cannot pass from the region in which no candidate is accepted directly into the region in which any candidate is accepted.
Now assume that the first case holds. When starting from state ( i N ∙ , i N ∙ − 2 , 0 ) (i_N^\bullet,i_N^\bullet-2,0) ( i N ∙ , i N ∙ − 2 , 0 ) or ( i N ∙ − 1 , i N ∙ − 1 , 0 ) (i_N^\bullet-1,i_N^\bullet-1,0) ( i N ∙ − 1 , i N ∙ − 1 , 0 ) the DM should always accept the next candidate to appear. It follows from Lemma 5 and (17) that
v i N ∙ , i N ∙ − 2 ≤ v i N ∙ − 1 , i N ∙ − 1 ≤ i N ∙ N . v_{i_N^\bullet,i_N^\bullet-2} \le v_{i_N^\bullet-1,i_N^\bullet-1} \le\frac{i_N^\bullet}{N}. v i N ∙ , i N ∙ − 2 ≤ v i N ∙ − 1 , i N ∙ − 1 ≤ N i N ∙ .
Thus the DM should stop in state ( i N ∙ , i N ∙ − 2 , 1 ) (i_N^\bullet,i_N^\bullet-2,1) ( i N ∙ , i N ∙ − 2 , 1 ) . From Lemma 7 it thus follows that when i + j = 2 ( i N ∙ − 1 ) i+j=2(i_N^\bullet-1) i + j = 2 ( i N ∙ − 1 ) and i ≠ j i\ne j i = j , then a candidate of the type that has been seen more often should be accepted and a candidate of the type that has been seen less often should be rejected. If i = j = i N ∙ − 1 i=j=i_N^\bullet-1 i = j = i N ∙ − 1 , then a candidate should always be rejected. Hence, the trajectory of the search process can only pass directly from the region in which no candidate is accepted to the region in which any candidate is accepted by passing through a state of the form ( i N ∙ − 1 , i N ∙ − 1 , k ) (i_N^\bullet-1,i_N^\bullet-1,k) ( i N ∙ − 1 , i N ∙ − 1 , k ) , k ∈ { 0 , 1 , 2 } k\in\{0,1,2\} k ∈ { 0 , 1 , 2 } .
In the third case, starting in state ( i N ∙ , i N ∙ − 1 , 0 ) (i_N^\bullet,i_N^\bullet-1,0) ( i N ∙ , i N ∙ − 1 , 0 ) it is optimal to accept the next candidate to appear. Hence, from the optimality criterion we obtain
v i N ∙ , i N ∙ − 1 = 1 N + i N ∙ α i N ∙ , i N ∙ − 1 v i N ∙ + 1 , i N ∙ − 1 i N ∙ + 1 + ( i N ∙ − 1 ) ( 1 − α i N ∙ , i N ∙ − 1 ) v i N ∙ , i N ∙ i N ∙ > i N ∙ N . (18) v_{i_N^\bullet,i_N^\bullet-1}
=
\frac{1}{N}
+
\frac{i_N^\bullet\alpha_{i_N^\bullet,i_N^\bullet-1}v_{i_N^\bullet+1,i_N^\bullet-1}}{i_N^\bullet+1}
+
\frac{(i_N^\bullet-1)(1-\alpha_{i_N^\bullet,i_N^\bullet-1})v_{i_N^\bullet,i_N^\bullet}}{i_N^\bullet}
>
\frac{i_N^\bullet}{N}. \tag*{(18)} v i N ∙ , i N ∙ − 1 = N 1 + i N ∙ + 1 i N ∙ α i N ∙ , i N ∙ − 1 v i N ∙ + 1 , i N ∙ − 1 + i N ∙ ( i N ∙ − 1 ) ( 1 − α i N ∙ , i N ∙ − 1 ) v i N ∙ , i N ∙ > N i N ∙ . (18)
From Lemma 6 and (18) it follows that
1 N + i N ∙ v i N ∙ + 1 , i N ∙ − 1 i N ∙ + 1 > i N ∙ N . \frac{1}{N}+\frac{i_N^\bullet v_{i_N^\bullet+1,i_N^\bullet-1}}{i_N^\bullet+1}>\frac{i_N^\bullet}{N}. N 1 + i N ∙ + 1 i N ∙ v i N ∙ + 1 , i N ∙ − 1 > N i N ∙ .
v i N ∙ + 1 , i N ∙ − 1 > ( i N ∙ + 1 ) ( i N ∙ − 1 ) N i N ∙ > i N ∙ − 1 N . v_{i_N^\bullet+1,i_N^\bullet-1}>
\frac{(i_N^\bullet+1)(i_N^\bullet-1)}{Ni_N^\bullet}>
\frac{i_N^\bullet-1}{N}. v i N ∙ + 1 , i N ∙ − 1 > N i N ∙ ( i N ∙ + 1 ) ( i N ∙ − 1 ) > N i N ∙ − 1 .
It follows that the DM should reject a candidate in state ( i N ∙ + 1 , i N ∙ − 1 , 2 ) (i_N^\bullet+1,i_N^\bullet-1,2) ( i N ∙ + 1 , i N ∙ − 1 , 2 ) . From Lemma 7 it thus follows that when i + j = 2 i N ∙ i+j=2i_N^\bullet i + j = 2 i N ∙ and i ≠ j i\ne j i = j , then a candidate of the type that has been seen more often should be accepted and a candidate of the type that has been seen less often should be rejected. If i = j = i N ∙ i=j=i_N^\bullet i = j = i N ∙ , then a candidate should always be accepted. Hence, in the third case, the trajectory of the search process can only pass directly from the region in which no candidate is accepted to the region in which any candidate is accepted by passing through a state of the form ( i N ∙ , i N ∙ , k ) (i_N^\bullet,i_N^\bullet,k) ( i N ∙ , i N ∙ , k ) , k ∈ { 0 , 1 , 2 } k\in\{0,1,2\} k ∈ { 0 , 1 , 2 } .
For the first case to occur, the possible range of values of v i N ∙ − 1 , i N ∙ − 1 v_{i_N^\bullet-1,i_N^\bullet-1} v i N ∙ − 1 , i N ∙ − 1 is relatively small compared to the second case, particularly when N N N is large. From Inequality (18), in the third case the possible range of values of v i N ∙ , i N ∙ v_{i_N^\bullet,i_N^\bullet} v i N ∙ , i N ∙ is relatively small. From the numerical calculations made for N ≥ 3 N\ge3 N ≥ 3 , it was always optimal to stop in state ( i N ∙ , i N ∙ − 1 , 1 ) (i_N^\bullet,i_N^\bullet-1,1) ( i N ∙ , i N ∙ − 1 , 1 ) and continue in state ( i N ∙ , i N ∙ − 1 , 2 ) (i_N^\bullet,i_N^\bullet-1,2) ( i N ∙ , i N ∙ − 1 , 2 ) . The realization of the problem when N = 2 N=2 N = 2 is specific: i 2 ∙ = 2 i_2^\bullet=2 i 2 ∙ = 2 , it is optimal to stop in state ( 2 , 1 , 1 ) (2,1,1) ( 2 , 1 , 1 ) and the DM is indifferent between stopping and continuing in state ( 2 , 1 , 2 ) (2,1,2) ( 2 , 1 , 2 ) .
Theorem 2. For all N N N , i N ∙ = m ( N ) = ⌈ N + 1 2 ⌉ i_N^\bullet=m(N)=\left\lceil\frac{N+1}{2}\right\rceil i N ∙ = m ( N ) = ⌈ 2 N + 1 ⌉ .
The proof of this theorem is technical and is based the following two lemmas.
Lemma 9. For all N ≥ 3 N\ge3 N ≥ 3 , w m ( N ) − 1 , m ( N ) − 1 > m ( N ) − 1 N w_{m(N)-1,m(N)-1}>\frac{m(N)-1}{N} w m ( N ) − 1 , m ( N ) − 1 > N m ( N ) − 1 .
Lemma 10. For all N ≥ 3 N\ge3 N ≥ 3 , w m ( N ) , m ( N ) ≤ m ( N ) N w_{m(N),m(N)}\le\frac{m(N)}{N} w m ( N ) , m ( N ) ≤ N m ( N ) .
From Lemma 9, it follows that i N ∙ ≥ ⌈ N + 1 2 ⌉ i_N^\bullet\ge\left\lceil\frac{N+1}{2}\right\rceil i N ∙ ≥ ⌈ 2 N + 1 ⌉ . Theorem 2 then follows from Lemma 10 and Theorem 1. The proofs of these lemmas are in the appendix.
Combining the results obtained above, we can state the main hypothesis of the paper describing the general form of the optimal strategy. Before doing this, we define an auxiliary trajectory, Q n Q_n Q n , of the trajectory T n = ( U n , V n , M n , R n ) T_n=(U_n,V_n,M_n,R_n) T n = ( U n , V n , M n , R n ) .
Definition 1. Let Q n = ( U n ′ , V n ′ , K n ′ , R n ) Q_n=(U'_n,V'_n,K'_n,R_n) Q n = ( U n ′ , V n ′ , K n ′ , R n ) , where U n ′ = max { U n , V n } U'_n=\max\{U_n,V_n\} U n ′ = max { U n , V n } , V n ′ = min { U n , V n } V'_n=\min\{U_n,V_n\} V n ′ = min { U n , V n } , K n ′ = 1 K'_n=1 K n ′ = 1 if the current object is of the type that has been observed more often (if U n = V n U_n=V_n U n = V n , then define K n = 1 K_n=1 K n = 1 ), otherwise K n ′ = 2 K'_n=2 K n ′ = 2 . As before, R n R_n R n is the relative rank of the n n n -th object to be observed compared to the previously observed objects of the same type. Denote the sequence of realizations of U n ′ U'_n U n ′ and V n ′ V'_n V n ′ , n = 1 , 2 , … , 2 N n=1,2,\ldots,2N n = 1 , 2 , … , 2 N by { ( i n , j n ) } 1 ≤ n ≤ 2 N \{(i_n,j_n)\}_{1\le n\le2N} {( i n , j n ) } 1 ≤ n ≤ 2 N , where ( i 1 , j 1 ) = ( 1 , 0 ) (i_1,j_1)=(1,0) ( i 1 , j 1 ) = ( 1 , 0 ) and i 2 N = j 2 N = N i_{2N}=j_{2N}=N i 2 N = j 2 N = N .
Theorem 3. Any auxiliary trajectory can be split into three subtrajectories: i) Q 1 , … , Q μ − 1 Q_1,\ldots,Q_{\mu-1} Q 1 , … , Q μ − 1 , ii) Q μ , … , Q λ − 1 Q_\mu,\ldots,Q_{\lambda-1} Q μ , … , Q λ − 1 and iii) Q λ , Q λ + 1 , … , Q 2 N Q_\lambda,Q_{\lambda+1},\ldots,Q_{2N} Q λ , Q λ + 1 , … , Q 2 N , such is always optimal to continue when n < μ n<\mu n < μ . For μ ≤ n < λ \mu\le n<\lambda μ ≤ n < λ , it is optimal to accept a candidate of the type that has appeared most often when such a candidate appears at moment n n n . For n ≥ λ n\ge\lambda n ≥ λ , it is optimal for the DM to accept a candidate of either type. The random time μ \mu μ denotes the moment at which it first becomes optimal to accept a candidate of the type that has been observed more often. Similarly, λ \lambda λ denotes the moment at which it first becomes optimal to accept a candidate of either type. The random time μ \mu μ corresponds to the first n n n that satisfies v i n , j n ≤ i n N v_{i_n,j_n}\le\frac{i_n}{N} v i n , j n ≤ N i n . The random time λ \lambda λ corresponds to the first n n n that satisfies v i n , j n ≤ j n N v_{i_n,j_n}\le\frac{j_n}{N} v i n , j n ≤ N j n . The optimal strategy of the DM is to reject any candidate when n < μ n<\mu n < μ , accept only a candidate of the type to have appeared more often when μ ≤ n < λ \mu\le n<\lambda μ ≤ n < λ and accept a candidate of either type when n ≥ λ n\ge\lambda n ≥ λ .
Remark 3. Note that by definition μ ≤ λ \mu\le\lambda μ ≤ λ .
Corollary to Theorem 3: Suppose that i i i objects of type 1 and j j j objects of type 2 have appeared, 0 ≤ i , j ≤ N 0\le i,j\le N 0 ≤ i , j ≤ N . The pairs ( i , j ) (i,j) ( i , j ) can be partitioned into the following four sets:
The set of pairs ( i , j ) (i,j) ( i , j ) such that any object should be rejected in state ( i , j , k ) (i,j,k) ( i , j , k ) , k ∈ { 0 , 1 , 2 } k\in\{0,1,2\} k ∈ { 0 , 1 , 2 } . This set will be denoted by C 0 N C^N_0 C 0 N . For ( i , j ) ∈ C 0 N (i,j)\in C^N_0 ( i , j ) ∈ C 0 N , v i , j > max { i N , j N } v_{i,j}>\max\{\frac{i}{N},\frac{j}{N}\} v i , j > max { N i , N j } .
The set of pairs ( i , j ) (i,j) ( i , j ) such that an object should be accepted in state ( i , j , 1 ) (i,j,1) ( i , j , 1 ) , but rejected in states ( i , j , 0 ) (i,j,0) ( i , j , 0 ) and ( i , j , 2 ) (i,j,2) ( i , j , 2 ) . This set will be denoted by C 1 N C^N_1 C 1 N . Thus only candidates of type 1 are accepted in this region. For ( i , j ) ∈ C 1 N (i,j)\in C^N_1 ( i , j ) ∈ C 1 N , i > j i>j i > j and j N < v i , j ≤ i N \frac{j}{N}<v_{i,j}\le\frac{i}{N} N j < v i , j ≤ N i .
The set of pairs ( i , j ) (i,j) ( i , j ) such that an object should be accepted in state ( i , j , 2 ) (i,j,2) ( i , j , 2 ) , but rejected in states ( i , j , 0 ) (i,j,0) ( i , j , 0 ) and ( i , j , 1 ) (i,j,1) ( i , j , 1 ) . This set will be denoted by C 2 N C^N_2 C 2 N . Thus only candidates of type 2 are accepted in this region. For ( i , j ) ∈ C 2 N (i,j)\in C^N_2 ( i , j ) ∈ C 2 N , j > i j>i j > i and i N < v i , j ≤ j N \frac{i}{N}<v_{i,j}\le\frac{j}{N} N i < v i , j ≤ N j .
The set of pairs ( i , j ) (i,j) ( i , j ) such that an object should be accepted in states ( i , j , 1 ) (i,j,1) ( i , j , 1 ) and ( i , j , 2 ) (i,j,2) ( i , j , 2 ) , but rejected in state ( i , j , 0 ) (i,j,0) ( i , j , 0 ) . This set will be denoted by C 3 N C^N_3 C 3 N . Thus candidates of either type are accepted in this region. For ( i , j ) ∈ C 3 N (i,j)\in C^N_3 ( i , j ) ∈ C 3 N , v i , j ≤ min { i N , j N } v_{i,j}\le\min\{\frac{i}{N},\frac{j}{N}\} v i , j ≤ min { N i , N j } .
Remark 4. All trajectories start in C 0 N C^N_0 C 0 N and pass at moment, μ \mu μ , into either C 1 N C^N_1 C 1 N (when i μ > j μ i_\mu>j_\mu i μ > j μ ) or C 2 N C^N_2 C 2 N (when i μ < j μ i_\mu<j_\mu i μ < j μ ). At moment λ \lambda λ , where λ ≥ μ \lambda\ge\mu λ ≥ μ , the trajectory passes into C 3 N C^N_3 C 3 N and remains in this set. If λ = μ \lambda=\mu λ = μ , then the trajectory passes directly from C 0 N C^N_0 C 0 N to C 3 N C^N_3 C 3 N .
Remark 5. For convenience, it is assumed that any artificial object observed in the artificial states ( 0 , 0 , k ) (0,0,k) ( 0 , 0 , k ) , ( i , 0 , 2 ) (i,0,2) ( i , 0 , 2 ) or ( 0 , j , 1 ) (0,j,1) ( 0 , j , 1 ) is rejected.
Remark 6. The set C 3 N C^N_3 C 3 N is very similar, but not identical, to the set B 3 N B^N_3 B 3 N . If ( i , j ) ∈ B 3 N (i,j)\in B^N_3 ( i , j ) ∈ B 3 N , then starting in state $(i,j,0) it is always optimal to stop when the next candidate appears. However, there will be cases where it is not optimal to stop in state ( i , j , 1 ) (i,j,1) ( i , j , 1 ) or in state ( i , j , 2 ) (i,j,2) ( i , j , 2 ) . If ( i , j ) ∈ C 3 N (i,j)\in C^N_3 ( i , j ) ∈ C 3 N , then starting in state ( i , j , 0 ) (i,j,0) ( i , j , 0 ) , it is always optimal to accept the next candidate to appear. Hence, C 3 N ⊂ B 3 N C^N_3\subset B^N_3 C 3 N ⊂ B 3 N . Also, when ( i , j ) ∉ C 3 N (i,j)\notin C^N_3 ( i , j ) ∈ / C 3 N , then ( i , j ) ∈ B 3 N (i,j)\in B^N_3 ( i , j ) ∈ B 3 N if and only if ( i + 1 , j ) ∈ C 3 N (i+1,j)\in C^N_3 ( i + 1 , j ) ∈ C 3 N and ( i , j + 1 ) ∈ C 3 N (i,j+1)\in C^N_3 ( i , j + 1 ) ∈ C 3 N .
The form of the optimal strategy is illustrated in Figure 1 .
Figure 1. Asymptotic Form of the Optimal Strategy
Asymptotic form of the Optimal Strategy
Let v ( s , t ) v(s,t) v ( s , t ) be the expected reward when a proportion s s s of objects of type 1 and a proportion t t t of objects of type 2 have been rejected. Define ( s , t , k ) (s,t,k) ( s , t , k ) to be the state of the process, where k = 0 k=0 k = 0 if the present object is not a candidate and when k = 1 , 2 k = 1, 2 k = 1 , 2 then the present object is a candidate of type k k k . We wish to derive an integral equation from which we can derive the value function v v v . According to the form of the optimal strategy for finite N N N , a candidate of type 1 should be accepted in state ( i , j , 1 ) (i,j,1) ( i , j , 1 ) when i ≥ i ∗ ( j ) i \ge i^{*}(j) i ≥ i ∗ ( j ) . When N → ∞ N \to\infty N → ∞ , this corresponds to a candidate of type 1 being accepted in state ( s , t , 1 ) (s,t,1) ( s , t , 1 ) when s ≥ s ∗ ( t ) s \ge s^{*}(t) s ≥ s ∗ ( t ) . Analogously, a candidate of type 1 should be accepted in state ( s , t , 2 ) (s,t,2) ( s , t , 2 ) if and only if t ≥ t ∗ ( s ) t \ge t^{*}(s) t ≥ t ∗ ( s ) , where s ∗ ≡ t ∗ s^{*} \equiv t^{*} s ∗ ≡ t ∗ .
By symmetry, we have v ( s , t ) = v ( t , s ) v(s,t) = v(t,s) v ( s , t ) = v ( t , s ) , thus without loss of generality we can assume that s ≤ t s \le t s ≤ t . First, we derive v ( s , t ) v(s,t) v ( s , t ) for the set of states ( s , t ) (s,t) ( s , t ) such that the decision maker should accept the next relatively best object to appear, regardless of which type it is. In the limit, the rate at which items of type 2 appear is ( 1 − t ) / ( 1 − s ) (1-t)/(1-s) ( 1 − t ) / ( 1 − s ) times the rate at which items of type 1 appear, i.e. the ratio of the proportion of type 2 objects that have not appeared to the proportion of type 1 objects that have not appeared. Hence, starting from the state ( s , t , 0 ) (s,t,0) ( s , t , 0 ) , we can define the time u u u to be the proportion of objects of type 1 that have appeared. Suppose that the next candidate (of either type) appears at time u u u . From the definitions made above, the state at this point is given by
[ u , t + ( u − s ) ( 1 − t ) 1 − s ] , k , (19) \left[u,t+\frac{(u-s)(1-t)}{1-s}\right],k, \tag*{(19)} [ u , t + 1 − s ( u − s ) ( 1 − t ) ] , k , (19)
where k = 1 k = 1 k = 1 if this relatively best object is of type 1, otherwise k = 2 k = 2 k = 2 .
From Ferguson [3], the density function of the time u u u at which the next relatively best object of type 1 appears is given by f 1 ( u ; s ) = s / u 2 f_1(u;s) = s/u^2 f 1 ( u ; s ) = s / u 2 , for s ≤ u ≤ 1 s \le u \le1 s ≤ u ≤ 1 . Note that the event that no relatively best object of type 1 appears after time s s s is equivalent to the event that the absolutely best object of type 1 appears before s s s , i.e. the probability of this event is s s s . Based on the appropriate scaling of time, the density function of the time at which the next relatively best object of type 2 appears is obtained by multiplying the density function of the time at which a candidate of type 2 appears according to the scaled time, f 1 ( t + ( u − s ) ( 1 − t ) 1 − s ; t ) f_1\left(t+\frac{(u-s)(1-t)}{1-s};t\right) f 1 ( t + 1 − s ( u − s ) ( 1 − t ) ; t ) , by the scaled rate of appearance of such candidates, i.e.
f 2 ( u ; t ) = f 1 ( t + ( u − s ) ( 1 − t ) 1 − s ; t ) 1 − t 1 − s = t ( 1 − t ) ( 1 − s ) [ t ( 1 − s ) + ( u − s ) ( 1 − t ) ] 2 . f_2(u;t)=f_1\left(t+\frac{(u-s)(1-t)}{1-s};t\right)\frac{1-t}{1-s}=\frac{t(1-t)(1-s)}{[t(1-s)+(u-s)(1-t)]^2}. f 2 ( u ; t ) = f 1 ( t + 1 − s ( u − s ) ( 1 − t ) ; t ) 1 − s 1 − t = [ t ( 1 − s ) + ( u − s ) ( 1 − t ) ] 2 t ( 1 − t ) ( 1 − s ) .
From the above considerations, given that the next relatively best object of type 2 (type 1, respectively) appears at time x x x , the probability that it is the next candidate of either type to appear [i.e. no relatively best object of the other type has appeared in the time interval ( s , x ) (s,x) ( s , x ) ] is given by p 2 ( x ; s , t ) p_2(x;s,t) p 2 ( x ; s , t ) (p 1 ( x ; s , t ) p_1(x;s,t) p 1 ( x ; s , t ) , respectively), where
p 2 ( x ; s , t ) = s x ; p 1 ( x ; s , t ) = t t + { ( x − s ) ( 1 − t ) / ( 1 − s ) } = t ( 1 − s ) t ( 1 − s ) + ( x − s ) ( 1 − t ) . p_2(x;s,t)=\frac{s}{x};\quad p_1(x;s,t)=\frac{t}{t+\{(x-s)(1-t)/(1-s)\}}=\frac{t(1-s)}{t(1-s)+(x-s)(1-t)}. p 2 ( x ; s , t ) = x s ; p 1 ( x ; s , t ) = t + {( x − s ) ( 1 − t ) / ( 1 − s )} t = t ( 1 − s ) + ( x − s ) ( 1 − t ) t ( 1 − s ) .
The density function of the time to the appearance of a relatively best object from either ordering is given by f ( x ; s , t ) f(x;s,t) f ( x ; s , t ) , where f ( x ; s , t ) = f 1 ( x ; s , t ) p 1 ( x ; s , t ) + f 2 ( x ; s , t ) p 2 ( x ; s , t ) f(x;s,t)=f_1(x;s,t)p_1(x;s,t)+f_2(x;s,t)p_2(x;s,t) f ( x ; s , t ) = f 1 ( x ; s , t ) p 1 ( x ; s , t ) + f 2 ( x ; s , t ) p 2 ( x ; s , t ) . Define r 1 ( x ; s , t ) = f 1 ( x ; s , t ) p 1 ( x ; s , t ) r_1(x;s,t)=f_1(x;s,t)p_1(x;s,t) r 1 ( x ; s , t ) = f 1 ( x ; s , t ) p 1 ( x ; s , t ) and r 2 ( x ; s , t ) = f 2 ( x ; s , t ) p 2 ( x ; s , t ) r_2(x;s,t)=f_2(x;s,t)p_2(x;s,t) r 2 ( x ; s , t ) = f 2 ( x ; s , t ) p 2 ( x ; s , t ) .
Given that the next relatively best object appears at time u u u , if it is of type 1 (type 2, respectively), it is the absolutely best object of type 1 (of type 2, respectively) with probability u [ t + ( u − s ) ( 1 − t ) 1 − s ] u\left[t+\frac{(u-s)(1-t)}{1-s}\right] u [ t + 1 − s ( u − s ) ( 1 − t ) ] , respectively. Given that the appearance time of the next relatively best object is u u u , the probability that it is of type 1 is r 1 ( u ; s , t ) r 1 ( u ; s , t ) + r 2 ( u ; s , t ) \frac{r_1(u;s,t)}{r_1(u;s,t)+r_2(u;s,t)} r 1 ( u ; s , t ) + r 2 ( u ; s , t ) r 1 ( u ; s , t ) . It follows that on the region where the next relatively best object should be accepted, the value function is given by
v ( s , t ) = ∫ s 1 [ u r 1 ( u ; s , t ) r 1 ( u ; s , t ) + r 2 ( u ; s , t ) + [ t ( 1 − s ) + ( u − s ) ( 1 − t ) ] r 2 ( u ; s , t ) ( 1 − s ) [ r 1 ( u ; s , t ) + r 2 ( u ; s , t ) ] ] f ( u ; s , t ) d u = ∫ s 1 [ u r 1 ( u ; s , t ) + t ( 1 − s ) + ( u − s ) ( 1 − t ) 1 − s r 2 ( u ; s , t ) ] d u = ∫ s 1 [ s t ( 2 − s − t ) u [ t ( 1 − s ) + ( u − s ) ( 1 − t ) ] ] d u . (20) \begin{aligned}
v(s,t) &= \int_s^1 \left[\frac{ur_1(u;s,t)}{r_1(u;s,t)+r_2(u;s,t)}+\frac{[t(1-s)+(u-s)(1-t)]r_2(u;s,t)}{(1-s)[r_1(u;s,t)+r_2(u;s,t)]}\right]f(u;s,t)\,du \\
&= \int_s^1 \left[ur_1(u;s,t)+\frac{t(1-s)+(u-s)(1-t)}{1-s}r_2(u;s,t)\right]\,du \\
&= \int_s^1 \left[\frac{st(2-s-t)}{u[t(1-s)+(u-s)(1-t)]}\right]\,du. \tag*{(20)}
\end{aligned} v ( s , t ) = ∫ s 1 [ r 1 ( u ; s , t ) + r 2 ( u ; s , t ) u r 1 ( u ; s , t ) + ( 1 − s ) [ r 1 ( u ; s , t ) + r 2 ( u ; s , t )] [ t ( 1 − s ) + ( u − s ) ( 1 − t )] r 2 ( u ; s , t ) ] f ( u ; s , t ) d u = ∫ s 1 [ u r 1 ( u ; s , t ) + 1 − s t ( 1 − s ) + ( u − s ) ( 1 − t ) r 2 ( u ; s , t ) ] d u = ∫ s 1 [ u [ t ( 1 − s ) + ( u − s ) ( 1 − t )] s t ( 2 − s − t ) ] d u . (20)
First, we consider the case s = t s=t s = t . From Equation (20) , we obtain
v ( s , s ) = ∫ s 1 2 s 2 u 2 d u = 2 s ( 1 − s ) . v(s,s)=\int_s^1 \frac{2s^2}{u^2}\,du=2s(1-s). v ( s , s ) = ∫ s 1 u 2 2 s 2 d u = 2 s ( 1 − s ) .
Suppose a relatively best object of either type appears in state ( s , s , k ) (s,s,k) ( s , s , k ) , k = 1 , 2 k=1,2 k = 1 , 2 . Since such a candidate is the absolute best of its type with probability s s s , it should be accepted if and only if s ≥ 2 s ( 1 − s ) s\ge2s(1-s) s ≥ 2 s ( 1 − s ) , i.e. s ≥ 1 / 2 s\ge1/2 s ≥ 1/2 .
When s < t s<t s < t , decomposing the integrand in Equation (20) into partial fractions and integrating, we obtain
v ( s , t ) = s t ( 2 − s − t ) [ ln ( t ) − ln ( s ) ] t − s . v(s,t)=\frac{st(2-s-t)[\ln(t)-\ln(s)]}{t-s}. v ( s , t ) = t − s s t ( 2 − s − t ) [ ln ( t ) − ln ( s )] .
If a relatively best object should be accepted in state ( s , t , 1 ) (s,t,1) ( s , t , 1 ) , then it should be accepted in state ( s , t , 2 ) (s,t,2) ( s , t , 2 ) . It follows that any relatively best object should be accepted if and only if
s ≥ s t ( 2 − s − t ) [ ln ( t ) − ln ( s ) ] t − s . s\ge\frac{st(2-s-t)[\ln(t)-\ln(s)]}{t-s}. s ≥ t − s s t ( 2 − s − t ) [ ln ( t ) − ln ( s )] .
It follows that for s < t s<t s < t , the boundary of the region in which any relatively best object should be accepted is given by the implicit function
1 = t ( 2 − s − t ) [ ln ( t ) − ln ( s ) ] t − s . (21) 1=\frac{t(2-s-t)[\ln(t)-\ln(s)]}{t-s}. \tag*{(21)} 1 = t − s t ( 2 − s − t ) [ ln ( t ) − ln ( s )] . (21)
Hence, for a fixed t t t , t > 0.5 t>0.5 t > 0.5 , then a candidate should be accepted in state ( s , t , 1 ) (s,t,1) ( s , t , 1 ) , when s ≥ s ∗ ( t ) s\ge s^*(t) s ≥ s ∗ ( t ) , where s ∗ ( t ) s^*(t) s ∗ ( t ) satisfies Equation (21) . Since s < t s<t s < t , a candidate should also be accepted in state ( s , t , 2 ) (s,t,2) ( s , t , 2 ) .
Now suppose that ( s , t ) (s,t) ( s , t ) is in the region where only relatively best objects of type 2 should be accepted. In order to obtain an integral equation for v ( s , t ) v(s,t) v ( s , t ) , we consider the following two events:
No relatively best object of type 2 appears before relatively best objects of type 1 become acceptable.
A relatively best object of type 2 appears before relatively best objects of type 1 become acceptable.
Starting from the state ( s , t , 0 ) (s,t,0) ( s , t , 0 ) , given that no relatively best object of type 2 appears, in the limit the process will enter the region in which any relatively best object will be accepted in the state [ k ( s , t ) , t + [ k ( s , t ) − s ] ( 1 − t ) 1 − s , 0 ] \left[k(s,t),t+\frac{[k(s,t)-s](1-t)}{1-s},0\right] [ k ( s , t ) , t + 1 − s [ k ( s , t ) − s ] ( 1 − t ) , 0 ] , where
v ( k ( s , t ) , t + [ k ( s , t ) − s ] ( 1 − t ) 1 − s ) = k ( s , t ) . v\left(k(s,t),t+\frac{[k(s,t)-s](1-t)}{1-s}\right)=k(s,t). v ( k ( s , t ) , t + 1 − s [ k ( s , t ) − s ] ( 1 − t ) ) = k ( s , t ) .
The probability that no such relatively best object appears is t ( 1 − s ) t ( 1 − s ) + [ k ( s , t ) − s ] ( 1 − t ) \frac{t(1-s)}{t(1-s)+[k(s,t)-s](1-t)} t ( 1 − s ) + [ k ( s , t ) − s ] ( 1 − t ) t ( 1 − s ) . Now we scale time such that the proportion of objects of type 2 that have appeared at time t t t is simply t t t . Considering the density function of the time x x x at which the next relatively best object of type 2 appears, since the probability that such an object is the absolute best of the objects of type 2 is x x x , we obtain
v ( s , t ) = ∫ t t ( 1 − s ) + [ k ( s , t ) − s ] ( 1 − t ) 1 − s t x d x + t ( 1 − s ) k ( s , t ) t ( 1 − s ) + [ k ( s , t ) − s ] ( 1 − t ) = t ln [ t ( 1 − s ) + [ k ( s , t ) − s ] ( 1 − t ) t ( 1 − s ) ] + t ( 1 − s ) k ( s , t ) t ( 1 − s ) + [ k ( s , t ) − s ] ( 1 − t ) . (22) \begin{aligned}
v(s,t) &= \int_t^{\frac{t(1-s)+[k(s,t)-s](1-t)}{1-s}} \frac{t}{x}\,dx+\frac{t(1-s)k(s,t)}{t(1-s)+[k(s,t)-s](1-t)} \\
&=t\ln\left[\frac{t(1-s)+[k(s,t)-s](1-t)}{t(1-s)}\right]+\frac{t(1-s)k(s,t)}{t(1-s)+[k(s,t)-s](1-t)}. \tag*{(22)}
\end{aligned} v ( s , t ) = ∫ t 1 − s t ( 1 − s ) + [ k ( s , t ) − s ] ( 1 − t ) x t d x + t ( 1 − s ) + [ k ( s , t ) − s ] ( 1 − t ) t ( 1 − s ) k ( s , t ) = t ln [ t ( 1 − s ) t ( 1 − s ) + [ k ( s , t ) − s ] ( 1 − t ) ] + t ( 1 − s ) + [ k ( s , t ) − s ] ( 1 − t ) t ( 1 − s ) k ( s , t ) . (22)
The lower boundary of the region in which only objects of type 2 are accepted satisfies the equation t = v ( s , t ) t = v(s,t) t = v ( s , t ) . Hence, this lower boundary is given by the implicit function
1 = ln [ t ( 1 − s ) + [ k ( s , t ) − s ] ( 1 − t ) t ( 1 − s ) ] + ( 1 − s ) k ( s , t ) t ( 1 − s ) + [ k ( s , t ) − s ] ( 1 − t ) . (23) 1 = \ln\left[\frac{t(1-s) + [k(s,t)-s](1-t)}{t(1-s)}\right] + \frac{(1-s)k(s,t)}{t(1-s) + [k(s,t)-s](1-t)}. \tag*{(23)} 1 = ln [ t ( 1 − s ) t ( 1 − s ) + [ k ( s , t ) − s ] ( 1 − t ) ] + t ( 1 − s ) + [ k ( s , t ) − s ] ( 1 − t ) ( 1 − s ) k ( s , t ) . (23)
Below this curve, the decision maker does not accept any object. It follows that in this region the value function at a given point is equal to the time when the limiting process intersects the region in which relatively best objects from ordering 2 become acceptable. It follows that v ( s , t ) = v ( c ( s , t ) , t + [ c ( s , t ) − t ] [ 1 − t ] 1 − s ) v(s,t)=v\left(c(s,t),t+\frac{[c(s,t)-t][1-t]}{1-s}\right) v ( s , t ) = v ( c ( s , t ) , t + 1 − s [ c ( s , t ) − t ] [ 1 − t ] ) , where c ( s , t ) c(s,t) c ( s , t ) satisfies
v ( c ( s , t ) , t + [ c ( s , t ) − t ] [ 1 − t ] 1 − s ) = t + [ c ( s , t ) − t ] [ 1 − t ] 1 − s . v\left(c(s,t),t+\frac{[c(s,t)-t][1-t]}{1-s}\right)=t+\frac{[c(s,t)-t][1-t]}{1-s}. v ( c ( s , t ) , t + 1 − s [ c ( s , t ) − t ] [ 1 − t ] ) = t + 1 − s [ c ( s , t ) − t ] [ 1 − t ] .
Since the upper boundary of this region is given by an implicit function, numerical estimation of the general form of the function is complex. However, it is relatively simple to estimate v ( s , t ) v(s,t) v ( s , t ) for specified values of s s s and t t t . In particular, the optimal expected reward is given by v ( 0 , 0 ) v(0,0) v ( 0 , 0 ) . In the limit, the trajectory of the process moves along the line s = t s=t s = t . Moving along such a trajectory, the DM should accept the first candidate to appear when s ≥ 0.5 s \ge0.5 s ≥ 0.5 . It follows that the optimal expected reward is v ( 0.5 , 0.5 ) = 0.5 v(0.5,0.5)=0.5 v ( 0.5 , 0.5 ) = 0.5 .
In addition, note that any relatively best object of type 2 should always be accepted when t ≥ t ∗ ( 0 ) t \ge t^*(0) t ≥ t ∗ ( 0 ) , even if no objects of type 1 have be observed. We can estimate t ∗ ( 0 ) t^*(0) t ∗ ( 0 ) , using t ∗ ( 0 ) = v ( 0 , t ∗ ( 0 ) ) t^*(0)=v(0,t^*(0)) t ∗ ( 0 ) = v ( 0 , t ∗ ( 0 )) . From Equation (22) , it follows that
1 = ln { t ∗ ( 0 ) + [ 1 − t ∗ ( 0 ) ] k ( 0 , t ∗ ( 0 ) ) t ∗ ( 0 ) } + k ( 0 , t ∗ ( 0 ) ) t ∗ ( 0 ) + [ 1 − t ∗ ( 0 ) ] k ( 0 , t ∗ ( 0 ) ) . (24) 1 = \ln\left\{\frac{t^*(0)+[1-t^*(0)]k(0,t^*(0))}{t^*(0)}\right\}+\frac{k(0,t^*(0))}{t^*(0)+[1-t^*(0)]k(0,t^*(0))}. \tag*{(24)} 1 = ln { t ∗ ( 0 ) t ∗ ( 0 ) + [ 1 − t ∗ ( 0 )] k ( 0 , t ∗ ( 0 )) } + t ∗ ( 0 ) + [ 1 − t ∗ ( 0 )] k ( 0 , t ∗ ( 0 )) k ( 0 , t ∗ ( 0 )) . (24)
Given that no object is chosen, then starting from the state ( 0 , t ∗ ( 0 ) , 0 ) (0,t^*(0),0) ( 0 , t ∗ ( 0 ) , 0 ) the limiting process will cross into the region where any relatively best object will be accepted in state ( s ∗ ( t ~ ) , t ~ , 0 ) (s^*(\tilde{t}),\tilde{t},0) ( s ∗ ( t ~ ) , t ~ , 0 ) , where
t ~ = t ∗ ( 0 ) + [ 1 − t ∗ ( 0 ) ] s ∗ ( t ~ ) (25) \tilde{t}=t^*(0)+[1-t^*(0)]s^*(\tilde{t}) \tag*{(25)} t ~ = t ∗ ( 0 ) + [ 1 − t ∗ ( 0 )] s ∗ ( t ~ ) (25)
and v ( s ∗ ( t ~ ) , t ~ ) = s ∗ ( t ~ ) v(s^*(\tilde{t}),\tilde{t})=s^*(\tilde{t}) v ( s ∗ ( t ~ ) , t ~ ) = s ∗ ( t ~ ) , which together with Equation (21) leads to
1 = t ~ ( 2 − s ∗ ( t ~ ) − t ~ ) [ ln ( t ~ ) − ln ( s ∗ ( t ~ ) ) ] t ~ − s ∗ ( t ~ ) . (26) 1=\frac{\tilde{t}(2-s^*(\tilde{t})-\tilde{t})[\ln(\tilde{t})-\ln(s^*(\tilde{t}))]}{\tilde{t}-s^*(\tilde{t})}. \tag*{(26)} 1 = t ~ − s ∗ ( t ~ ) t ~ ( 2 − s ∗ ( t ~ ) − t ~ ) [ ln ( t ~ ) − ln ( s ∗ ( t ~ ))] . (26)
Equations (24)-(26) were solved numerically using the dfsane procedure in the BB package written for R (see Varadhan and Gilbert [27 ] ). We obtain t ∗ ( 0 ) ≈ 0.5082004 t^*(0)\approx0.5082004 t ∗ ( 0 ) ≈ 0.5082004 and starting from the state ( 0 , t ∗ ( 0 ) , 0 ) (0,t^*(0),0) ( 0 , t ∗ ( 0 ) , 0 ) , the limiting process crosses into the region where any relatively best object will be accepted at the point ( s ∗ ( t ~ ) , t ~ ) ≈ ( 0.4633848 , 0.7360929 ) (s^*(\tilde{t}),\tilde{t})\approx(0.4633848,0.7360929) ( s ∗ ( t ~ ) , t ~ ) ≈ ( 0.4633848 , 0.7360929 ) .
It should be noted that solving the discrete time problem with N ≥ 10 000 N \ge10\,000 N ≥ 10 000 gives (for the purposes of visualization) a reasonable approximation to the asymptotic solution of the problem. For example, suppose N = 10 000 N=10\,000 N = 10 000 . If no objects of type 1 have been seen, then a relatively best object of type 2 should be accepted if and only if at least 5 083 objects of type 2 have appeared. Figure 1 illustrates the asymptotic form of the solution, estimated on this basis.
Conclusion
This paper has considered a secretary problem, a stopping problem, in which there are an equal number of objects of two different types. Objects of a given type can be fully ranked, but objects of different types cannot be compared. The goal of the DM is choose an object which is the absolute best of its type. Any particular realization of such a problem can be solved using dynamic programming. Some stopping problems can be solved using the concept of a one-step look-ahead rule (OSLAR). Under such a rule, a DM stops if and only if the expected reward from stopping at the current decision point is at least as great as the expected reward from stopping at the next decision point. It was argued that the optimal solution to the problem considered is not an OSLAR. However, given that the process has not yet been stopped, eventually it passes into a region where it is optimal to apply such a rule.
The form of the optimal strategy was then derived by combining the approaches of dynamic programming and the theory of OSLAR. A particularly strong result on whether or not a candidate should be accepted in state ( i , i , 1 ) (i,i,1) ( i , i , 1 ) was given. This was followed by a number of results on the asymptotical solution when the number of objects of both types tends to infinity.
There are a number of other directions for future research. One could relax the assumption that the number of objects of both types are equal. Suppose there are N i N_i N i objects of type i i i , i = 1 , 2 i=1,2 i = 1 , 2 . One could then derive asymptotic results for the case where N 2 = k N 1 N_2=kN_1 N 2 = k N 1 and N 1 , N 2 → ∞ N_1,N_2 \to\infty N 1 , N 2 → ∞ . One could also increase the number of types of object available. This would increase the complexity of the problem. However, it is likely that the methods applied here could be also used, or adapted, in such problems. One could also look at similar problems in which the DM has a different goal (e.g. to choose one of the two best objects of a type).
Proof of Lemma 5
Let $0 \le a \le b \le c \le d \le N$, such that a + d = b + c = n a+d=b+c=n a + d = b + c = n and ( a , d ) ≠ ( b , c ) (a,d) \ne(b,c) ( a , d ) = ( b , c ) . Then w a , d ≤ w b , c w_{a,d} \le w_{b,c} w a , d ≤ w b , c .
Proof. Note that from the definition of a a a , b b b , c c c , d d d then a ≤ d − 2 a \le d-2 a ≤ d − 2 . We shall use recursion with respect to n n n . From the symmetry of the problem w N − 1 , N = w N , N − 1 w_{N-1,N}=w_{N,N-1} w N − 1 , N = w N , N − 1 . The largest relevant value of n n n is 2 N − 2 2N-2 2 N − 2 . Assume that a = N − 2 , d = N a=N-2,d=N a = N − 2 , d = N . In this case we have
w N − 1 , N − 1 = 1 N + N − 1 N w N − 1 , N = 1 N + N − 1 N ⋅ 1 N ≥ 1 N + N − 2 N − 1 ⋅ 1 N = w N − 2 , N . \begin{aligned}
w_{N-1,N-1} &= \frac{1}{N}+\frac{N-1}{N}w_{N-1,N}=\frac{1}{N}+\frac{N-1}{N}\cdot\frac{1}{N}\\
&\ge\frac{1}{N}+\frac{N-2}{N-1}\cdot\frac{1}{N}=w_{N-2,N}.
\end{aligned} w N − 1 , N − 1 = N 1 + N N − 1 w N − 1 , N = N 1 + N N − 1 ⋅ N 1 ≥ N 1 + N − 1 N − 2 ⋅ N 1 = w N − 2 , N .
Hence our claim is true for n = 2 N − 2 n=2N-2 n = 2 N − 2 .
For the rest of the proof, we first show that for 0 ≤ a ≤ d − 2 ≤ N − 2 0 \le a \le d-2 \le N-2 0 ≤ a ≤ d − 2 ≤ N − 2
N − a − 1 2 N − a − d a + 1 a + 2 + N − d + 1 2 N − a − d d − 1 d ≥ N − a 2 N − a − d a a + 1 + N − d 2 N − a − d d d + 1 . (27) \frac{N-a-1}{2N-a-d}\frac{a+1}{a+2}+\frac{N-d+1}{2N-a-d}\frac{d-1}{d}\ge\frac{N-a}{2N-a-d}\frac{a}{a+1}+\frac{N-d}{2N-a-d}\frac{d}{d+1}. \tag*{(27)} 2 N − a − d N − a − 1 a + 2 a + 1 + 2 N − a − d N − d + 1 d d − 1 ≥ 2 N − a − d N − a a + 1 a + 2 N − a − d N − d d + 1 d . (27)
Let
f ( a , d ) = N − a − 1 2 N − a − d a + 1 a + 2 + N − d + 1 2 N − a − d d − 1 d − N − a 2 N − a − d a a + 1 − N − d 2 N − a − d d d + 1 . f(a,d)=\frac{N-a-1}{2N-a-d}\frac{a+1}{a+2}+\frac{N-d+1}{2N-a-d}\frac{d-1}{d}-\frac{N-a}{2N-a-d}\frac{a}{a+1}-\frac{N-d}{2N-a-d}\frac{d}{d+1}. f ( a , d ) = 2 N − a − d N − a − 1 a + 2 a + 1 + 2 N − a − d N − d + 1 d d − 1 − 2 N − a − d N − a a + 1 a − 2 N − a − d N − d d + 1 d .
We have
f ( a , d ) = N − a 2 N − a − d [ a + 1 a + 2 − a a + 1 ] + N − d 2 N − a − d [ d − 1 d − d d + 1 ] + 1 2 N − a − d [ d − 1 d − a + 1 a + 2 ] ≥ N − a 2 N − a − d ⋅ 1 ( a + 1 ) ( a + 2 ) − N − d 2 N − a − d ⋅ 1 d ( d + 1 ) ≥ 0. \begin{aligned}
f(a,d)={}&\frac{N-a}{2N-a-d}\left[\frac{a+1}{a+2}-\frac{a}{a+1}\right]+\frac{N-d}{2N-a-d}\left[\frac{d-1}{d}-\frac{d}{d+1}\right]\\
&+\frac{1}{2N-a-d}\left[\frac{d-1}{d}-\frac{a+1}{a+2}\right]\\
\ge{}&\frac{N-a}{2N-a-d}\cdot\frac{1}{(a+1)(a+2)}-\frac{N-d}{2N-a-d}\cdot\frac{1}{d(d+1)}\ge0.
\end{aligned} f ( a , d ) = ≥ 2 N − a − d N − a [ a + 2 a + 1 − a + 1 a ] + 2 N − a − d N − d [ d d − 1 − d + 1 d ] + 2 N − a − d 1 [ d d − 1 − a + 2 a + 1 ] 2 N − a − d N − a ⋅ ( a + 1 ) ( a + 2 ) 1 − 2 N − a − d N − d ⋅ d ( d + 1 ) 1 ≥ 0.
Assume now that the recursion hypothesis is true for some n = a + d + 1 n=a+d+1 n = a + d + 1 , where 1 ≤ n ≤ 2 N − 2 1 \le n \le2N-2 1 ≤ n ≤ 2 N − 2 , and a ≤ d − 3 a \le d-3 a ≤ d − 3 . Using the recursion hypothesis, from Equation (4) we obtain
w a + 1 , d − 1 = 1 N + N − a − 1 2 N − a − d ⋅ ( a + 1 ) w a + 2 , d − 1 a + 2 + N − d + 1 2 N − a − d ⋅ ( d − 1 ) w a + 1 , d d ≥ 1 N + N − a − 1 2 N − a − d ⋅ ( a + 1 ) w a + 1 , d a + 2 + N − d + 1 2 N − a − d ⋅ ( d − 1 ) w a + 1 , d d = 1 N + ( N − a − 1 2 N − a − d ⋅ a + 1 a + 2 + N − d + 1 2 N − a − d ⋅ d − 1 d ) w a + 1 , d ≥ 1 N + ( N − a 2 N − a − d ⋅ a a + 1 + N − d 2 N − a − d ⋅ d d + 1 ) w a + 1 , d ≥ 1 N + N − a 2 N − a − d ⋅ a w a + 1 , d a + 1 + N − d 2 N − a − d ⋅ d w a , d + 1 d + 1 = w a , d . \begin{aligned}
w_{a+1,d-1}={}&\frac{1}{N}+\frac{N-a-1}{2N-a-d}\cdot\frac{(a+1)w_{a+2,d-1}}{a+2}+\frac{N-d+1}{2N-a-d}\cdot\frac{(d-1)w_{a+1,d}}{d}\\
\ge{}&\frac{1}{N}+\frac{N-a-1}{2N-a-d}\cdot\frac{(a+1)w_{a+1,d}}{a+2}+\frac{N-d+1}{2N-a-d}\cdot\frac{(d-1)w_{a+1,d}}{d}\\
={}&\frac{1}{N}+\left(\frac{N-a-1}{2N-a-d}\cdot\frac{a+1}{a+2}+\frac{N-d+1}{2N-a-d}\cdot\frac{d-1}{d}\right)w_{a+1,d}\\
\ge{}&\frac{1}{N}+\left(\frac{N-a}{2N-a-d}\cdot\frac{a}{a+1}+\frac{N-d}{2N-a-d}\cdot\frac{d}{d+1}\right)w_{a+1,d}\\
\ge{}&\frac{1}{N}+\frac{N-a}{2N-a-d}\cdot\frac{a w_{a+1,d}}{a+1}+\frac{N-d}{2N-a-d}\cdot\frac{d w_{a,d+1}}{d+1}=w_{a,d}.
\end{aligned} w a + 1 , d − 1 = ≥ = ≥ ≥ N 1 + 2 N − a − d N − a − 1 ⋅ a + 2 ( a + 1 ) w a + 2 , d − 1 + 2 N − a − d N − d + 1 ⋅ d ( d − 1 ) w a + 1 , d N 1 + 2 N − a − d N − a − 1 ⋅ a + 2 ( a + 1 ) w a + 1 , d + 2 N − a − d N − d + 1 ⋅ d ( d − 1 ) w a + 1 , d N 1 + ( 2 N − a − d N − a − 1 ⋅ a + 2 a + 1 + 2 N − a − d N − d + 1 ⋅ d d − 1 ) w a + 1 , d N 1 + ( 2 N − a − d N − a ⋅ a + 1 a + 2 N − a − d N − d ⋅ d + 1 d ) w a + 1 , d N 1 + 2 N − a − d N − a ⋅ a + 1 a w a + 1 , d + 2 N − a − d N − d ⋅ d + 1 d w a , d + 1 = w a , d .
The first and third inequalities result from the induction hypothesis. The second inequality follows from Inequality (27).
The final case we need to consider is when d = a + 2 d=a+2 d = a + 2 and a + d ≤ N − 3 a+d\le N-3 a + d ≤ N − 3 . We have
w a , a + 2 = 1 N + N − a 2 N − 2 a − 2 ⋅ a w a + 1 , a + 2 a + 1 + N − a − 2 2 N − 2 a − 2 ⋅ ( a + 2 ) w a , a + 3 a + 3 ≤ 1 N + N − a 2 N − 2 a − 2 ⋅ a w a + 1 , a + 2 a + 1 + N − a − 2 2 N − 2 a − 2 ⋅ ( a + 2 ) w a + 1 , a + 2 a + 3 = 1 N + [ N − a 2 N − 2 a − 2 ⋅ a a + 1 + N − a − 2 2 N − 2 a − 2 ⋅ a + 2 a + 3 ] w a + 1 , a + 2 ≤ 1 N + ( a + 1 ) w a + 1 , a + 2 a + 2 = w a + 1 , a + 1 . \begin{aligned}
w_{a,a+2}=\frac{1}{N}+\frac{N-a}{2N-2a-2}\cdot\frac{aw_{a+1,a+2}}{a+1}+\frac{N-a-2}{2N-2a-2}\cdot\frac{(a+2)w_{a,a+3}}{a+3} \\
&\le\frac{1}{N}+\frac{N-a}{2N-2a-2}\cdot\frac{aw_{a+1,a+2}}{a+1}+\frac{N-a-2}{2N-2a-2}\cdot\frac{(a+2)w_{a+1,a+2}}{a+3} \\
&=\frac{1}{N}+\left[\frac{N-a}{2N-2a-2}\cdot\frac{a}{a+1}+\frac{N-a-2}{2N-2a-2}\cdot\frac{a+2}{a+3}\right]w_{a+1,a+2} \\
&\le\frac{1}{N}+\frac{(a+1)w_{a+1,a+2}}{a+2}=w_{a+1,a+1}.
\end{aligned} w a , a + 2 = N 1 + 2 N − 2 a − 2 N − a ⋅ a + 1 a w a + 1 , a + 2 + 2 N − 2 a − 2 N − a − 2 ⋅ a + 3 ( a + 2 ) w a , a + 3 ≤ N 1 + 2 N − 2 a − 2 N − a ⋅ a + 1 a w a + 1 , a + 2 + 2 N − 2 a − 2 N − a − 2 ⋅ a + 3 ( a + 2 ) w a + 1 , a + 2 = N 1 + [ 2 N − 2 a − 2 N − a ⋅ a + 1 a + 2 N − 2 a − 2 N − a − 2 ⋅ a + 3 a + 2 ] w a + 1 , a + 2 ≤ N 1 + a + 2 ( a + 1 ) w a + 1 , a + 2 = w a + 1 , a + 1 .
The first equation results from the induction hypothesis. The second inequality results from the fact that when d = a + 2 d=a+2 d = a + 2 , Inequality (27) reduces to
a + 1 a + 2 ≥ N − a 2 N − 2 a − 2 ⋅ a a + 1 + N − a − 2 2 N − 2 a − 2 ⋅ a + 2 a + 3 . \frac{a+1}{a+2}\ge\frac{N-a}{2N-2a-2}\cdot\frac{a}{a+1}+\frac{N-a-2}{2N-2a-2}\cdot\frac{a+2}{a+3}. a + 2 a + 1 ≥ 2 N − 2 a − 2 N − a ⋅ a + 1 a + 2 N − 2 a − 2 N − a − 2 ⋅ a + 3 a + 2 .
Proof of Lemma 6
Suppose that j ≤ i < N j\le i<N j ≤ i < N . It follows that
i w i + 1 , j i + 1 ≥ j w i , j + 1 j + 1 . \frac{iw_{i+1,j}}{i+1}\ge\frac{jw_{i,j+1}}{j+1}. i + 1 i w i + 1 , j ≥ j + 1 j w i , j + 1 .
Proof. First note that by symmetry w i + 1 , i = w i , i + 1 w_{i+1,i}=w_{i,i+1} w i + 1 , i = w i , i + 1 and thus when i = j i=j i = j the inequality in the lemma is satisfied with equality. Otherwise, the proof is by recursion according to the total number of objects that have appeared, n n n , for n ≤ 2 N − 3 n\le2N-3 n ≤ 2 N − 3 .
When n = 2 N − 3 n=2N-3 n = 2 N − 3 , the only case that we need to consider is i = N − 1 , j = N − 2 i=N-1,j=N-2 i = N − 1 , j = N − 2 . It is necessary to show that
( N − 1 ) w N , N − 2 N ≥ ( N − 2 ) w N − 1 , N − 1 N − 1 . (28) \frac{(N-1)w_{N,N-2}}{N}\ge\frac{(N-2)w_{N-1,N-1}}{N-1}. \tag*{(28)} N ( N − 1 ) w N , N − 2 ≥ N − 1 ( N − 2 ) w N − 1 , N − 1 . (28)
Using (4) , we obtain
w N , N − 2 = 1 N + ( N − 2 ) w N , N − 1 N − 1 = 2 N − 3 N ( N − 1 ) w_{N,N-2}=\frac{1}{N}+\frac{(N-2)w_{N,N-1}}{N-1}=\frac{2N-3}{N(N-1)} w N , N − 2 = N 1 + N − 1 ( N − 2 ) w N , N − 1 = N ( N − 1 ) 2 N − 3
w N − 1 , N − 1 = 1 N + ( N − 1 ) w N , N − 1 N = 2 N − 1 N 2 . w_{N-1,N-1}=\frac{1}{N}+\frac{(N-1)w_{N,N-1}}{N}=\frac{2N-1}{N^2}. w N − 1 , N − 1 = N 1 + N ( N − 1 ) w N , N − 1 = N 2 2 N − 1 .
Hence,
( N − 2 ) w N − 1 , N − 1 N − 1 = ( N − 2 ) ( 2 N − 1 ) N 2 ( N − 1 ) = 2 N 2 − 5 N + 2 N 2 ( N − 1 ) \frac{(N-2)w_{N-1,N-1}}{N-1}=\frac{(N-2)(2N-1)}{N^2(N-1)}=\frac{2N^2-5N+2}{N^2(N-1)} N − 1 ( N − 2 ) w N − 1 , N − 1 = N 2 ( N − 1 ) ( N − 2 ) ( 2 N − 1 ) = N 2 ( N − 1 ) 2 N 2 − 5 N + 2
( N − 1 ) w N , N − 2 N = ( 2 N − 3 ) ( N − 1 ) N 2 ( N − 1 ) = 2 N 2 − 5 N + 3 N 2 ( N − 1 ) . \frac{(N-1)w_{N,N-2}}{N}=\frac{(2N-3)(N-1)}{N^2(N-1)}=\frac{2N^2-5N+3}{N^2(N-1)}. N ( N − 1 ) w N , N − 2 = N 2 ( N − 1 ) ( 2 N − 3 ) ( N − 1 ) = N 2 ( N − 1 ) 2 N 2 − 5 N + 3 .
It is thus clear that Inequality (28) holds for any N ≥ 2 N\ge2 N ≥ 2 (which is necessary for there to be three objects yet to appear).
Now suppose that the lemma holds for n ≥ 2 N − k + 1 n\ge2N-k+1 n ≥ 2 N − k + 1 . We now show that the lemma holds for n = 2 N − k n=2N-k n = 2 N − k . The lemma then follows by recursion. Suppose that n = i + j = 2 N − k n=i+j=2N-k n = i + j = 2 N − k and i > j i>j i > j . Define δ = 1 n + 1 \delta=\frac{1}{n+1} δ = n + 1 1 . From Equation (4)
w i + 1 , j = 1 N + ( i + 1 ) α i + 1 , j w i + 2 , j i + 2 + j ( 1 − α i + 1 , j ) w i + 1 , j + 1 j + 1 ≥ 1 N + j w i + 1 , j + 1 j + 1 . \begin{aligned}
w_{i+1,j}=\frac{1}{N}+\frac{(i+1)\alpha_{i+1,j}w_{i+2,j}}{i+2}+\frac{j(1-\alpha_{i+1,j})w_{i+1,j+1}}{j+1} \\
&\ge\frac{1}{N}+\frac{jw_{i+1,j+1}}{j+1}.
\end{aligned} w i + 1 , j = N 1 + i + 2 ( i + 1 ) α i + 1 , j w i + 2 , j + j + 1 j ( 1 − α i + 1 , j ) w i + 1 , j + 1 ≥ N 1 + j + 1 j w i + 1 , j + 1 .
where 0 ≤ α i + 1 , j = N − i − 1 2 N − i − j − 1 < 0.5 0\le\alpha_{i+1,j}=\frac{N-i-1}{2N-i-j-1}<0.5 0 ≤ α i + 1 , j = 2 N − i − j − 1 N − i − 1 < 0.5 and the inequality results from the induction assumption. Similarly,
w i , j + 1 = 1 N + i ( α i , j + δ ) w i + 1 , j + 1 i + 1 + ( j + 1 ) ( 1 − α i , j − δ ) w i , j + 2 j + 2 ≤ 1 N + i w i + 1 , j + 1 i + 1 . \begin{aligned}
w_{i,j+1}=\frac{1}{N}+\frac{i(\alpha_{i,j}+\delta)w_{i+1,j+1}}{i+1}+\frac{(j+1)(1-\alpha_{i,j}-\delta)w_{i,j+2}}{j+2} \\
&\le\frac{1}{N}+\frac{iw_{i+1,j+1}}{i+1}.
\end{aligned} w i , j + 1 = N 1 + i + 1 i ( α i , j + δ ) w i + 1 , j + 1 + j + 2 ( j + 1 ) ( 1 − α i , j − δ ) w i , j + 2 ≤ N 1 + i + 1 i w i + 1 , j + 1 .
Multiplying the above inequalities by i i + 1 \frac{i}{i+1} i + 1 i and j j + 1 \frac{j}{j+1} j + 1 j , respectively, it follows that
i w i + 1 , j i + 1 − j w i , j + 1 j + 1 ≥ 1 N [ i i + 1 − j j + 1 ] ≥ 0. \frac{iw_{i+1,j}}{i+1}-\frac{jw_{i,j+1}}{j+1}\ge\frac{1}{N}\left[\frac{i}{i+1}-\frac{j}{j+1}\right]\ge0. i + 1 i w i + 1 , j − j + 1 j w i , j + 1 ≥ N 1 [ i + 1 i − j + 1 j ] ≥ 0.
The final inequality results from the fact that i > j i>j i > j .
□
Proof of Lemma 7
For 1 ≤ i , j ≤ N − 1 1\le i,j\le N-1 1 ≤ i , j ≤ N − 1 , ∣ v i + 1 , j − v i , j + 1 ∣ ≤ 1 N \lvert v_{i+1,j}-v_{i,j+1}\rvert\le\frac{1}{N} ∣ v i + 1 , j − v i , j + 1 ∣ ≤ N 1 .
Proof. The proof is by recursion on the number of offers that have appeared, n = i + j n=i+j n = i + j . For n = 2 N − 1 n=2N-1 n = 2 N − 1 , v N , N − 1 = v N − 1 , N = 1 N v_{N,N-1}=v_{N-1,N}=\frac{1}{N} v N , N − 1 = v N − 1 , N = N 1 . Hence, the hypothesis is true for n = 2 N − 1 n=2N-1 n = 2 N − 1 .
Assume that this lemma is true for n = 2 N − s n=2N-s n = 2 N − s , where s ≥ 1 s\ge1 s ≥ 1 . Given that i i i objects of type 1 and j j j objects of type 2 have appeared, let v i , j ∣ k v_{i,j|k} v i , j ∣ k be the optimal reward given that the next object to appear is of type k k k .
v i − 1 , j = α i − 1 , j v i − 1 , j ∣ 1 + ( 1 − α i − 1 , j ) v i − 1 , j ∣ 2 (29) v_{i-1,j}=\alpha_{i-1,j}v_{i-1,j|1}+(1-\alpha_{i-1,j})v_{i-1,j|2} \tag*{(29)} v i − 1 , j = α i − 1 , j v i − 1 , j ∣1 + ( 1 − α i − 1 , j ) v i − 1 , j ∣2 (29)
v i , j − 1 = [ α i − 1 , j − 1 N − n + 1 ] v i , j − 1 ∣ 1 + [ 1 − α i − 1 , j + 1 N − n + 1 ] v i , j − 1 ∣ 2 . (30) v_{i,j-1}=\left[\alpha_{i-1,j}-\frac{1}{N-n+1}\right]v_{i,j-1|1}+\left[1-\alpha_{i-1,j}+\frac{1}{N-n+1}\right]v_{i,j-1|2}. \tag*{(30)} v i , j − 1 = [ α i − 1 , j − N − n + 1 1 ] v i , j − 1∣1 + [ 1 − α i − 1 , j + N − n + 1 1 ] v i , j − 1∣2 . (30)
Note that
v i − 1 , j ∣ 1 = max { v i , j , 1 N + ( i − 1 ) v i , j i } v_{i-1,j|1}=\max\left\{v_{i,j},\frac{1}{N}+\frac{(i-1)v_{i,j}}{i}\right\} v i − 1 , j ∣1 = max { v i , j , N 1 + i ( i − 1 ) v i , j }
v i − 1 , j ∣ 2 = max { v i − 1 , j + 1 , 1 N + j v i − 1 , j + 1 j + 1 } . v_{i-1,j|2}=\max\left\{v_{i-1,j+1},\frac{1}{N}+\frac{jv_{i-1,j+1}}{j+1}\right\}. v i − 1 , j ∣2 = max { v i − 1 , j + 1 , N 1 + j + 1 j v i − 1 , j + 1 } .
Firstly, suppose that v i , j ≥ 1 N + ( i − 1 ) v i , j i v_{i,j}\ge\frac{1}{N}+\frac{(i-1)v_{i,j}}{i} v i , j ≥ N 1 + i ( i − 1 ) v i , j and v i + 1 , j − 1 ≥ 1 N + i v i + 1 , j − 1 i + 1 v_{i+1,j-1}\ge\frac{1}{N}+\frac{iv_{i+1,j-1}}{i+1} v i + 1 , j − 1 ≥ N 1 + i + 1 i v i + 1 , j − 1 . It follows that
∣ v i − 1 , j ∣ 1 − v i , j − 1 ∣ 1 ∣ = ∣ v i , j − v i + 1 , j − 1 ∣ ≤ 1 N , \lvert v_{i-1,j|1}-v_{i,j-1|1}\rvert=\lvert v_{i,j}-v_{i+1,j-1}\rvert\le\frac{1}{N}, ∣ v i − 1 , j ∣1 − v i , j − 1∣1 ∣ = ∣ v i , j − v i + 1 , j − 1 ∣ ≤ N 1 ,
where the inequality results from the recursion hypothesis. Secondly, suppose that v i , j < 1 N + ( i − 1 ) v i , j i v_{i,j}<\frac{1}{N}+\frac{(i-1)v_{i,j}}{i} v i , j < N 1 + i ( i − 1 ) v i , j and v i + 1 , j − 1 < 1 N + i v i + 1 , j − 1 i + 1 v_{i+1,j-1}<\frac{1}{N}+\frac{iv_{i+1,j-1}}{i+1} v i + 1 , j − 1 < N 1 + i + 1 i v i + 1 , j − 1 . It follows that v i + 1 , j − 1 ≤ i + 1 N v_{i+1,j-1}\leq\frac{i+1}{N} v i + 1 , j − 1 ≤ N i + 1 . We have
∣ v i − 1 , j ∣ 1 − v i , j − 1 ∣ 1 ∣ = ∣ ( i − 1 ) v i , j i − i v i + 1 , j − 1 i + 1 ∣ ≤ i − 1 i ∣ v i , j − v i + 1 , j − 1 ∣ + v i + 1 , j − 1 i ( i + 1 ) ≤ i − 1 i N + 1 i ( i + 1 ) × i + 1 N ≤ 1 N . \begin{aligned}
|v_{i-1,j|1}-v_{i,j-1|1}|=\left|\frac{(i-1)v_{i,j}}{i}-\frac{iv_{i+1,j-1}}{i+1}\right| \\
&\leq\frac{i-1}{i}|v_{i,j}-v_{i+1,j-1}|+\frac{v_{i+1,j-1}}{i(i+1)} \\
&\leq\frac{i-1}{iN}+\frac{1}{i(i+1)}\times\frac{i+1}{N}\leq\frac{1}{N}.
\end{aligned} ∣ v i − 1 , j ∣1 − v i , j − 1∣1 ∣ = i ( i − 1 ) v i , j − i + 1 i v i + 1 , j − 1 ≤ i i − 1 ∣ v i , j − v i + 1 , j − 1 ∣ + i ( i + 1 ) v i + 1 , j − 1 ≤ i N i − 1 + i ( i + 1 ) 1 × N i + 1 ≤ N 1 .
Thirdly, suppose that v i , j ≥ 1 N + ( i − 1 ) v i , j i v_{i,j}\geq\frac{1}{N}+\frac{(i-1)v_{i,j}}{i} v i , j ≥ N 1 + i ( i − 1 ) v i , j and v i + 1 , j − 1 < 1 N + v i + 1 , j − 1 i + 1 v_{i+1,j-1}<\frac{1}{N}+\frac{v_{i+1,j-1}}{i+1} v i + 1 , j − 1 < N 1 + i + 1 v i + 1 , j − 1 . In this case, since v i + 1 , j − 1 < i + 1 N v_{i+1,j-1}<\frac{i+1}{N} v i + 1 , j − 1 < N i + 1 and v i , j ≥ i N v_{i,j}\geq\frac{i}{N} v i , j ≥ N i , it follows from the recursion hypothesis that i N ≤ v i , j ≤ i + 2 N \frac{i}{N}\leq v_{i,j}\leq\frac{i+2}{N} N i ≤ v i , j ≤ N i + 2 . We have
∣ v i − 1 , j ∣ 1 − v i , j − 1 ∣ 1 ∣ = ∣ v i , j − i v i + 1 , j − 1 i + 1 − 1 N ∣ ≤ i i + 1 ∣ v i , j − v i + 1 , j − 1 ∣ + ∣ v i , j i + 1 − 1 N ∣ . \begin{aligned}
|v_{i-1,j|1}-v_{i,j-1|1}|=\left|v_{i,j}-\frac{iv_{i+1,j-1}}{i+1}-\frac{1}{N}\right| \\
&\leq\frac{i}{i+1}|v_{i,j}-v_{i+1,j-1}|+\left|\frac{v_{i,j}}{i+1}-\frac{1}{N}\right|.
\end{aligned} ∣ v i − 1 , j ∣1 − v i , j − 1∣1 ∣ = v i , j − i + 1 i v i + 1 , j − 1 − N 1 ≤ i + 1 i ∣ v i , j − v i + 1 , j − 1 ∣ + i + 1 v i , j − N 1 .
Note that
− 1 ( i + 1 ) N = i ( i + 1 ) N − 1 N ≤ v i , j i + 1 − 1 N ≤ i + 2 ( i + 1 ) N − 1 N = 1 ( i + 1 ) N . -\frac{1}{(i+1)N}=\frac{i}{(i+1)N}-\frac{1}{N}\leq\frac{v_{i,j}}{i+1}-\frac{1}{N}\leq\frac{i+2}{(i+1)N}-\frac{1}{N}=\frac{1}{(i+1)N}. − ( i + 1 ) N 1 = ( i + 1 ) N i − N 1 ≤ i + 1 v i , j − N 1 ≤ ( i + 1 ) N i + 2 − N 1 = ( i + 1 ) N 1 .
Hence,
∣ v i − 1 , j ∣ 1 − v i , j − 1 ∣ 1 ∣ ≤ i ( i + 1 ) N + 1 ( i + 1 ) N = 1 N . |v_{i-1,j|1}-v_{i,j-1|1}|\leq\frac{i}{(i+1)N}+\frac{1}{(i+1)N}=\frac{1}{N}. ∣ v i − 1 , j ∣1 − v i , j − 1∣1 ∣ ≤ ( i + 1 ) N i + ( i + 1 ) N 1 = N 1 .
Finally, note that the combined conditions v i , j < 1 N + ( i − 1 ) v i , j i v_{i,j}<\frac{1}{N}+\frac{(i-1)v_{i,j}}{i} v i , j < N 1 + i ( i − 1 ) v i , j and v i + 1 , j − 1 ≥ 1 N + i v i + 1 , j − 1 i + 1 v_{i+1,j-1}\geq\frac{1}{N}+\frac{iv_{i+1,j-1}}{i+1} v i + 1 , j − 1 ≥ N 1 + i + 1 i v i + 1 , j − 1 contradict the induction hypothesis, since it follows that v i + 1 , j − 1 ≥ i + 1 N v_{i+1,j-1}\geq\frac{i+1}{N} v i + 1 , j − 1 ≥ N i + 1 and v i , j < i N v_{i,j}<\frac{i}{N} v i , j < N i . Hence, ∣ v i − 1 , j ∣ 1 − v i , j − 1 ∣ 1 ∣ ≤ 1 N |v_{i-1,j|1}-v_{i,j-1|1}|\leq\frac{1}{N} ∣ v i − 1 , j ∣1 − v i , j − 1∣1 ∣ ≤ N 1 .
Note that by symmetry v i , j ∣ 2 = v j , i ∣ 1 v_{i,j|2}=v_{j,i|1} v i , j ∣2 = v j , i ∣1 . Hence, it follows from the above arguments that ∣ v i − 1 , j ∣ 2 − v i , j − 1 ∣ 2 ∣ ≤ 1 N |v_{i-1,j|2}-v_{i,j-1|2}|\leq\frac{1}{N} ∣ v i − 1 , j ∣2 − v i , j − 1∣2 ∣ ≤ N 1 .
Let δ = α i − 1 , j − α i , j − 1 = 1 N − n + 1 \delta=\alpha_{i-1,j}-\alpha_{i,j-1}=\frac{1}{N-n+1} δ = α i − 1 , j − α i , j − 1 = N − n + 1 1 . From Equations (29) and (30), it follows that
∣ v i − 1 , j − v i , j − 1 ∣ = ∣ α i − 1 , j v i − 1 , j ∣ 1 + ( 1 − α i − 1 , j ) v i − 1 , j ∣ 2 − ( α i − 1 , j − δ ) v i , j − 1 ∣ 1 − ( 1 − α i − 1 , j + δ ) v i , j − 1 ∣ 2 ∣ ≤ ( α i − 1 , j − δ ) ∣ v i − 1 , j ∣ 1 − v i , j − 1 ∣ 1 ∣ + ( 1 − α i − 1 , j ) ∣ v i − 1 , j ∣ 2 − v i , j − 1 ∣ 2 ∣ + δ ∣ v i − 1 , j ∣ 1 − v i , j − 1 ∣ 2 ∣ ≤ 1 N [ 1 − δ ] + δ ∣ v i − 1 , j ∣ 1 − v i , j − 1 ∣ 2 ∣ . (31) \begin{aligned}
|v_{i-1,j}-v_{i,j-1}|={}&\left|\alpha_{i-1,j}v_{i-1,j|1}+(1-\alpha_{i-1,j})v_{i-1,j|2}\right.\\
&\left.-(\alpha_{i-1,j}-\delta)v_{i,j-1|1}-(1-\alpha_{i-1,j}+\delta)v_{i,j-1|2}\right|\\
\leq{}&(\alpha_{i-1,j}-\delta)|v_{i-1,j|1}-v_{i,j-1|1}|+(1-\alpha_{i-1,j})|v_{i-1,j|2}-v_{i,j-1|2}|\\
&+\delta|v_{i-1,j|1}-v_{i,j-1|2}|\\
\leq{}&\frac{1}{N}[1-\delta]+\delta|v_{i-1,j|1}-v_{i,j-1|2}|. \tag*{(31)}
\end{aligned} ∣ v i − 1 , j − v i , j − 1 ∣ = ≤ ≤ α i − 1 , j v i − 1 , j ∣1 + ( 1 − α i − 1 , j ) v i − 1 , j ∣2 − ( α i − 1 , j − δ ) v i , j − 1∣1 − ( 1 − α i − 1 , j + δ ) v i , j − 1∣2 ( α i − 1 , j − δ ) ∣ v i − 1 , j ∣1 − v i , j − 1∣1 ∣ + ( 1 − α i − 1 , j ) ∣ v i − 1 , j ∣2 − v i , j − 1∣2 ∣ + δ ∣ v i − 1 , j ∣1 − v i , j − 1∣2 ∣ N 1 [ 1 − δ ] + δ ∣ v i − 1 , j ∣1 − v i , j − 1∣2 ∣. (31)
Suppose that in both of the states ( i , j , 1 ) (i,j,1) ( i , j , 1 ) and ( i , j , 2 ) (i,j,2) ( i , j , 2 ) , the DM should reject a candidate. It follows that v i − 1 , j ∣ 1 = v i , j − 1 ∣ 2 = v i , j v_{i-1,j|1}=v_{i,j-1|2}=v_{i,j} v i − 1 , j ∣1 = v i , j − 1∣2 = v i , j .
Now suppose that in both of the states ( i , j , 1 ) (i,j,1) ( i , j , 1 ) and ( i , j , 2 ) (i,j,2) ( i , j , 2 ) , the DM should accept a candidate. It follows that
∣ v i − 1 , j ∣ 1 − v i , j − 1 ∣ 2 ∣ = ∣ [ 1 N + ( i − 1 ) v i , j i ] − [ 1 N + ( j − 1 ) v i , j j ] ∣ = v i , j ∣ i − 1 i − j − 1 j ∣ = v i , j ∣ i − j i j ∣ . \begin{aligned}
|v_{i-1,j|1}-v_{i,j-1|2}|&=\left|\left[\frac{1}{N}+\frac{(i-1)v_{i,j}}{i}\right]-\left[\frac{1}{N}+\frac{(j-1)v_{i,j}}{j}\right]\right|\\
&=v_{i,j}\left|\frac{i-1}{i}-\frac{j-1}{j}\right|=v_{i,j}\left|\frac{i-j}{ij}\right|.
\end{aligned} ∣ v i − 1 , j ∣1 − v i , j − 1∣2 ∣ = [ N 1 + i ( i − 1 ) v i , j ] − [ N 1 + j ( j − 1 ) v i , j ] = v i , j i i − 1 − j j − 1 = v i , j ij i − j .
From the symmetry between i i i and j j j , we may assume without loss of generality that i ≥ j i \ge j i ≥ j . Since a candidate should be accepted in state ( i , j , 2 ) (i,j,2) ( i , j , 2 ) , v i , j ≤ j N v_{i,j} \le\frac{j}{N} v i , j ≤ N j . Thus
∣ v i − 1 , j ∣ 1 − v i , j − 1 ∣ 2 ∣ ≤ ( i − j ) j i j N = i − j i N ≤ 1 N . \left|v_{i-1,j|1}-v_{i,j-1|2}\right| \le\frac{(i-j)j}{ijN}=\frac{i-j}{iN}\le\frac{1}{N}. v i − 1 , j ∣1 − v i , j − 1∣2 ≤ ij N ( i − j ) j = i N i − j ≤ N 1 .
Assume that a DM should accept a candidate in state ( i , j , 1 ) (i,j,1) ( i , j , 1 ) , but not in state ( i , j , 2 ) (i,j,2) ( i , j , 2 ) . Hence, i > j i>j i > j and j N < v i , j ≤ i N \frac{j}{N}<v_{i,j}\le\frac{i}{N} N j < v i , j ≤ N i .
∣ v i − 1 , j ∣ 1 − v i , j − 1 ∣ 2 ∣ = ∣ 1 N + ( i − 1 ) v i , j i − v i , j ∣ = ∣ 1 N − v i , j i ∣ ≤ 1 N . \left|v_{i-1,j|1}-v_{i,j-1|2}\right|=\left|\frac{1}{N}+\frac{(i-1)v_{i,j}}{i}-v_{i,j}\right|=\left|\frac{1}{N}-\frac{v_{i,j}}{i}\right|\le\frac{1}{N}. v i − 1 , j ∣1 − v i , j − 1∣2 = N 1 + i ( i − 1 ) v i , j − v i , j = N 1 − i v i , j ≤ N 1 .
It follows from an analogous argument that when a DM should accept a candidate in state ( i , j , 2 ) (i,j,2) ( i , j , 2 ) , but not in state ( i , j , 1 ) (i,j,1) ( i , j , 1 ) , then ∣ v i − 1 , j ∣ 1 − v i , j − 1 ∣ 2 ∣ ≤ 1 N \left|v_{i-1,j|1}-v_{i,j-1|2}\right|\le\frac{1}{N} v i − 1 , j ∣1 − v i , j − 1∣2 ≤ N 1 . Hence, for all 1 ≤ i , j ≤ N 1\le i,j\le N 1 ≤ i , j ≤ N , ∣ v i − 1 , j ∣ 1 − v i , j − 1 ∣ 2 ∣ ≤ 1 N \left|v_{i-1,j|1}-v_{i,j-1|2}\right|\le\frac{1}{N} v i − 1 , j ∣1 − v i , j − 1∣2 ≤ N 1 .
It thus follows from Equation (31) that ∣ v i − 1 , j − v i , j − 1 ∣ ≤ 1 N \left|v_{i-1,j}-v_{i,j-1}\right|\le\frac{1}{N} ∣ v i − 1 , j − v i , j − 1 ∣ ≤ N 1 and Lemma 7 follows by recursion.
Proof of Lemma 8
Assume that it is optimal to accept an offer in state ( i + 1 , j , 1 ) (i+1,j,1) ( i + 1 , j , 1 ) , where j ≤ i < N j\le i<N j ≤ i < N . It follows that
1 N + i v i + 1 , j i + 1 ≥ v i , j + 1 . (32) \frac{1}{N}+\frac{i v_{i+1,j}}{i+1}\ge v_{i,j+1}. \tag*{(32)} N 1 + i + 1 i v i + 1 , j ≥ v i , j + 1 . (32)
Proof. First, assume that ( i , j ) ∈ B 3 (i,j)\in B_3 ( i , j ) ∈ B 3 , i.e. starting from the state ( i , j , 0 ) (i,j,0) ( i , j , 0 ) it is always optimal to accept the next candidate to appear. From Lemma 6 it follows that
1 N + i v i + 1 , j i + 1 ≥ 1 N + j v i , j + 1 j + 1 . \frac{1}{N}+\frac{i v_{i+1,j}}{i+1}\ge\frac{1}{N}+\frac{j v_{i,j+1}}{j+1}. N 1 + i + 1 i v i + 1 , j ≥ N 1 + j + 1 j v i , j + 1 .
In this case, the hypothesis follows from the optimality criterion
v i , j + 1 ≤ j + 1 N ⇒ 1 N + j v i , j + 1 j + 1 ≥ v i , j + 1 . v_{i,j+1}\le\frac{j+1}{N}\Rightarrow\frac{1}{N}+\frac{j v_{i,j+1}}{j+1}\ge v_{i,j+1}. v i , j + 1 ≤ N j + 1 ⇒ N 1 + j + 1 j v i , j + 1 ≥ v i , j + 1 .
Note that from Theorem 1, when ( i , j ) ∈ B 3 (i,j)\in B_3 ( i , j ) ∈ B 3 it follows that v i , j ≥ v i , j + 1 v_{i,j}\ge v_{i,j+1} v i , j ≥ v i , j + 1 .
When i ≥ i N ∗ i\ge i_N^* i ≥ i N ∗ a candidate should not be accepted in state ( i , j ∘ ( i ) , 2 ) (i,j^\circ(i),2) ( i , j ∘ ( i ) , 2 ) , but always be accepted in state ( i , j ∘ ( i ) + 1 , k ) (i,j^\circ(i)+1,k) ( i , j ∘ ( i ) + 1 , k ) , where k ∈ { 1 , 2 } k\in\{1,2\} k ∈ { 1 , 2 } . Now we consider starting from a state ( i , j , 0 ) (i,j,0) ( i , j , 0 ) , j < i N ∗ ≤ i < N j<i_N^*\le i<N j < i N ∗ ≤ i < N , that borders the set B 3 B_3 B 3 , i.e. ( i + 1 , j ) (i+1,j) ( i + 1 , j ) and/or ( i , j + 1 ) ∈ B 3 (i,j+1)\in B_3 ( i , j + 1 ) ∈ B 3 , but ( i , j ) ∉ B 3 (i,j)\notin B_3 ( i , j ) ∈ / B 3 . Consider a state of the form ( i , j , 0 ) (i,j,0) ( i , j , 0 ) such that both ( i + 1 , j ) (i+1,j) ( i + 1 , j ) and ( i , j + 1 ) (i,j+1) ( i , j + 1 ) are in B 3 B_3 B 3 . It follows that a candidate should be accepted in both of the states ( i + 1 , j + 1 , 1 ) (i+1,j+1,1) ( i + 1 , j + 1 , 1 ) and ( i , j + 2 , 2 ) (i,j+2,2) ( i , j + 2 , 2 ) . Note that by assumption a candidate should be accepted in state ( i + 1 , j , 1 ) (i+1,j,1) ( i + 1 , j , 1 ) . We have
1 N + i v i + 1 , j i + 1 − v i , j + 1 ≥ 1 N + i i + 1 [ α i + 1 , j ( 1 N + ( i + 1 ) v i + 2 , j i + 2 ) + ( 1 − α i + 1 , j ) v i + 1 , j + 1 ] − ( α i + 1 , j + ϵ ) [ 1 N + i v i + 1 , j + 1 i + 1 ] − ( 1 − α i + 1 , j − ϵ ) [ 1 N + ( j + 1 ) v i , j + 2 j + 2 ] = i α i + 1 , j i + 1 [ 1 N + ( i + 1 ) v i + 2 , j i + 2 − v i + 1 , j + 1 ] + ( 1 − α i + 1 , j − ϵ ) [ i v i + 1 , j + 1 i + 1 − ( j + 1 ) v i , j + 2 j + 2 ] ≥ 0 , (33) \begin{aligned}
\frac{1}{N}+\frac{i v_{i+1,j}}{i+1}-v_{i,j+1}
&\ge\frac{1}{N}+\frac{i}{i+1}\left[\alpha_{i+1,j}\left(\frac{1}{N}+\frac{(i+1)v_{i+2,j}}{i+2}\right)+(1-\alpha_{i+1,j})v_{i+1,j+1}\right]\\
&\quad-(\alpha_{i+1,j}+\epsilon)\left[\frac{1}{N}+\frac{i v_{i+1,j+1}}{i+1}\right]-(1-\alpha_{i+1,j}-\epsilon)\left[\frac{1}{N}+\frac{(j+1)v_{i,j+2}}{j+2}\right]\\
&=\frac{i\alpha_{i+1,j}}{i+1}\left[\frac{1}{N}+\frac{(i+1)v_{i+2,j}}{i+2}-v_{i+1,j+1}\right]\\
&\quad+(1-\alpha_{i+1,j}-\epsilon)\left[\frac{i v_{i+1,j+1}}{i+1}-\frac{(j+1)v_{i,j+2}}{j+2}\right]\ge0, \tag*{(33)}
\end{aligned} N 1 + i + 1 i v i + 1 , j − v i , j + 1 ≥ N 1 + i + 1 i [ α i + 1 , j ( N 1 + i + 2 ( i + 1 ) v i + 2 , j ) + ( 1 − α i + 1 , j ) v i + 1 , j + 1 ] − ( α i + 1 , j + ϵ ) [ N 1 + i + 1 i v i + 1 , j + 1 ] − ( 1 − α i + 1 , j − ϵ ) [ N 1 + j + 2 ( j + 1 ) v i , j + 2 ] = i + 1 i α i + 1 , j [ N 1 + i + 2 ( i + 1 ) v i + 2 , j − v i + 1 , j + 1 ] + ( 1 − α i + 1 , j − ϵ ) [ i + 1 i v i + 1 , j + 1 − j + 2 ( j + 1 ) v i , j + 2 ] ≥ 0 , (33)
where ϵ = 1 2 N − i − j − 1 \epsilon= \frac{1}{2N-i-j-1} ϵ = 2 N − i − j − 1 1 . The first term in square brackets in the final inequality is non-negative because ( i + 1 , j ) ∈ B 3 (i+1,j) \in B_3 ( i + 1 , j ) ∈ B 3 . The fact that the second term in square brackets is non-negative results from Lemma 6 and the facts that i > j i>j i > j and ( i , j + 1 ) ∈ B 3 (i,j+1) \in B_3 ( i , j + 1 ) ∈ B 3 . Note that for such states
v i , j = α i , j [ 1 N + i v i + 1 , j i + 1 ] + ( 1 − α i , j ) v i , j + 1 . v_{i,j}=\alpha_{i,j}\left[\frac{1}{N}+\frac{i v_{i+1,j}}{i+1}\right]+(1-\alpha_{i,j})v_{i,j+1}. v i , j = α i , j [ N 1 + i + 1 i v i + 1 , j ] + ( 1 − α i , j ) v i , j + 1 .
Hence, it follows that v i , j ≥ v i , j + 1 v_{i,j}\ge v_{i,j+1} v i , j ≥ v i , j + 1 , since v i , j v_{i,j} v i , j is the weighted average of v i , j + 1 v_{i,j+1} v i , j + 1 and another term which is at least as large as v i , j + 1 v_{i,j+1} v i , j + 1 .
Let t ( j ) t(j) t ( j ) be the largest integer i i i for a given j j j , where j ∘ ( N ) ≤ j ≤ j ∘ ( i N ) j^\circ(N)\le j\le j^\circ(i_N) j ∘ ( N ) ≤ j ≤ j ∘ ( i N ) , such that ( i , j ) ∉ B 3 (i,j)\notin B_3 ( i , j ) ∈ / B 3 . From the argument above, the lemma holds for ( i , j ) = ( t ( j ) , j ) (i,j)=(t(j),j) ( i , j ) = ( t ( j ) , j ) . Now we consider starting in a state of the form ( i , j , 0 ) (i,j,0) ( i , j , 0 ) such that j ≥ j ∘ ( N ) j\ge j^\circ(N) j ≥ j ∘ ( N ) , a candidate should be accepted in state ( i + 1 , j , 1 ) (i+1,j,1) ( i + 1 , j , 1 ) , ( i + 1 , j ) ∉ B 3 (i+1,j)\notin B_3 ( i + 1 , j ) ∈ / B 3 , but ( i , j + 1 ) ∈ B 3 (i,j+1)\in B_3 ( i , j + 1 ) ∈ B 3 . It follows that a candidate should be accepted in both of the states ( i + 1 , j + 1 , 1 ) (i+1,j+1,1) ( i + 1 , j + 1 , 1 ) and ( i , j + 2 , 2 ) (i,j+2,2) ( i , j + 2 , 2 ) . Hence, for a given j j j , the set of ( i , j ) (i,j) ( i , j ) satisfying this condition is of the form { ( s ( j ) , j ) , ( s ( j ) + 1 , j ) , … , ( t ( j ) − 1 , j ) } \{(s(j),j),(s(j)+1,j),\ldots,(t(j)-1,j)\} {( s ( j ) , j ) , ( s ( j ) + 1 , j ) , … , ( t ( j ) − 1 , j )} . Adapting the derivation of Inequality (33) for ( i , j ) = ( t ( j ) − 1 , j ) (i,j)=(t(j)-1,j) ( i , j ) = ( t ( j ) − 1 , j ) , it follows that the lemma holds for state ( t ( j ) − 1 , j ) (t(j)-1,j) ( t ( j ) − 1 , j ) . The only change in the argument is that the first term in square brackets in Inequality (33) is non-negative due to the lemma holding for ( i , j ) = ( t ( j ) , j ) (i,j)=(t(j),j) ( i , j ) = ( t ( j ) , j ) . Arguing analogously, it follows by recursion that the lemma holds for each state in the set ( s ( j ) , j ) , ( s ( j ) + 1 , j ) , … , ( t ( j ) − 1 , j ) (s(j),j),(s(j)+1,j),\ldots,(t(j)-1,j) ( s ( j ) , j ) , ( s ( j ) + 1 , j ) , … , ( t ( j ) − 1 , j ) . Hence, the lemma holds for any ( i , j ) ∉ B 3 (i,j)\notin B_3 ( i , j ) ∈ / B 3 such that ( i , j + 1 ) ∈ B 3 (i,j+1)\in B_3 ( i , j + 1 ) ∈ B 3 .
Assume that i > j i>j i > j , it is impossible for ( i + 1 , j ) ∈ B 3 (i+1,j)\in B_3 ( i + 1 , j ) ∈ B 3 and ( i , j + 1 ) ∉ B 3 (i,j+1)\notin B_3 ( i , j + 1 ) ∈ / B 3 . The first condition requires that v i + 1 , j + 1 ≤ j + 1 N v_{i+1,j+1}\le\frac{j+1}{N} v i + 1 , j + 1 ≤ N j + 1 . From Lemma 7 it follows that v i , j + 2 ≤ j + 2 N v_{i,j+2}\le\frac{j+2}{N} v i , j + 2 ≤ N j + 2 . Hence, starting from state ( i , j + 1 , 0 ) (i,j+1,0) ( i , j + 1 , 0 ) , any candidate which appears at the next moment, i.e. in state ( i + 1 , j + 1 , 1 ) (i+1,j+1,1) ( i + 1 , j + 1 , 1 ) or ( i , j + 2 , 2 ) (i,j+2,2) ( i , j + 2 , 2 ) should be accepted.
From the above arguments, it follows that Inequality (32) holds whenever ( i + 1 , j ) ∈ B 3 (i+1,j)\in B_3 ( i + 1 , j ) ∈ B 3 and/or ( i , j + 1 ) ∈ B 3 (i,j+1)\in B_3 ( i , j + 1 ) ∈ B 3 . Let U 0 U_0 U 0 be the set of ( i , j ) (i,j) ( i , j ) , such that i > j i>j i > j , a candidate should be accepted in state ( i , j , 1 ) (i,j,1) ( i , j , 1 ) , ( i , j ) ∉ B 3 (i,j)\notin B_3 ( i , j ) ∈ / B 3 but ( i + 1 , j ) ∈ B 3 (i+1,j)\in B_3 ( i + 1 , j ) ∈ B 3 and/or ( i , j + 1 ) ∈ B 3 (i,j+1)\in B_3 ( i , j + 1 ) ∈ B 3 .
Note that v i , j ≥ v i , j + 1 v_{i,j}\ge v_{i,j+1} v i , j ≥ v i , j + 1 for ( i , j ) ∈ U 0 (i,j)\in U_0 ( i , j ) ∈ U 0 . Hence, if a candidate should be accepted in state ( i , j , 1 ) (i,j,1) ( i , j , 1 ) , i.e. v i , j ≤ i N v_{i,j}\le\frac{i}{N} v i , j ≤ N i , it follows that a candidate should be accepted in state ( i , j + 1 , 1 ) (i,j+1,1) ( i , j + 1 , 1 ) , since v i , j + 1 ≤ i N v_{i,j+1}\le\frac{i}{N} v i , j + 1 ≤ N i . From Lemma 7, v i + 1 , j ≤ i + 1 N v_{i+1,j}\le\frac{i+1}{N} v i + 1 , j ≤ N i + 1 and thus a candidate should be accepted in state ( i + 1 , j , 1 ) (i+1,j,1) ( i + 1 , j , 1 ) .
Finally, we consider starting from a state ( i , j , 0 ) (i,j,0) ( i , j , 0 ) such that i > j i>j i > j , a candidate should be accepted in state ( i + 1 , j , 1 ) (i+1,j,1) ( i + 1 , j , 1 ) , but neither ( i + 1 , j ) (i+1,j) ( i + 1 , j ) nor ( i , j + 1 ) (i,j+1) ( i , j + 1 ) belong to B 3 B_3 B 3 . Since a candidate should be accepted in state ( i + 1 , j + 1 , 1 ) (i+1,j+1,1) ( i + 1 , j + 1 , 1 )
1 N + i v i + 1 , j i + 1 − v i , j + 1 ≥ 1 N + i i + 1 [ α i + 1 , j ( 1 N + ( i + 1 ) v i + 2 , j i + 2 ) + ( 1 − α i + 1 , j ) v i + 1 , j + 1 ] − ( α i + 1 , j + ϵ ) [ 1 N + i v i + 1 , j + 1 i + 1 ] − ( 1 − α i + 1 , j − ϵ ) v i , j + 2 = i α i + 1 , j i + 1 [ 1 N + ( i + 1 ) v i + 2 , j i + 2 − v i + 1 , j + 1 ] + ( 1 − α i + 1 , j − ϵ ) [ 1 N + i v i + 1 , j + 1 i + 1 − v i , j + 2 ] . (34) \begin{aligned}
\frac{1}{N}+\frac{i v_{i+1,j}}{i+1}-v_{i,j+1}
&\ge\frac{1}{N}+\frac{i}{i+1}\left[\alpha_{i+1,j}\left(\frac{1}{N}+\frac{(i+1)v_{i+2,j}}{i+2}\right)+(1-\alpha_{i+1,j})v_{i+1,j+1}\right]\\
&\quad-(\alpha_{i+1,j}+\epsilon)\left[\frac{1}{N}+\frac{i v_{i+1,j+1}}{i+1}\right]-(1-\alpha_{i+1,j}-\epsilon)v_{i,j+2}\\
&= \frac{i\alpha_{i+1,j}}{i+1}\left[\frac{1}{N}+\frac{(i+1)v_{i+2,j}}{i+2}-v_{i+1,j+1}\right]\\
&\quad+(1-\alpha_{i+1,j}-\epsilon)\left[\frac{1}{N}+\frac{i v_{i+1,j+1}}{i+1}-v_{i,j+2}\right]. \tag*{(34)}
\end{aligned} N 1 + i + 1 i v i + 1 , j − v i , j + 1 ≥ N 1 + i + 1 i [ α i + 1 , j ( N 1 + i + 2 ( i + 1 ) v i + 2 , j ) + ( 1 − α i + 1 , j ) v i + 1 , j + 1 ] − ( α i + 1 , j + ϵ ) [ N 1 + i + 1 i v i + 1 , j + 1 ] − ( 1 − α i + 1 , j − ϵ ) v i , j + 2 = i + 1 i α i + 1 , j [ N 1 + i + 2 ( i + 1 ) v i + 2 , j − v i + 1 , j + 1 ] + ( 1 − α i + 1 , j − ϵ ) [ N 1 + i + 1 i v i + 1 , j + 1 − v i , j + 2 ] . (34)
Define the set U m U_m U m iteratively for m ≥ 1 m\ge1 m ≥ 1 as
U m = U m − 1 ∪ { ( i , j ) : ( i + 1 , j ) ∈ U m − 1 , ( i , j + 1 ) ∈ U m − 1 , v i + 1 , j ≤ i + 1 N } . U_m=U_{m-1}\cup\left\{(i,j):(i+1,j)\in U_{m-1},(i,j+1)\in U_{m-1},v_{i+1,j}\le\frac{i+1}{N}\right\}. U m = U m − 1 ∪ { ( i , j ) : ( i + 1 , j ) ∈ U m − 1 , ( i , j + 1 ) ∈ U m − 1 , v i + 1 , j ≤ N i + 1 } .
It follows that U m U_m U m denotes the set of ( i , j ) (i,j) ( i , j ) such that in m m m steps of the search process the state is guaranteed to have reached (or passed through) the set U 0 U_0 U 0 and it is optimal to accept a candidate in state ( i + 1 , j , 1 ) (i+1,j,1) ( i + 1 , j , 1 ) . From Inequality (32), for ( i , j ) ∈ U 0 (i,j)\in U_0 ( i , j ) ∈ U 0 , we have v i + 1 , j ≥ v i + 1 , j + 1 v_{i+1,j}\ge v_{i+1,j+1} v i + 1 , j ≥ v i + 1 , j + 1 . Hence, given that a candidate should be accepted in state ( i + 1 , j , 1 ) (i+1,j,1) ( i + 1 , j , 1 ) , it is also optimal to accept a candidate in state ( i + 1 , j + 1 , 1 ) (i+1,j+1,1) ( i + 1 , j + 1 , 1 ) . From Inequality (34) it then follows that Inequality (32) holds for ( i , j ) ∈ U 1 (i,j) \in U_1 ( i , j ) ∈ U 1 . Similarly, if this inequality holds for ( i , j ) ∈ U m (i,j) \in U_m ( i , j ) ∈ U m , then it holds for ( i , j ) ∈ U m + 1 (i,j) \in U_{m+1} ( i , j ) ∈ U m + 1 . It then follows by induction that this inequality holds whenever it is optimal to accept a candidate in state ( i + 1 , j , 1 ) (i+1,j,1) ( i + 1 , j , 1 ) . In addition, whenever v i , j ≤ i N v_{i,j} \le\frac{i}{N} v i , j ≤ N i , then v i + 1 , j ≤ i + 1 N v_{i+1,j} \le\frac{i+1}{N} v i + 1 , j ≤ N i + 1 and from the dynamic programming equation it follows that v i , j ≥ v i , j + 1 v_{i,j} \ge v_{i,j+1} v i , j ≥ v i , j + 1 for such ( i , j ) (i,j) ( i , j ) . Hence, if it is optimal to accept a candidate in state ( i , j , 1 ) (i,j,1) ( i , j , 1 ) , then it is optimal to accept a candidate in states ( i + 1 , j , 1 ) (i+1,j,1) ( i + 1 , j , 1 ) and ( i , j + 1 , 1 ) (i,j+1,1) ( i , j + 1 , 1 ) . Thus it follows by induction that if the search process enters a region in which it is optimal to accept a candidate of type 1, it will be optimal to accept a candidate of type 1 at any later moment. By symmetry, an analogous result holds for candidates of type 2.
Proof of Lemma 9
For all N N N , i N ≥ ⌈ N + 1 2 ⌉ i_N \ge\left\lceil\frac{N+1}{2} \right\rceil i N ≥ ⌈ 2 N + 1 ⌉ .
For N = 2 m N=2m N = 2 m and N = 2 m + 1 N=2m+1 N = 2 m + 1 we shall prove that it is not optimal to stop before time ⌈ N + 1 2 ⌉ \left\lceil\frac{N+1}{2} \right\rceil ⌈ 2 N + 1 ⌉ .
First we assume that N = 2 m N=2m N = 2 m , i.e. N N N is even. We shall prove that in the state ( m , m , 1 ) (m,m,1) ( m , m , 1 ) it is not optimal to stop. Namely we are going to show that
w m , m > m 2 m = 1 2 . (35) w_{m,m} > \frac{m}{2m} = \frac{1}{2}. \tag*{(35)} w m , m > 2 m m = 2 1 . (35)
We have
w m , m = 2 m 2 4 m 2 ∑ k = m 2 m − 1 1 k + m 2 4 m 2 ∑ u = 1 m ∑ v = 1 m ( 2 m − u − 1 m − 1 ) ( 2 m − v − 1 m − 1 ) ( 2 m − 1 m − 1 ) 2 2 u + v . w_{m,m}=2\frac{m^2}{4m^2}\sum_{k=m}^{2m-1}\frac{1}{k}+\frac{m^2}{4m^2}\sum_{u=1}^{m}\sum_{v=1}^{m}\frac{\binom{2m-u-1}{m-1}\binom{2m-v-1}{m-1}}{\binom{2m-1}{m-1}^2}\frac{2}{u+v}. w m , m = 2 4 m 2 m 2 k = m ∑ 2 m − 1 k 1 + 4 m 2 m 2 u = 1 ∑ m v = 1 ∑ m ( m − 1 2 m − 1 ) 2 ( m − 1 2 m − u − 1 ) ( m − 1 2 m − v − 1 ) u + v 2 .
Thus inequality (35) takes the form
∑ k = m 2 m − 1 1 k + ∑ u = 1 m ∑ v = 1 m ( 2 m − u − 1 m − 1 ) ( 2 m − v − 1 m − 1 ) ( 2 m − 1 m − 1 ) 2 1 u + v > 1. (36) \sum_{k=m}^{2m-1}\frac{1}{k}+\sum_{u=1}^{m}\sum_{v=1}^{m}\frac{\binom{2m-u-1}{m-1}\binom{2m-v-1}{m-1}}{\binom{2m-1}{m-1}^2}\frac{1}{u+v}>1. \tag*{(36)} k = m ∑ 2 m − 1 k 1 + u = 1 ∑ m v = 1 ∑ m ( m − 1 2 m − 1 ) 2 ( m − 1 2 m − u − 1 ) ( m − 1 2 m − v − 1 ) u + v 1 > 1. (36)
Let us note that
∑ u = 1 m ( 2 m − u − 1 m − 1 ) = ( 2 m − 1 m − 1 ) . \sum_{u=1}^{m}\binom{2m-u-1}{m-1}=\binom{2m-1}{m-1}. u = 1 ∑ m ( m − 1 2 m − u − 1 ) = ( m − 1 2 m − 1 ) .
Thus if we set
α ( m , u ) : = ( 2 m − u − 1 m − 1 ) ( 2 m − 1 m − 1 ) , \alpha(m,u):=\frac{\binom{2m-u-1}{m-1}}{\binom{2m-1}{m-1}}, α ( m , u ) := ( m − 1 2 m − 1 ) ( m − 1 2 m − u − 1 ) ,
and
α ( m , v ) : = ( 2 m − v − 1 m − 1 ) ( 2 m − 1 m − 1 ) , \alpha(m,v):=\frac{\binom{2m-v-1}{m-1}}{\binom{2m-1}{m-1}}, α ( m , v ) := ( m − 1 2 m − 1 ) ( m − 1 2 m − v − 1 ) ,
then
∑ u = 1 m α ( m , u ) = 1 and ∑ v = 1 m α ( m , v ) = 1 \sum_{u=1}^{m}\alpha(m,u)=1\quad\text{and}\quad\sum_{v=1}^{m}\alpha(m,v)=1 u = 1 ∑ m α ( m , u ) = 1 and v = 1 ∑ m α ( m , v ) = 1
and
∑ u , v = 1 m α ( m , u ) α ( m , v ) = 1. \sum_{u,v=1}^{m}\alpha(m,u)\alpha(m,v)=1. u , v = 1 ∑ m α ( m , u ) α ( m , v ) = 1.
Thus inequality (36) can be written as
∑ k = m 2 m − 1 1 k + ∑ u , v = 1 m α ( m , u ) α ( m , v ) 1 u + v > ∑ u , v = 1 m α ( m , u ) α ( m , v ) . (37) \sum_{k=m}^{2m-1}\frac{1}{k}+\sum_{u,v=1}^{m}\alpha(m,u)\alpha(m,v)\frac{1}{u+v}>\sum_{u,v=1}^{m}\alpha(m,u)\alpha(m,v). \tag*{(37)} k = m ∑ 2 m − 1 k 1 + u , v = 1 ∑ m α ( m , u ) α ( m , v ) u + v 1 > u , v = 1 ∑ m α ( m , u ) α ( m , v ) . (37)
We can still transform (37) to the form
∑ k = m 2 m − 1 1 k > ∑ u , v = 1 m α ( m , u ) α ( m , v ) ( 1 − 1 u + v ) . (38) \sum_{k=m}^{2m-1}\frac{1}{k}>\sum_{u,v=1}^{m}\alpha(m,u)\alpha(m,v)\left(1-\frac{1}{u+v}\right). \tag*{(38)} k = m ∑ 2 m − 1 k 1 > u , v = 1 ∑ m α ( m , u ) α ( m , v ) ( 1 − u + v 1 ) . (38)
The right-hand side of (38) can be expressed as
∑ k = m 2 m − 1 1 k > ∑ u , v = 1 m α ( m , u ) α ( m , v ) ( 1 − 1 u + v ) = ∑ k = 2 2 m ∑ 1 ≤ u , v ≤ m u + v = k α ( m , u ) α ( m , v ) ( 1 − 1 k ) . \sum_{k=m}^{2m-1}\frac{1}{k}>\sum_{u,v=1}^{m}\alpha(m,u)\alpha(m,v)\left(1-\frac{1}{u+v}\right)=\sum_{k=2}^{2m}\sum_{\substack{1\le u,v\le m\\u+v=k}}\alpha(m,u)\alpha(m,v)\left(1-\frac{1}{k}\right). k = m ∑ 2 m − 1 k 1 > u , v = 1 ∑ m α ( m , u ) α ( m , v ) ( 1 − u + v 1 ) = k = 2 ∑ 2 m 1 ≤ u , v ≤ m u + v = k ∑ α ( m , u ) α ( m , v ) ( 1 − k 1 ) .
Because there is no more than k − 1 k-1 k − 1 pairs ( u , v ) (u,v) ( u , v ) such that u + v = k u+v=k u + v = k we obtain for the right-hand side of (38) we have the following estimation
∑ k = 2 2 m ∑ 1 ≤ u , v ≤ m u + v = k α ( m , u ) α ( m , v ) ( 1 − 1 k ) < ( m 2 m − 1 ) 2 ( 1 − 1 2 ) + 2 ( m 2 m − 1 ) 2 ⋅ 1 2 ( 1 − 1 3 ) + ∑ k = 4 ∞ ( 1 2 ) k ( k − 1 k ) ( k − 1 ) = ∑ k = 2 ∞ ( 1 2 ) k ( k − 1 k ) ( k − 1 ) + [ ( m 2 m − 1 ) 2 ( 1 − 1 2 ) − ( 1 2 ) 2 ( 1 − 1 2 ) ] + [ 2 ( m 2 m − 1 ) 2 ⋅ 1 2 ( 1 − 1 3 ) − 2 ( 1 2 ) 3 ( 1 − 1 3 ) ] < ∑ k = 2 ∞ ( 1 2 ) k ( k − 1 k ) ( k − 1 ) + 1 2 ( 2 m − 1 ) 2 + 1 3 ( 2 m − 1 ) 2 = ∑ k = 2 ∞ ( 1 2 ) k ( k − 1 k ) ( k − 1 ) + 5 6 ( 2 m − 1 ) 2 . \begin{aligned}
\sum_{k=2}^{2m}\sum_{\substack{1\le u,v\le m\\u+v=k}}\alpha(m,u)\alpha(m,v)\left(1-\frac{1}{k}\right)
&<
\left(\frac{m}{2m-1}\right)^2\left(1-\frac{1}{2}\right)
+2\left(\frac{m}{2m-1}\right)^2\cdot\frac{1}{2}\left(1-\frac{1}{3}\right)
+\sum_{k=4}^{\infty}\left(\frac{1}{2}\right)^k\left(\frac{k-1}{k}\right)(k-1)\\
&=\sum_{k=2}^{\infty}\left(\frac{1}{2}\right)^k\left(\frac{k-1}{k}\right)(k-1)
+\left[\left(\frac{m}{2m-1}\right)^2\left(1-\frac{1}{2}\right)
-\left(\frac{1}{2}\right)^2\left(1-\frac{1}{2}\right)\right]\\
&\quad+\left[2\left(\frac{m}{2m-1}\right)^2\cdot\frac{1}{2}\left(1-\frac{1}{3}\right)
-2\left(\frac{1}{2}\right)^3\left(1-\frac{1}{3}\right)\right]\\
&<\sum_{k=2}^{\infty}\left(\frac{1}{2}\right)^k\left(\frac{k-1}{k}\right)(k-1)
+\frac{1}{2(2m-1)^2}+\frac{1}{3(2m-1)^2}\\
&=\sum_{k=2}^{\infty}\left(\frac{1}{2}\right)^k\left(\frac{k-1}{k}\right)(k-1)
+\frac{5}{6(2m-1)^2}.
\end{aligned} k = 2 ∑ 2 m 1 ≤ u , v ≤ m u + v = k ∑ α ( m , u ) α ( m , v ) ( 1 − k 1 ) < ( 2 m − 1 m ) 2 ( 1 − 2 1 ) + 2 ( 2 m − 1 m ) 2 ⋅ 2 1 ( 1 − 3 1 ) + k = 4 ∑ ∞ ( 2 1 ) k ( k k − 1 ) ( k − 1 ) = k = 2 ∑ ∞ ( 2 1 ) k ( k k − 1 ) ( k − 1 ) + [ ( 2 m − 1 m ) 2 ( 1 − 2 1 ) − ( 2 1 ) 2 ( 1 − 2 1 ) ] + [ 2 ( 2 m − 1 m ) 2 ⋅ 2 1 ( 1 − 3 1 ) − 2 ( 2 1 ) 3 ( 1 − 3 1 ) ] < k = 2 ∑ ∞ ( 2 1 ) k ( k k − 1 ) ( k − 1 ) + 2 ( 2 m − 1 ) 2 1 + 3 ( 2 m − 1 ) 2 1 = k = 2 ∑ ∞ ( 2 1 ) k ( k k − 1 ) ( k − 1 ) + 6 ( 2 m − 1 ) 2 5 .
As
∑ k = 2 ∞ ( 1 2 ) k ( k − 1 k ) ( k − 1 ) = 1 − ln 2 , \sum_{k=2}^{\infty}\left(\frac{1}{2}\right)^k\left(\frac{k-1}{k}\right)(k-1)=1-\ln2, k = 2 ∑ ∞ ( 2 1 ) k ( k k − 1 ) ( k − 1 ) = 1 − ln 2 ,
it is enough to notice now that
∑ k = 1 2 m − 2 1 k + ( 1 2 m − 1 − 5 6 ( 2 m − 1 ) 2 ) > ln 2 , \sum_{k=1}^{2m-2}\frac{1}{k}+\left(\frac{1}{2m-1}-\frac{5}{6(2m-1)^2}\right)>\ln2, k = 1 ∑ 2 m − 2 k 1 + ( 2 m − 1 1 − 6 ( 2 m − 1 ) 2 5 ) > ln 2 ,
and this follows by the well known estimation
∑ k = 1 2 m − 1 1 k − ln 2 > 1 4 m . \sum_{k=1}^{2m-1}\frac{1}{k}-\ln2>\frac{1}{4m}. k = 1 ∑ 2 m − 1 k 1 − ln 2 > 4 m 1 .
For N = 2 m + 1 N=2m+1 N = 2 m + 1 the proof that w m , m > m 2 m + 1 w_{m,m}>\frac{m}{2m+1} w m , m > 2 m + 1 m is analogous.
Proof of Lemma 10
We first consider that case that N N N is an even integer such that N = 2 M ≥ 4 N=2M\ge4 N = 2 M ≥ 4 . Let i , j ≥ 1 i,j\ge1 i , j ≥ 1 . Denote
Z 1 ( i , j ) = i N 2 ∑ r = 0 N − j − 1 j j + r . Z_1(i,j)=\frac{i}{N^2}\sum_{r=0}^{N-j-1}\frac{j}{j+r}. Z 1 ( i , j ) = N 2 i r = 0 ∑ N − j − 1 j + r j .
Z 2 ( i , j ) = j N 2 ∑ r = 0 N − i − 1 i i + r . Z_2(i,j)=\frac{j}{N^2}\sum_{r=0}^{N-i-1}\frac{i}{i+r}. Z 2 ( i , j ) = N 2 j r = 0 ∑ N − i − 1 i + r i .
Z 3 ( i , j ) = i j N 2 ∑ u = 2 N − i + 1 ∑ v = 2 N − j + 1 ( N − u i − 1 ) ( N − 1 i − 1 ) ( N − v j − 1 ) ( N − 1 j − 1 ) 2 u + v − 2 . Z_3(i,j)=\frac{ij}{N^2}\sum_{u=2}^{N-i+1}\sum_{v=2}^{N-j+1}\frac{\binom{N-u}{i-1}}{\binom{N-1}{i-1}}\frac{\binom{N-v}{j-1}}{\binom{N-1}{j-1}}\frac{2}{u+v-2}. Z 3 ( i , j ) = N 2 ij u = 2 ∑ N − i + 1 v = 2 ∑ N − j + 1 ( i − 1 N − 1 ) ( i − 1 N − u ) ( j − 1 N − 1 ) ( j − 1 N − v ) u + v − 2 2 .
It follows from (10) that w i , j = Z 1 ( i , j ) + Z 2 ( i , j ) + Z 3 ( i , j ) w_{i,j}=Z_1(i,j)+Z_2(i,j)+Z_3(i,j) w i , j = Z 1 ( i , j ) + Z 2 ( i , j ) + Z 3 ( i , j ) . We have
Z 1 ( N 2 + 1 , N 2 + 1 ) = Z 2 ( N 2 + 1 , N 2 + 1 ) = ( 1 + N 2 N ) 2 ∑ s = N 2 + 1 N − 1 1 s ≤ ( 1 + N 2 N ) 2 ( ln ( N − 1 ) − ln ( N 2 ) ) . \begin{aligned}
Z_1\left(\frac{N}{2}+1,\frac{N}{2}+1\right)=Z_2\left(\frac{N}{2}+1,\frac{N}{2}+1\right)=\left(\frac{1+\frac{N}{2}}{N}\right)^2\sum_{s=\frac{N}{2}+1}^{N-1}\frac{1}{s} \\
&\le\left(\frac{1+\frac{N}{2}}{N}\right)^2\left(\ln(N-1)-\ln\left(\frac{N}{2}\right)\right).
\end{aligned} Z 1 ( 2 N + 1 , 2 N + 1 ) = Z 2 ( 2 N + 1 , 2 N + 1 ) = ( N 1 + 2 N ) 2 s = 2 N + 1 ∑ N − 1 s 1 ≤ ( N 1 + 2 N ) 2 ( ln ( N − 1 ) − ln ( 2 N ) ) .
We have
( N − u N 2 ) ( N − 1 N 2 ) = ( N 2 − 1 ) ( N 2 − 2 ) ⋯ ( N 2 − u + 1 ) ( N − 1 ) ( N − 2 ) ⋯ ( N − u + 1 ) < ( N 2 − 1 N − 1 ) u − 1 , \frac{\binom{N-u}{\frac{N}{2}}}{\binom{N-1}{\frac{N}{2}}}=\frac{\left(\frac{N}{2}-1\right)\left(\frac{N}{2}-2\right)\cdots\left(\frac{N}{2}-u+1\right)}{(N-1)(N-2)\cdots(N-u+1)}<\left(\frac{\frac{N}{2}-1}{N-1}\right)^{u-1}, ( 2 N N − 1 ) ( 2 N N − u ) = ( N − 1 ) ( N − 2 ) ⋯ ( N − u + 1 ) ( 2 N − 1 ) ( 2 N − 2 ) ⋯ ( 2 N − u + 1 ) < ( N − 1 2 N − 1 ) u − 1 ,
and
( N − v N 2 − 1 ) ( N − 1 N 2 − 1 ) = ( N 2 − 1 ) ( N 2 − 2 ) ⋯ ( N 2 − v + 1 ) ( N − 1 ) ( N − 2 ) ⋯ ( N − u + 1 ) < ( N 2 − 1 N − 1 ) v − 1 . \frac{\binom{N-v}{\frac{N}{2}-1}}{\binom{N-1}{\frac{N}{2}-1}}=\frac{\left(\frac{N}{2}-1\right)\left(\frac{N}{2}-2\right)\cdots\left(\frac{N}{2}-v+1\right)}{(N-1)(N-2)\cdots(N-u+1)}<\left(\frac{\frac{N}{2}-1}{N-1}\right)^{v-1}. ( 2 N − 1 N − 1 ) ( 2 N − 1 N − v ) = ( N − 1 ) ( N − 2 ) ⋯ ( N − u + 1 ) ( 2 N − 1 ) ( 2 N − 2 ) ⋯ ( 2 N − v + 1 ) < ( N − 1 2 N − 1 ) v − 1 .
Hence
Z 3 ( N 2 + 1 , N 2 + 1 ) < ( 1 + N 2 N ) 2 ∑ u = 2 ∞ ∑ v = 2 ∞ ( N 2 − 1 N − 1 ) u + v − 2 2 u + v − 2 = 2 ( 1 + N 2 N ) 2 ∑ k = 1 ∞ ∑ l = 1 ∞ 1 k + l ( N 2 − 1 N − 1 ) k + l = 2 ( 1 + N 2 N ) 2 ∑ m = 2 ∞ m − 1 m ( N 2 − 1 N − 1 ) m = 2 ( 1 + N 2 N ) 2 ( ( N 2 − 1 N − 1 ) 2 1 − ( N 2 − 1 N − 1 ) − ∑ m = 2 ∞ 1 m ( N 2 − 1 N − 1 ) m ) = 2 ( 1 + N 2 N ) 2 ( N 2 − 1 N − 1 ) 2 1 − ( N 2 − 1 N − 1 ) − 2 ( 1 + N 2 N ) 2 ∑ m = 2 ∞ 1 m ( N 2 − 1 N − 1 ) m = 2 ( 1 + N 2 N ) 2 ( N 2 − 1 N − 1 ) 2 1 − ( N 2 − 1 N − 1 ) − 2 ( 1 + N 2 N ) 2 ∑ m = 2 ∞ 1 m x m ∣ x = N 2 − 1 N − 1 . \begin{aligned}
Z_3\left(\frac{N}{2}+1,\frac{N}{2}+1\right)<\left(\frac{1+\frac{N}{2}}{N}\right)^2\sum_{u=2}^{\infty}\sum_{v=2}^{\infty}\left(\frac{\frac{N}{2}-1}{N-1}\right)^{u+v-2}\frac{2}{u+v-2} \\
&=2\left(\frac{1+\frac{N}{2}}{N}\right)^2\sum_{k=1}^{\infty}\sum_{l=1}^{\infty}\frac{1}{k+l}\left(\frac{\frac{N}{2}-1}{N-1}\right)^{k+l}
=2\left(\frac{1+\frac{N}{2}}{N}\right)^2\sum_{m=2}^{\infty}\frac{m-1}{m}\left(\frac{\frac{N}{2}-1}{N-1}\right)^m \\
&=2\left(\frac{1+\frac{N}{2}}{N}\right)^2\left(\frac{\left(\frac{\frac{N}{2}-1}{N-1}\right)^2}{1-\left(\frac{\frac{N}{2}-1}{N-1}\right)}-\sum_{m=2}^{\infty}\frac{1}{m}\left(\frac{\frac{N}{2}-1}{N-1}\right)^m\right) \\
&=2\left(\frac{1+\frac{N}{2}}{N}\right)^2\frac{\left(\frac{\frac{N}{2}-1}{N-1}\right)^2}{1-\left(\frac{\frac{N}{2}-1}{N-1}\right)}
-2\left(\frac{1+\frac{N}{2}}{N}\right)^2\sum_{m=2}^{\infty}\frac{1}{m}\left(\frac{\frac{N}{2}-1}{N-1}\right)^m \\
&=2\left(\frac{1+\frac{N}{2}}{N}\right)^2\frac{\left(\frac{\frac{N}{2}-1}{N-1}\right)^2}{1-\left(\frac{\frac{N}{2}-1}{N-1}\right)}
-2\left(\frac{1+\frac{N}{2}}{N}\right)^2\left.\sum_{m=2}^{\infty}\frac{1}{m}x^m\right|_{x=\frac{\frac{N}{2}-1}{N-1}}.
\end{aligned} Z 3 ( 2 N + 1 , 2 N + 1 ) < ( N 1 + 2 N ) 2 u = 2 ∑ ∞ v = 2 ∑ ∞ ( N − 1 2 N − 1 ) u + v − 2 u + v − 2 2 = 2 ( N 1 + 2 N ) 2 k = 1 ∑ ∞ l = 1 ∑ ∞ k + l 1 ( N − 1 2 N − 1 ) k + l = 2 ( N 1 + 2 N ) 2 m = 2 ∑ ∞ m m − 1 ( N − 1 2 N − 1 ) m = 2 ( N 1 + 2 N ) 2 1 − ( N − 1 2 N − 1 ) ( N − 1 2 N − 1 ) 2 − m = 2 ∑ ∞ m 1 ( N − 1 2 N − 1 ) m = 2 ( N 1 + 2 N ) 2 1 − ( N − 1 2 N − 1 ) ( N − 1 2 N − 1 ) 2 − 2 ( N 1 + 2 N ) 2 m = 2 ∑ ∞ m 1 ( N − 1 2 N − 1 ) m = 2 ( N 1 + 2 N ) 2 1 − ( N − 1 2 N − 1 ) ( N − 1 2 N − 1 ) 2 − 2 ( N 1 + 2 N ) 2 m = 2 ∑ ∞ m 1 x m x = N − 1 2 N − 1 .
further we set a = N 2 − 1 N − 1 a=\frac{\frac{N}{2}-1}{N-1} a = N − 1 2 N − 1 ,
= 2 ( 1 + N 2 N ) 2 ( N 2 − 1 N − 1 ) 2 1 − ( N 2 − 1 N − 1 ) − 2 ( 1 + N 2 N ) 2 ∑ m = 2 ∞ ∫ 0 a x m − 1 d x = 2 ( 1 + N 2 N ) 2 ( N 2 − 1 N − 1 ) 2 1 − ( N 2 − 1 N − 1 ) − 2 ( 1 + N 2 N ) 2 ∫ 0 a ∑ m = 1 ∞ x m d x = 2 ( 1 + N 2 N ) 2 ( N 2 − 1 N − 1 ) 2 1 − ( N 2 − 1 N − 1 ) − 2 ( 1 + N 2 N ) 2 ∫ 0 a x 1 − x d x = 2 ( 1 + N 2 N ) 2 ( N 2 − 1 N − 1 ) 2 1 − ( N 2 − 1 N − 1 ) − 2 ( 1 + N 2 N ) 2 ∫ 0 a ( ( − 1 ) + 1 1 − x ) d x = 2 ( 1 + N 2 N ) 2 ( N 2 − 1 N − 1 ) 2 1 − ( N 2 − 1 N − 1 ) − 2 ( 1 + N 2 N ) 2 ( − a − ln ( 1 − a ) ) \begin{aligned}
&=2\left(\frac{1+\frac{N}{2}}{N}\right)^2\frac{\left(\frac{\frac{N}{2}-1}{N-1}\right)^2}{1-\left(\frac{\frac{N}{2}-1}{N-1}\right)}-2\left(\frac{1+\frac{N}{2}}{N}\right)^2\sum_{m=2}^{\infty}\int_0^a x^{m-1}\,dx\\
&=2\left(\frac{1+\frac{N}{2}}{N}\right)^2\frac{\left(\frac{\frac{N}{2}-1}{N-1}\right)^2}{1-\left(\frac{\frac{N}{2}-1}{N-1}\right)}-2\left(\frac{1+\frac{N}{2}}{N}\right)^2\int_0^a\sum_{m=1}^{\infty}x^m\,dx\\
&=2\left(\frac{1+\frac{N}{2}}{N}\right)^2\frac{\left(\frac{\frac{N}{2}-1}{N-1}\right)^2}{1-\left(\frac{\frac{N}{2}-1}{N-1}\right)}-2\left(\frac{1+\frac{N}{2}}{N}\right)^2\int_0^a\frac{x}{1-x}\,dx\\
&=2\left(\frac{1+\frac{N}{2}}{N}\right)^2\frac{\left(\frac{\frac{N}{2}-1}{N-1}\right)^2}{1-\left(\frac{\frac{N}{2}-1}{N-1}\right)}-2\left(\frac{1+\frac{N}{2}}{N}\right)^2\int_0^a\left((-1)+\frac{1}{1-x}\right)\,dx\\
&=2\left(\frac{1+\frac{N}{2}}{N}\right)^2\frac{\left(\frac{\frac{N}{2}-1}{N-1}\right)^2}{1-\left(\frac{\frac{N}{2}-1}{N-1}\right)}-2\left(\frac{1+\frac{N}{2}}{N}\right)^2\left(-a-\ln(1-a)\right)
\end{aligned} = 2 ( N 1 + 2 N ) 2 1 − ( N − 1 2 N − 1 ) ( N − 1 2 N − 1 ) 2 − 2 ( N 1 + 2 N ) 2 m = 2 ∑ ∞ ∫ 0 a x m − 1 d x = 2 ( N 1 + 2 N ) 2 1 − ( N − 1 2 N − 1 ) ( N − 1 2 N − 1 ) 2 − 2 ( N 1 + 2 N ) 2 ∫ 0 a m = 1 ∑ ∞ x m d x = 2 ( N 1 + 2 N ) 2 1 − ( N − 1 2 N − 1 ) ( N − 1 2 N − 1 ) 2 − 2 ( N 1 + 2 N ) 2 ∫ 0 a 1 − x x d x = 2 ( N 1 + 2 N ) 2 1 − ( N − 1 2 N − 1 ) ( N − 1 2 N − 1 ) 2 − 2 ( N 1 + 2 N ) 2 ∫ 0 a ( ( − 1 ) + 1 − x 1 ) d x = 2 ( N 1 + 2 N ) 2 1 − ( N − 1 2 N − 1 ) ( N − 1 2 N − 1 ) 2 − 2 ( N 1 + 2 N ) 2 ( − a − ln ( 1 − a ) )
1 2 ⋅ 1 + N 2 N ⋅ N 3 − 4 N − 2 N 2 + 8 N 3 − N 2 + 1 2 ⋅ 1 + N 2 N ⋅ N 2 − 4 N 2 − N − 2 ( 1 + N 2 N ) 2 ( ln ( N − 1 ) − ln ( N 2 ) ) \frac{1}{2}\cdot\frac{1+\frac{N}{2}}{N}\cdot\frac{N^3-4N-2N^2+8}{N^3-N^2}+\frac{1}{2}\cdot\frac{1+\frac{N}{2}}{N}\cdot\frac{N^2-4}{N^2-N}-2\left(\frac{1+\frac{N}{2}}{N}\right)^2\left(\ln(N-1)-\ln\left(\frac{N}{2}\right)\right) 2 1 ⋅ N 1 + 2 N ⋅ N 3 − N 2 N 3 − 4 N − 2 N 2 + 8 + 2 1 ⋅ N 1 + 2 N ⋅ N 2 − N N 2 − 4 − 2 ( N 1 + 2 N ) 2 ( ln ( N − 1 ) − ln ( 2 N ) )
= 1 + N 2 N ⋅ N 3 − N 2 − 4 N + 4 N 3 − N 2 − 2 ( 1 + N 2 N ) 2 ( ln ( N − 1 ) − ln ( N 2 ) ) ≤ 1 + N 2 N − 2 ( 1 + N 2 N ) 2 ( ln ( N − 1 ) − ln ( N 2 ) ) \begin{aligned}
&=\frac{1+\frac{N}{2}}{N}\cdot\frac{N^3-N^2-4N+4}{N^3-N^2}-2\left(\frac{1+\frac{N}{2}}{N}\right)^2\left(\ln(N-1)-\ln\left(\frac{N}{2}\right)\right)\\
&\le\frac{1+\frac{N}{2}}{N}-2\left(\frac{1+\frac{N}{2}}{N}\right)^2\left(\ln(N-1)-\ln\left(\frac{N}{2}\right)\right)
\end{aligned} = N 1 + 2 N ⋅ N 3 − N 2 N 3 − N 2 − 4 N + 4 − 2 ( N 1 + 2 N ) 2 ( ln ( N − 1 ) − ln ( 2 N ) ) ≤ N 1 + 2 N − 2 ( N 1 + 2 N ) 2 ( ln ( N − 1 ) − ln ( 2 N ) )
Hence, for M = N 2 M=\frac{N}{2} M = 2 N
w M + 1 , M + 1 = 2 Z 1 ( 1 + N 2 , 1 + N 2 ) + Z 3 ( 1 + N 2 , 1 + N 2 ) ≤ 1 + M N . w_{M+1,M+1}=2Z_1\left(1+\frac{N}{2},1+\frac{N}{2}\right)+Z_3\left(1+\frac{N}{2},1+\frac{N}{2}\right)\le\frac{1+M}{N}. w M + 1 , M + 1 = 2 Z 1 ( 1 + 2 N , 1 + 2 N ) + Z 3 ( 1 + 2 N , 1 + 2 N ) ≤ N 1 + M .
Now let us assume that N N N is odd, N = 2 M + 1 ≥ 3 N=2M+1\ge3 N = 2 M + 1 ≥ 3 and i , j ≥ 1 i,j\ge1 i , j ≥ 1 . As in the case where N N N is even
w M + 1 , M + 1 = 2 Z 1 ( M + 1 , M + 1 ) + Z 3 ( M + 1 , M + 1 ) . w_{M+1,M+1}=2Z_1(M+1,M+1)+Z_3(M+1,M+1). w M + 1 , M + 1 = 2 Z 1 ( M + 1 , M + 1 ) + Z 3 ( M + 1 , M + 1 ) .
We have
Z 1 ( M + 1 , M + 1 ) = ( M + 1 2 M + 1 ) 2 ∑ s = M + 1 2 M 1 s . Z_1(M+1,M+1)=\left(\frac{M+1}{2M+1}\right)^2\sum_{s=M+1}^{2M}\frac{1}{s}. Z 1 ( M + 1 , M + 1 ) = ( 2 M + 1 M + 1 ) 2 s = M + 1 ∑ 2 M s 1 .
Also,
Z 3 ( M + 1 , M + 1 ) = 2 ⋅ ( M + 1 2 M + 1 ) 2 ∑ u = 2 , v = 2 M + 1 ( 2 M + 1 − u M ) ( 2 M + 1 − v M ) ( 2 M M ) 2 1 u + v − 2 = 2 ⋅ ( M + 1 2 M + 1 ) 2 ∑ u = 1 , v = 1 M ( 2 M − u M ) ( 2 M − v M ) ( 2 M M ) 2 1 u + v . \begin{aligned}
Z_3(M+1,M+1)
&=2\cdot\left(\frac{M+1}{2M+1}\right)^2\sum_{u=2,v=2}^{M+1}\frac{\binom{2M+1-u}{M}\binom{2M+1-v}{M}}{\binom{2M}{M}^2}\frac{1}{u+v-2}\\
&=2\cdot\left(\frac{M+1}{2M+1}\right)^2\sum_{u=1,v=1}^{M}\frac{\binom{2M-u}{M}\binom{2M-v}{M}}{\binom{2M}{M}^2}\frac{1}{u+v}.
\end{aligned} Z 3 ( M + 1 , M + 1 ) = 2 ⋅ ( 2 M + 1 M + 1 ) 2 u = 2 , v = 2 ∑ M + 1 ( M 2 M ) 2 ( M 2 M + 1 − u ) ( M 2 M + 1 − v ) u + v − 2 1 = 2 ⋅ ( 2 M + 1 M + 1 ) 2 u = 1 , v = 1 ∑ M ( M 2 M ) 2 ( M 2 M − u ) ( M 2 M − v ) u + v 1 .
In addition,
( 2 M − u M ) ( 2 M M ) = M 2 M M − 1 2 M − 1 ⋯ M − u + 1 2 M − u + 1 = ∏ i = 0 u − 1 M − i 2 M − i \frac{\binom{2M-u}{M}}{\binom{2M}{M}}=\frac{M}{2M}\frac{M-1}{2M-1}\cdots\frac{M-u+1}{2M-u+1}=\prod_{i=0}^{u-1}\frac{M-i}{2M-i} ( M 2 M ) ( M 2 M − u ) = 2 M M 2 M − 1 M − 1 ⋯ 2 M − u + 1 M − u + 1 = i = 0 ∏ u − 1 2 M − i M − i
and
( 2 M − v M ) ( 2 M M ) = M 2 M M − 1 2 M − 1 ⋯ M − v + 1 2 M − v + 1 = ∏ i = 0 v − 1 M − i 2 M − i . \frac{\binom{2M-v}{M}}{\binom{2M}{M}}=\frac{M}{2M}\frac{M-1}{2M-1}\cdots\frac{M-v+1}{2M-v+1}=\prod_{i=0}^{v-1}\frac{M-i}{2M-i}. ( M 2 M ) ( M 2 M − v ) = 2 M M 2 M − 1 M − 1 ⋯ 2 M − v + 1 M − v + 1 = i = 0 ∏ v − 1 2 M − i M − i .
Thus
Z 3 ( M + 1 , M + 1 ) = 2 ⋅ ( M + 1 2 M + 1 ) 2 ∑ u = 1 , v = 1 M 1 u + v ∏ i = 0 u − 1 M − i 2 M − i ∏ i = 0 v − 1 M − i 2 M − i Z_3(M+1,M+1)=2\cdot\left(\frac{M+1}{2M+1}\right)^2\sum_{u=1,v=1}^{M}\frac{1}{u+v}\prod_{i=0}^{u-1}\frac{M-i}{2M-i}\prod_{i=0}^{v-1}\frac{M-i}{2M-i} Z 3 ( M + 1 , M + 1 ) = 2 ⋅ ( 2 M + 1 M + 1 ) 2 u = 1 , v = 1 ∑ M u + v 1 i = 0 ∏ u − 1 2 M − i M − i i = 0 ∏ v − 1 2 M − i M − i
It follows that w M + 1 , M + 1 ≤ M + 1 2 M + 1 w_{M+1,M+1}\leq\frac{M+1}{2M+1} w M + 1 , M + 1 ≤ 2 M + 1 M + 1 is equivalent to the condition
2 ( M + 1 2 M + 1 ) 2 ∑ s = M + 1 2 M 1 s + 2 ( M + 1 2 M + 1 ) 2 ∑ u = 1 , v = 1 M 1 u + v ∏ i = 0 u − 1 M − i 2 M − i ∏ i = 0 v − 1 M − i 2 M − i ≤ M + 1 2 M + 1 . 2\left(\frac{M+1}{2M+1}\right)^2\sum_{s=M+1}^{2M}\frac{1}{s}+2\left(\frac{M+1}{2M+1}\right)^2\sum_{u=1,v=1}^{M}\frac{1}{u+v}\prod_{i=0}^{u-1}\frac{M-i}{2M-i}\prod_{i=0}^{v-1}\frac{M-i}{2M-i}\leq\frac{M+1}{2M+1}. 2 ( 2 M + 1 M + 1 ) 2 s = M + 1 ∑ 2 M s 1 + 2 ( 2 M + 1 M + 1 ) 2 u = 1 , v = 1 ∑ M u + v 1 i = 0 ∏ u − 1 2 M − i M − i i = 0 ∏ v − 1 2 M − i M − i ≤ 2 M + 1 M + 1 .
This is equivalent to
∑ s = M + 1 2 M 1 s + ∑ u = 1 , v = 1 M 1 u + v ∏ i = 0 u − 1 M − i 2 M − i ∏ i = 0 v − 1 M − i 2 M − i ≤ 2 M + 1 2 M + 2 . (39) \sum_{s=M+1}^{2M}\frac{1}{s}+\sum_{u=1,v=1}^{M}\frac{1}{u+v}\prod_{i=0}^{u-1}\frac{M-i}{2M-i}\prod_{i=0}^{v-1}\frac{M-i}{2M-i}\leq\frac{2M+1}{2M+2}. \tag*{(39)} s = M + 1 ∑ 2 M s 1 + u = 1 , v = 1 ∑ M u + v 1 i = 0 ∏ u − 1 2 M − i M − i i = 0 ∏ v − 1 2 M − i M − i ≤ 2 M + 2 2 M + 1 . (39)
We have
∑ u = 1 , v = 1 M 1 u + v ∏ i = 0 u − 1 M − i 2 M − i ∏ i = 0 v − 1 M − i 2 M − i = 1 8 + 2 ∑ v = 2 M 1 v + 1 ⋅ 1 2 ⋅ 1 2 ⋅ ∏ i = 1 v − 1 M − i 2 M − i + 1 4 ∑ u , v = 2 M 1 u + v ∏ i = 1 u − 1 M − i 2 M − i ∏ i = 1 v − 1 M − i 2 M − i \begin{aligned}
\sum_{u=1,v=1}^{M}\frac{1}{u+v}\prod_{i=0}^{u-1}\frac{M-i}{2M-i}\prod_{i=0}^{v-1}\frac{M-i}{2M-i}
={}&\frac{1}{8}+2\sum_{v=2}^{M}\frac{1}{v+1}\cdot\frac{1}{2}\cdot\frac{1}{2}\cdot\prod_{i=1}^{v-1}\frac{M-i}{2M-i}\\
&+\frac{1}{4}\sum_{u,v=2}^{M}\frac{1}{u+v}\prod_{i=1}^{u-1}\frac{M-i}{2M-i}\prod_{i=1}^{v-1}\frac{M-i}{2M-i}
\end{aligned} u = 1 , v = 1 ∑ M u + v 1 i = 0 ∏ u − 1 2 M − i M − i i = 0 ∏ v − 1 2 M − i M − i = 8 1 + 2 v = 2 ∑ M v + 1 1 ⋅ 2 1 ⋅ 2 1 ⋅ i = 1 ∏ v − 1 2 M − i M − i + 4 1 u , v = 2 ∑ M u + v 1 i = 1 ∏ u − 1 2 M − i M − i i = 1 ∏ v − 1 2 M − i M − i
= 1 8 + 1 2 ( 1 3 ⋅ M − 1 2 M − 1 + M − 1 2 M − 1 ∑ v = 3 M 1 v + 1 ∏ i = 2 v − 1 M − i 2 M − i ) + 1 4 [ 1 4 ( M − 1 2 M − 1 ) 2 + 2 ∑ v = 3 M 1 v + 2 ⋅ M − 1 2 M − 1 ∏ i = 1 v − 1 M − i 2 M − i + ∑ u , v = 3 M 1 u + v ∏ i = 1 u − 1 M − i 2 M − i ∏ i = 1 v − 1 M − i 2 M − i ] \begin{aligned}
={}&\frac{1}{8}+\frac{1}{2}\left(\frac{1}{3}\cdot\frac{M-1}{2M-1}+\frac{M-1}{2M-1}\sum_{v=3}^{M}\frac{1}{v+1}\prod_{i=2}^{v-1}\frac{M-i}{2M-i}\right)\\
&+\frac{1}{4}\left[\frac{1}{4}\left(\frac{M-1}{2M-1}\right)^2+2\sum_{v=3}^{M}\frac{1}{v+2}\cdot\frac{M-1}{2M-1}\prod_{i=1}^{v-1}\frac{M-i}{2M-i}\right.\\
&\left.\qquad+\sum_{u,v=3}^{M}\frac{1}{u+v}\prod_{i=1}^{u-1}\frac{M-i}{2M-i}\prod_{i=1}^{v-1}\frac{M-i}{2M-i}\right]
\end{aligned} = 8 1 + 2 1 ( 3 1 ⋅ 2 M − 1 M − 1 + 2 M − 1 M − 1 v = 3 ∑ M v + 1 1 i = 2 ∏ v − 1 2 M − i M − i ) + 4 1 [ 4 1 ( 2 M − 1 M − 1 ) 2 + 2 v = 3 ∑ M v + 2 1 ⋅ 2 M − 1 M − 1 i = 1 ∏ v − 1 2 M − i M − i + u , v = 3 ∑ M u + v 1 i = 1 ∏ u − 1 2 M − i M − i i = 1 ∏ v − 1 2 M − i M − i ]
= 1 8 + 1 2 ⋅ M − 1 2 M − 1 ( 1 3 + ∑ v = 3 M 1 v + 1 ∏ i = 2 v − 1 M − i 2 M − i ) + 1 16 ( M − 1 2 M − 1 ) 2 + 1 4 [ 2 ( M − 1 2 M − 1 ) 2 ∑ v = 3 M 1 v + 2 ∏ i = 2 v − 1 M − i 2 M − i + ( M − 1 2 M − 1 ) 2 ∑ u , v = 3 M 1 u + v ∏ i = 2 u − 1 M − i 2 M − i ∏ i = 1 v − 1 M − i 2 M − i ] \begin{aligned}
={}&\frac{1}{8}+\frac{1}{2}\cdot\frac{M-1}{2M-1}\left(\frac{1}{3}+\sum_{v=3}^{M}\frac{1}{v+1}\prod_{i=2}^{v-1}\frac{M-i}{2M-i}\right)+\frac{1}{16}\left(\frac{M-1}{2M-1}\right)^2\\
&+\frac{1}{4}\left[2\left(\frac{M-1}{2M-1}\right)^2\sum_{v=3}^{M}\frac{1}{v+2}\prod_{i=2}^{v-1}\frac{M-i}{2M-i}\right.\\
&\left.\qquad+\left(\frac{M-1}{2M-1}\right)^2\sum_{u,v=3}^{M}\frac{1}{u+v}\prod_{i=2}^{u-1}\frac{M-i}{2M-i}\prod_{i=1}^{v-1}\frac{M-i}{2M-i}\right]
\end{aligned} = 8 1 + 2 1 ⋅ 2 M − 1 M − 1 ( 3 1 + v = 3 ∑ M v + 1 1 i = 2 ∏ v − 1 2 M − i M − i ) + 16 1 ( 2 M − 1 M − 1 ) 2 + 4 1 [ 2 ( 2 M − 1 M − 1 ) 2 v = 3 ∑ M v + 2 1 i = 2 ∏ v − 1 2 M − i M − i + ( 2 M − 1 M − 1 ) 2 u , v = 3 ∑ M u + v 1 i = 2 ∏ u − 1 2 M − i M − i i = 1 ∏ v − 1 2 M − i M − i ]
≤ 1 8 + 1 2 ⋅ M − 1 2 M − 1 ( 1 3 + ∑ v = 3 ∞ 1 v + 1 ( M − 2 2 M − 2 ) v − 2 ) + 1 4 ( M − 1 2 M − 1 ) 2 [ 1 4 + 2 ∑ v = 3 ∞ 1 v + 2 ( M − 2 2 M − 2 ) v − 2 + ∑ u , v = 3 ∞ 1 u + v ( M − 2 2 M − 2 ) u + v − 4 ] . \begin{aligned}
\leq{}&\frac{1}{8}+\frac{1}{2}\cdot\frac{M-1}{2M-1}\left(\frac{1}{3}+\sum_{v=3}^{\infty}\frac{1}{v+1}\left(\frac{M-2}{2M-2}\right)^{v-2}\right)\\
&+\frac{1}{4}\left(\frac{M-1}{2M-1}\right)^2\left[\frac{1}{4}+2\sum_{v=3}^{\infty}\frac{1}{v+2}\left(\frac{M-2}{2M-2}\right)^{v-2}+\sum_{u,v=3}^{\infty}\frac{1}{u+v}\left(\frac{M-2}{2M-2}\right)^{u+v-4}\right].
\end{aligned} ≤ 8 1 + 2 1 ⋅ 2 M − 1 M − 1 ( 3 1 + v = 3 ∑ ∞ v + 1 1 ( 2 M − 2 M − 2 ) v − 2 ) + 4 1 ( 2 M − 1 M − 1 ) 2 [ 4 1 + 2 v = 3 ∑ ∞ v + 2 1 ( 2 M − 2 M − 2 ) v − 2 + u , v = 3 ∑ ∞ u + v 1 ( 2 M − 2 M − 2 ) u + v − 4 ] .
Setting x = M − 2 2 M − 2 x=\frac{M-2}{2M-2} x = 2 M − 2 M − 2 , this expression is given by
1 8 + 1 2 ⋅ M − 1 2 M − 1 ( 1 3 + 1 x 3 ∑ ν = 3 ∞ 1 ν + 1 x ν + 1 ) + + 1 4 ⋅ ( M − 1 2 M − 1 ) 2 [ 1 4 + 2 x 4 ∑ ν = 3 ∞ 1 ν + 2 x ν + 2 + 1 x 4 ∑ u , ν = 3 ∞ 1 u + ν x u + ν ] = 1 8 + 1 2 ⋅ M − 1 2 M − 1 ( 1 3 + 1 x 3 ∑ k = 4 ∞ 1 k x k ) + + 1 4 ⋅ ( M − 1 2 M − 1 ) 2 [ 1 4 + 2 x 4 ∑ k = 5 ∞ 1 k x k + 1 x 4 ∑ k = 6 ∞ k − 5 k x k ] = 1 8 + 1 2 ⋅ M − 1 2 M − 1 ( 1 3 + 1 x 3 ( ∑ k = 1 ∞ x k k − x 3 3 − x 2 2 − x ) ) + + 1 4 ⋅ ( M − 1 2 M − 1 ) 2 [ 1 4 + 2 x 4 ( ∑ k = 1 ∞ x k k − x 4 4 − x 3 3 − x 2 2 − x ) + + 1 x 4 ( ∑ k = 6 ∞ x k − 5 ( ∑ k = 1 ∞ x k k − x 5 5 − x 4 4 − x 3 3 − x 2 2 − x ) ) ] = 1 8 + 1 2 ⋅ M − 1 2 M − 1 ( 1 3 + 1 x 3 ( − ln ( 1 − x ) − x 3 3 − x 2 2 − x ) ) + + 1 4 ⋅ ( M − 1 2 M − 1 ) 2 [ 1 4 + 2 x 4 ( − ln ( 1 − x ) − x 4 4 − x 3 3 − x 2 2 − x ) + + 1 x 4 ( x 6 1 − x − 5 ( − ln ( 1 − x ) − x 5 5 − x 4 4 − x 3 3 − x 2 2 − x ) ) ] = 1 8 − 1 2 ⋅ M − 1 2 M − 1 ⋅ 1 x ( 1 2 + 1 x ) + + 1 4 ⋅ ( M − 1 2 M − 1 ) 2 ( 1 + x + 1 x + 3 2 ⋅ 1 x 2 + 3 x 3 + x 2 1 − x ) + − ln ( 1 − x ) ⋅ 1 2 ⋅ M − 1 2 M − 1 ⋅ 1 x 4 ( x − 3 2 ⋅ M − 1 2 M − 1 ) = 1 8 − 1 2 ⋅ M − 1 2 M − 1 ⋅ 1 x ( 1 2 + 1 x ) + + 1 4 ( M − 1 2 M − 1 ) 2 ( 1 + x + 1 x + 3 2 ⋅ 1 x 2 + 3 x 3 + x 2 1 − x ) + + ( ln ( 2 ) − ln ( 1 + M − 2 M − 1 ) ) ⋅ 1 2 ⋅ M − 1 2 M − 1 ⋅ 1 x 4 ( x − 3 2 ⋅ M − 1 2 M − 1 ) = 1 8 − 1 2 ⋅ M − 1 2 M − 1 ⋅ 1 x ( 1 2 + 1 x ) + + 1 4 ( M − 1 2 M − 1 ) 2 ( 1 + x + 1 x + 3 2 1 x 2 + 3 x 3 + x 2 1 − x ) + ( − ln ( 2 ) + ln ( 1 + 1 M − 1 ) ) ⋅ 1 4 M 2 − M + 1 x 4 ( 2 M − 1 ) 2 . \begin{aligned}
&\frac{1}{8}+\frac{1}{2}\cdot\frac{M-1}{2M-1}\left(\frac{1}{3}+\frac{1}{x^3}\sum_{\nu=3}^{\infty}\frac{1}{\nu+1}x^{\nu+1}\right)+\\
&\quad+\frac{1}{4}\cdot\left(\frac{M-1}{2M-1}\right)^2\left[\frac{1}{4}+\frac{2}{x^4}\sum_{\nu=3}^{\infty}\frac{1}{\nu+2}x^{\nu+2}+\frac{1}{x^4}\sum_{u,\nu=3}^{\infty}\frac{1}{u+\nu}x^{u+\nu}\right]\\
&=\frac{1}{8}+\frac{1}{2}\cdot\frac{M-1}{2M-1}\left(\frac{1}{3}+\frac{1}{x^3}\sum_{k=4}^{\infty}\frac{1}{k}x^k\right)+\\
&\quad+\frac{1}{4}\cdot\left(\frac{M-1}{2M-1}\right)^2\left[\frac{1}{4}+\frac{2}{x^4}\sum_{k=5}^{\infty}\frac{1}{k}x^k+\frac{1}{x^4}\sum_{k=6}^{\infty}\frac{k-5}{k}x^k\right]\\
&=\frac{1}{8}+\frac{1}{2}\cdot\frac{M-1}{2M-1}\left(\frac{1}{3}+\frac{1}{x^3}\left(\sum_{k=1}^{\infty}\frac{x^k}{k}-\frac{x^3}{3}-\frac{x^2}{2}-x\right)\right)+\\
&\quad+\frac{1}{4}\cdot\left(\frac{M-1}{2M-1}\right)^2\left[\frac{1}{4}+\frac{2}{x^4}\left(\sum_{k=1}^{\infty}\frac{x^k}{k}-\frac{x^4}{4}-\frac{x^3}{3}-\frac{x^2}{2}-x\right)+\right.\\
&\qquad\left.+\frac{1}{x^4}\left(\sum_{k=6}^{\infty}x^k-5\left(\sum_{k=1}^{\infty}\frac{x^k}{k}-\frac{x^5}{5}-\frac{x^4}{4}-\frac{x^3}{3}-\frac{x^2}{2}-x\right)\right)\right]\\
&=\frac{1}{8}+\frac{1}{2}\cdot\frac{M-1}{2M-1}\left(\frac{1}{3}+\frac{1}{x^3}\left(-\ln(1-x)-\frac{x^3}{3}-\frac{x^2}{2}-x\right)\right)+\\
&\quad+\frac{1}{4}\cdot\left(\frac{M-1}{2M-1}\right)^2\left[\frac{1}{4}+\frac{2}{x^4}\left(-\ln(1-x)-\frac{x^4}{4}-\frac{x^3}{3}-\frac{x^2}{2}-x\right)+\right.\\
&\qquad\left.+\frac{1}{x^4}\left(\frac{x^6}{1-x}-5\left(-\ln(1-x)-\frac{x^5}{5}-\frac{x^4}{4}-\frac{x^3}{3}-\frac{x^2}{2}-x\right)\right)\right]\\
&=\frac{1}{8}-\frac{1}{2}\cdot\frac{M-1}{2M-1}\cdot\frac{1}{x}\left(\frac{1}{2}+\frac{1}{x}\right)+\\
&\quad+\frac{1}{4}\cdot\left(\frac{M-1}{2M-1}\right)^2\left(1+x+\frac{1}{x}+\frac{3}{2}\cdot\frac{1}{x^2}+\frac{3}{x^3}+\frac{x^2}{1-x}\right)+\\
&\quad-\ln(1-x)\cdot\frac{1}{2}\cdot\frac{M-1}{2M-1}\cdot\frac{1}{x^4}\left(x-\frac{3}{2}\cdot\frac{M-1}{2M-1}\right)\\
&=\frac{1}{8}-\frac{1}{2}\cdot\frac{M-1}{2M-1}\cdot\frac{1}{x}\left(\frac{1}{2}+\frac{1}{x}\right)+\\
&\quad+\frac{1}{4}\left(\frac{M-1}{2M-1}\right)^2\left(1+x+\frac{1}{x}+\frac{3}{2}\cdot\frac{1}{x^2}+\frac{3}{x^3}+\frac{x^2}{1-x}\right)+\\
&\quad+\left(\ln(2)-\ln\left(1+\frac{M-2}{M-1}\right)\right)\cdot\frac{1}{2}\cdot\frac{M-1}{2M-1}\cdot\frac{1}{x^4}\left(x-\frac{3}{2}\cdot\frac{M-1}{2M-1}\right)\\
&=\frac{1}{8}-\frac{1}{2}\cdot\frac{M-1}{2M-1}\cdot\frac{1}{x}\left(\frac{1}{2}+\frac{1}{x}\right)+ \\
&+\frac{1}{4}\left(\frac{M-1}{2M-1}\right)^2\left(1+x+\frac{1}{x}+\frac{3}{2}\frac{1}{x^2}+\frac{3}{x^3}+\frac{x^2}{1-x}\right)+
\left(-\ln(2)+\ln\left(1+\frac{1}{M-1}\right)\right)\cdot\frac{1}{4}\frac{M^2-M+1}{x^4(2M-1)^2}.
\end{aligned} 8 1 + 2 1 ⋅ 2 M − 1 M − 1 ( 3 1 + x 3 1 ν = 3 ∑ ∞ ν + 1 1 x ν + 1 ) + + 4 1 ⋅ ( 2 M − 1 M − 1 ) 2 [ 4 1 + x 4 2 ν = 3 ∑ ∞ ν + 2 1 x ν + 2 + x 4 1 u , ν = 3 ∑ ∞ u + ν 1 x u + ν ] = 8 1 + 2 1 ⋅ 2 M − 1 M − 1 ( 3 1 + x 3 1 k = 4 ∑ ∞ k 1 x k ) + + 4 1 ⋅ ( 2 M − 1 M − 1 ) 2 [ 4 1 + x 4 2 k = 5 ∑ ∞ k 1 x k + x 4 1 k = 6 ∑ ∞ k k − 5 x k ] = 8 1 + 2 1 ⋅ 2 M − 1 M − 1 ( 3 1 + x 3 1 ( k = 1 ∑ ∞ k x k − 3 x 3 − 2 x 2 − x ) ) + + 4 1 ⋅ ( 2 M − 1 M − 1 ) 2 [ 4 1 + x 4 2 ( k = 1 ∑ ∞ k x k − 4 x 4 − 3 x 3 − 2 x 2 − x ) + + x 4 1 ( k = 6 ∑ ∞ x k − 5 ( k = 1 ∑ ∞ k x k − 5 x 5 − 4 x 4 − 3 x 3 − 2 x 2 − x ) ) ] = 8 1 + 2 1 ⋅ 2 M − 1 M − 1 ( 3 1 + x 3 1 ( − ln ( 1 − x ) − 3 x 3 − 2 x 2 − x ) ) + + 4 1 ⋅ ( 2 M − 1 M − 1 ) 2 [ 4 1 + x 4 2 ( − ln ( 1 − x ) − 4 x 4 − 3 x 3 − 2 x 2 − x ) + + x 4 1 ( 1 − x x 6 − 5 ( − ln ( 1 − x ) − 5 x 5 − 4 x 4 − 3 x 3 − 2 x 2 − x ) ) ] = 8 1 − 2 1 ⋅ 2 M − 1 M − 1 ⋅ x 1 ( 2 1 + x 1 ) + + 4 1 ⋅ ( 2 M − 1 M − 1 ) 2 ( 1 + x + x 1 + 2 3 ⋅ x 2 1 + x 3 3 + 1 − x x 2 ) + − ln ( 1 − x ) ⋅ 2 1 ⋅ 2 M − 1 M − 1 ⋅ x 4 1 ( x − 2 3 ⋅ 2 M − 1 M − 1 ) = 8 1 − 2 1 ⋅ 2 M − 1 M − 1 ⋅ x 1 ( 2 1 + x 1 ) + + 4 1 ( 2 M − 1 M − 1 ) 2 ( 1 + x + x 1 + 2 3 ⋅ x 2 1 + x 3 3 + 1 − x x 2 ) + + ( ln ( 2 ) − ln ( 1 + M − 1 M − 2 ) ) ⋅ 2 1 ⋅ 2 M − 1 M − 1 ⋅ x 4 1 ( x − 2 3 ⋅ 2 M − 1 M − 1 ) = 8 1 − 2 1 ⋅ 2 M − 1 M − 1 ⋅ x 1 ( 2 1 + x 1 ) + + 4 1 ( 2 M − 1 M − 1 ) 2 ( 1 + x + x 1 + 2 3 x 2 1 + x 3 3 + 1 − x x 2 ) + ( − ln ( 2 ) + ln ( 1 + M − 1 1 ) ) ⋅ 4 1 x 4 ( 2 M − 1 ) 2 M 2 − M + 1 .
Using the Taylor expansion of the logarithm expansion up to the third term, it follows that this expression is bounded above by
1 8 − 1 2 ⋅ M − 1 2 M − 1 ⋅ 1 x ( 1 2 + 1 x ) + 1 4 ( M − 1 2 M − 1 ) 2 ( 1 + x + 1 x + 3 2 1 x 2 + 3 x 3 + x 2 1 − x ) + ( − ln ( 2 ) + 1 M − 1 − 1 2 ( M − 1 ) 2 + 1 3 ( M − 1 ) 3 ) ⋅ 1 4 M 2 − M + 1 x 4 ( 2 M − 1 ) 2 . \frac{1}{8}-\frac{1}{2}\cdot\frac{M-1}{2M-1}\cdot\frac{1}{x}\left(\frac{1}{2}+\frac{1}{x}\right)+
\frac{1}{4}\left(\frac{M-1}{2M-1}\right)^2\left(1+x+\frac{1}{x}+\frac{3}{2}\frac{1}{x^2}+\frac{3}{x^3}+\frac{x^2}{1-x}\right)+
\left(-\ln(2)+\frac{1}{M-1}-\frac{1}{2(M-1)^2}+\frac{1}{3(M-1)^3}\right)\cdot\frac{1}{4}\frac{M^2-M+1}{x^4(2M-1)^2}. 8 1 − 2 1 ⋅ 2 M − 1 M − 1 ⋅ x 1 ( 2 1 + x 1 ) + 4 1 ( 2 M − 1 M − 1 ) 2 ( 1 + x + x 1 + 2 3 x 2 1 + x 3 3 + 1 − x x 2 ) + ( − ln ( 2 ) + M − 1 1 − 2 ( M − 1 ) 2 1 + 3 ( M − 1 ) 3 1 ) ⋅ 4 1 x 4 ( 2 M − 1 ) 2 M 2 − M + 1 .
Hence, Z 3 ( M + 1 , M + 1 ) Z_3(M+1,M+1) Z 3 ( M + 1 , M + 1 ) has been bounded from above by a rational function. To obtain an upper bound on 2 Z 1 ( M + 1 , M + 1 ) 2Z_1(M+1,M+1) 2 Z 1 ( M + 1 , M + 1 ) , note that
( M + 1 2 M + 1 ) − 2 Z 1 ( M + 1 , M + 1 ) = ∑ s = M + 1 2 M 1 s = ∑ s = M + 1 2 M 1 s − ln ( 2 ) + ln ( 2 ) = ∑ s = M + 1 2 M 1 s − ∫ M 2 M 1 t d t + ln ( 2 ) = ln ( 2 ) − ∑ k = M 2 M − 1 ( ∫ k k + 1 1 t d t − 1 k + 1 ) = ln ( 2 ) − ∑ k = M 2 M − 1 ( ln ( k + 1 k ) − 1 k + 1 ) = ln ( 2 ) − ∑ k = M 2 M − 1 ( ln ( 1 + 1 k ) − 1 k + 1 ) = ln ( 2 ) − ∑ k = M 2 M − 1 ( ( 1 k − 1 2 k 2 + 1 3 k 3 − ⋯ ) − 1 k + 1 ) ≤ ln ( 2 ) − ∑ k = M 2 M − 1 ( ( 1 k − 1 2 k 2 ) − 1 k + 1 ) = ln ( 2 ) − ( 1 M − 1 2 M ) + 1 2 ∑ k = M 2 M − 1 1 k 2 ≤ ln ( 2 ) − 1 2 M + 1 2 ∫ M − 1 2 M − 1 1 t 2 d t = ln ( 2 ) − 1 2 M + 1 2 ( 1 M − 1 − 1 2 M − 1 ) . \begin{aligned}
\left(\frac{M+1}{2M+1}\right)^{-2}Z_1(M+1,M+1)=\sum_{s=M+1}^{2M}\frac{1}{s}=\sum_{s=M+1}^{2M}\frac{1}{s}-\ln(2)+\ln(2) \\
&=\sum_{s=M+1}^{2M}\frac{1}{s}-\int_M^{2M}\frac{1}{t}\,dt+\ln(2)
=\ln(2)-\sum_{k=M}^{2M-1}\left(\int_k^{k+1}\frac{1}{t}\,dt-\frac{1}{k+1}\right) \\
&=\ln(2)-\sum_{k=M}^{2M-1}\left(\ln\left(\frac{k+1}{k}\right)-\frac{1}{k+1}\right)
=\ln(2)-\sum_{k=M}^{2M-1}\left(\ln\left(1+\frac{1}{k}\right)-\frac{1}{k+1}\right) \\
&=\ln(2)-\sum_{k=M}^{2M-1}\left(\left(\frac{1}{k}-\frac{1}{2k^2}+\frac{1}{3k^3}-\cdots\right)-\frac{1}{k+1}\right) \\
&\leq\ln(2)-\sum_{k=M}^{2M-1}\left(\left(\frac{1}{k}-\frac{1}{2k^2}\right)-\frac{1}{k+1}\right)
=\ln(2)-\left(\frac{1}{M}-\frac{1}{2M}\right)+\frac{1}{2}\sum_{k=M}^{2M-1}\frac{1}{k^2} \\
&\leq\ln(2)-\frac{1}{2M}+\frac{1}{2}\int_{M-1}^{2M-1}\frac{1}{t^2}\,dt
=\ln(2)-\frac{1}{2M}+\frac{1}{2}\left(\frac{1}{M-1}-\frac{1}{2M-1}\right).
\end{aligned} ( 2 M + 1 M + 1 ) − 2 Z 1 ( M + 1 , M + 1 ) = s = M + 1 ∑ 2 M s 1 = s = M + 1 ∑ 2 M s 1 − ln ( 2 ) + ln ( 2 ) = s = M + 1 ∑ 2 M s 1 − ∫ M 2 M t 1 d t + ln ( 2 ) = ln ( 2 ) − k = M ∑ 2 M − 1 ( ∫ k k + 1 t 1 d t − k + 1 1 ) = ln ( 2 ) − k = M ∑ 2 M − 1 ( ln ( k k + 1 ) − k + 1 1 ) = ln ( 2 ) − k = M ∑ 2 M − 1 ( ln ( 1 + k 1 ) − k + 1 1 ) = ln ( 2 ) − k = M ∑ 2 M − 1 ( ( k 1 − 2 k 2 1 + 3 k 3 1 − ⋯ ) − k + 1 1 ) ≤ ln ( 2 ) − k = M ∑ 2 M − 1 ( ( k 1 − 2 k 2 1 ) − k + 1 1 ) = ln ( 2 ) − ( M 1 − 2 M 1 ) + 2 1 k = M ∑ 2 M − 1 k 2 1 ≤ ln ( 2 ) − 2 M 1 + 2 1 ∫ M − 1 2 M − 1 t 2 1 d t = ln ( 2 ) − 2 M 1 + 2 1 ( M − 1 1 − 2 M − 1 1 ) .
Thus inequality (39) is satisfied when the following inequality holds
1 8 − 1 2 ⋅ M − 1 2 M − 1 ⋅ 1 x ( 1 2 + 1 x ) + 1 4 ( M − 1 2 M − 1 ) 2 ( 1 + x + 1 x + 3 2 1 x 2 + 3 x 3 + x 2 1 − x ) + ( − ln ( 2 ) + 1 M − 1 − 1 2 ( M − 1 ) 2 + 1 3 ( M − 1 ) 3 ) ⋅ 1 4 M 2 − M + 1 x 4 ( 2 M − 1 ) 2 + ln ( 2 ) − 1 2 M + 1 2 ( 1 M − 1 − 1 2 M − 1 ) ≤ 2 M + 1 2 M + 2 . \frac{1}{8}-\frac{1}{2}\cdot\frac{M-1}{2M-1}\cdot\frac{1}{x}\left(\frac{1}{2}+\frac{1}{x}\right)+
\frac{1}{4}\left(\frac{M-1}{2M-1}\right)^2\left(1+x+\frac{1}{x}+\frac{3}{2}\frac{1}{x^2}+\frac{3}{x^3}+\frac{x^2}{1-x}\right)+
\left(-\ln(2)+\frac{1}{M-1}-\frac{1}{2(M-1)^2}+\frac{1}{3(M-1)^3}\right)\cdot\frac{1}{4}\frac{M^2-M+1}{x^4(2M-1)^2}
+\ln(2)-\frac{1}{2M}+\frac{1}{2}\left(\frac{1}{M-1}-\frac{1}{2M-1}\right)\leq\frac{2M+1}{2M+2}. 8 1 − 2 1 ⋅ 2 M − 1 M − 1 ⋅ x 1 ( 2 1 + x 1 ) + 4 1 ( 2 M − 1 M − 1 ) 2 ( 1 + x + x 1 + 2 3 x 2 1 + x 3 3 + 1 − x x 2 ) + ( − ln ( 2 ) + M − 1 1 − 2 ( M − 1 ) 2 1 + 3 ( M − 1 ) 3 1 ) ⋅ 4 1 x 4 ( 2 M − 1 ) 2 M 2 − M + 1 + ln ( 2 ) − 2 M 1 + 2 1 ( M − 1 1 − 2 M − 1 1 ) ≤ 2 M + 2 2 M + 1 .
Rearranging this inequality leads to
( 384 ln ( 2 ) − 264 ) M 8 + ( − 2040 ln ( 2 ) + 1401 ) M 7 + ( 3840 ln ( 2 ) − 2744 ) M 6 + + ( − 2088 ln ( 2 ) + 2347 ) M 5 + ( − 2400 ln ( 2 ) − 1544 ) M 4 + ( 3840 ln ( 2 ) + 2956 ) M 3 + ( − 1824 ln ( 2 ) − 3824 ) M 2 + ( 288 ln ( 2 ) + 2032 ) M − 384 ≥ 0. \begin{aligned}
(384\ln(2)-264)M^8+(-2040\ln(2)+1401)M^7+(3840\ln(2)-2744)M^6+ \\
&+(-2088\ln(2) + 2347)M^{5} + (-2400\ln(2) - 1544)M^{4} +
(3840\ln(2) + 2956)M^{3} + (-1824\ln(2) - 3824)M^{2} + (288\ln(2) + 2032)M - 384 \ge0.
\end{aligned} ( 384 ln ( 2 ) − 264 ) M 8 + ( − 2040 ln ( 2 ) + 1401 ) M 7 + ( 3840 ln ( 2 ) − 2744 ) M 6 + + ( − 2088 ln ( 2 ) + 2347 ) M 5 + ( − 2400 ln ( 2 ) − 1544 ) M 4 + ( 3840 ln ( 2 ) + 2956 ) M 3 + ( − 1824 ln ( 2 ) − 3824 ) M 2 + ( 288 ln ( 2 ) + 2032 ) M − 384 ≥ 0.
It is a matter of simple checking that
( 384 ln ( 2 ) − 264 ) M 8 + ( − 2040 ln ( 2 ) + 1401 ) M 7 + ( 3840 ln ( 2 ) − 2744 ) M 6 ≥ 0 (384\ln(2) - 264)M^{8} + (-2040\ln(2) + 1401)M^{7} + (3840\ln(2) - 2744)M^{6} \ge0 ( 384 ln ( 2 ) − 264 ) M 8 + ( − 2040 ln ( 2 ) + 1401 ) M 7 + ( 3840 ln ( 2 ) − 2744 ) M 6 ≥ 0
for all M ≥ 10 M \ge10 M ≥ 10 , and that
( − 2088 ln ( 2 ) + 2347 ) M 5 + ( − 2400 ln ( 2 ) − 1544 ) M 4 ≥ 0 (-2088\ln(2) + 2347)M^{5} + (-2400\ln(2) - 1544)M^{4} \ge0 ( − 2088 ln ( 2 ) + 2347 ) M 5 + ( − 2400 ln ( 2 ) − 1544 ) M 4 ≥ 0
and
( 3840 ln ( 2 ) + 2956 ) M 3 + ( − 1824 ln ( 2 ) − 3824 ) M 2 ≥ 0 (3840\ln(2) + 2956)M^{3} + (-1824\ln(2) - 3824)M^{2} \ge0 ( 3840 ln ( 2 ) + 2956 ) M 3 + ( − 1824 ln ( 2 ) − 3824 ) M 2 ≥ 0
and
( 288 ln ( 2 ) + 2032 ) M − 384 ≥ 0 (288\ln(2) + 2032)M - 384 \ge0 ( 288 ln ( 2 ) + 2032 ) M − 384 ≥ 0
for all nonnegative M M M .
Inequality (39) can be checked ”by hand” for M ≤ 10 M \le10 M ≤ 10 .
Appendix
Table 3. Description of the notation for the most often used variables, functions and sets.