Transcript Power Point presentation

The Odds Algorithm
E 8 1 0 0 / B 9 8 0 1 C L A S S P RO J E C T
D A N I E L G U E T TA
Outline
 The odds algorithm
 The classical secretary problem
 The secretary problem with group
interviews
 A continuous-time secretary problem
 The secretary problem with rejection
 The IID case – known distributions
The Odds Algorithm
11 , 12 , 13 , 14 , 15 , 16 , 17 , 18 , 19
0 , 0 ,1 , 0 ,1 ,1 , 0 ,1 , 0
A Simple Example
Throw a fair six-sided die n times – want to stop at
the last 6 obtained.
1k = 1
{k
th
t h r ow of t h e d ie w a s a 6
}
P (E x a ct ly on e 6 in r em a in in g s t h r ow s ) = P (B in [s , 16 ] = 1 )
s
s- 1
= C 1 ( 6 )( 6 )
1
5
s- 1
= s ( 6 )( 6 )
1
Maximized at s = 6
5
The Odds Theorem
Theorem: • Let 11 , L , 1n be a sequence of n independent
indicators
• Let p k = E ( 1k ) , rk = pk / (1 – pk) = pk/qk.
Then, there exist an optimal rule which
maximizes the probability of stopping at the
last success.
It prescribes to stop on the first success with
index > s, where s is…
Bruss (2000), Ann. Probab. Volume 28, Number 3 (2000), 1384-1391
The Odds Theorem
rk =
pk
1- p k
contd… …where s is…
T h e la r gest n u m b er for w h ich
For
example
pk
rk
å
n
j= s
rj ³ 1
11
12
13
14
1
0.5
0.3
0.3
∞
1
0.5
0.5 0.25 0.2 0.17
1.12 0.62 0.37 0.17
15
16
17
0.2 0.17 0.14
Optimal Strategy: from the 4th observation
onwards, stop at any success.
The Odds Theorem
Proof: Three steps
1. Find the a-priori probability
P (O n e su ccess in t h e la st k ob ser v a t ion s )
2. Find the s that maximizes this
probability.
3. Show that the optimal strategy ignores
everything up to s and then picks the
next success.
Bruss (2000), Ann. Probab. Volume 28, Number 3 (2000), 1384-1391
The Odds Theorem
Probability Generating Function (PGF)
Step
o f XS == G1X (+q )L= +E (1q . )We
= åneed
q P ((XS == k1)) .
1:P G FLet
k
k
k
k
n
X
k
P G F of 1k = g i ( q )
G X¢ ( 0) = P ( X = 1)
0
1
= q qj + q pj
G X + Y (q) = E (q
X +Y
X
Y
) = E ( q =) Eq( q (1) += qGr X)( q )G Y ( q )
j
j
P G F of S k = G k ( q )
=
=
Õ
Õ
n
j= k
n
j= k
g j (q)
q j (1 + r j q )
The Odds Theorem
Step 1:
Let
. We need P (S k
G k (q) =
Õ
n
j= k
= 1).
q j (1 + r j q )
The Odds Theorem
Step 1:
G k¢( q )
G kLet
(q) =
Õ
n
j= k
d
=
log éêG k ( q ) ù
=
ú
ë
û
G k (q)
dq
P (S k
= 1) = G k¢( 0 ) =
q j (1 + r j q ).
å
n
(å
n
P ( S k = 1) =
We need P (S k
d
j= k
j= k
log éêq j (1 + r j q ) ù
=
ú
ë
û
dq
)
(å
n
n
rj G k ( 0) =
(å
j= k
rj
)(Õ
j= k
n
j= k
qj
)
rj
= 1).
å
rj
n
j= k
)(Õ
1 + rj q
n
j= k
qj
)
The Odds Theorem
Proof: Three steps
 1. Find the a-priori probability
P (O n e su ccess in t h e la st k ob ser v a t ion s )
2. Find the s that maximizes this
probability.
3. Show that the optimal strategy ignores
everything up to s and then picks the
next success.
The Odds Theorem
Step 2:
Pk = P ( S k = 1) =
n
(å
j= k
rj
)(Õ
n
j= k
qj
)
P k in cr ea sin g in k Û P k < P k + 1
Û
(
rk +
<
Û qk
n
å
(å
(r +
j= k+ 1
å
n
j
j= k+ 1
Û q k rk < (1 - q k ) å
Û qk
Û
å
1- qk
qk
qk Õ
j= k+ 1
j= k+ 1
j
rj > 1
j
n
j
j= k+ 1
n
j= k+ 1
n
< (1 - q k ) å
n
j= k+ 1
n
n
k
n
q )
)(
r )(Õ
q )
r ) < (å
r )
j= k+ 1
rj
rj
j= k+ 1
rj
j
The Odds Theorem
Proof: Three steps
 1. Find the a-priori probability
P (O n e su ccess in t h e la st k ob ser v a t ion s )
 2. Find the s that maximizes this
probability.
3. Show that the optimal strategy ignores
everything up to s and then picks the
next success.
The Odds Theorem
Step 3: • Most general strategy stops at a random
time W such that {W = k } Î s (11 , L , 1k ) .
• However, note that
P (S W = 1 | 11 , L , 1k ,W = k ) = P (S k = 1 )
• We have shown, however, that this last
probability is unimodal; it is therefore
maximized at a fixed k.
The Classical Secretary
Problem
1k = 11 S ecr et a r y
{
1
k is t h e b est o n e so fa r }
1
1
p k = P (Sec. k b est so fa r ) =
1
k
Classical Result
Odds algorithm tells us to ignore all secretaries until
secretary s and then to choose the first “success” (ie:
the first secretary that is the best so far)
s = T h e la r g est n u m b er fo r w h ich
å
ò
s
n
n
1
k
j = s 1-
1
1
k
=
å
n
1
j= s k- 1
d k = log
k - 1
» 1
n - 1
s- 1
s » n / e
å
» 1
n
j= s
rj ³ 1
The Secretary Problem with
Group Interviews
n groups of size
l 1, l 2, L , l
n
Members of a group are interviewed together.
After the interview, either one group member
is chosen or the whole group is ignored
without a chance of recall
from Bruss (2000)
Group Interviews
Associate indicator to each group. Aim to stop at last 1
1k = 1 G r ou p
{
k con t a in s t h e it em t h a t is t h e b es t of a ll seen so fa r }
p k = E ( 1k ) =
å
pj
n
j= s
=
1 - pj
å
l
l
1
n
j= s
k
=
+ L + l
l
k
bk - l
k
k
bk
k
=
l
å
n
j= s
l
k
bk -
1
So pick the first “best” item after group s, where
ìï
s = su p ïí k :
ï
ïî
å
n
i= k
l
k
bk -
1
ü
ï
³ 1 ïý
ï
ïþ
Hsiau and Yang (2000)
The Odds Theorem & Secretary
Problem in Continuous Time
0
t=0
01
1
0
10
1
1
0
10
1
t=T
Random arrivals in [0, T] form an inhomogeneous
Poisson process with density (t)
P (A r r iva l a su ccess | A r r ives a t t im e t ) = h ( t )
from Bruss (2000)
Continuous Time Problem
Consider an interval
k
= (tk – 1,tk]
p k = P (Su ccess in D k ) = l ( t k )h ( t k ) D k + o ( D k )
rk =
pk
1 - pk
»
l ( t k )h ( t k )
1 - l ( t k )h ( t k ) D k
D k ~D
k
® 0
l ( t k )h ( t k ) D k
As such, the “odds of success” has a well-defined
density, (t) = (t)h(t)
ìï
s = su p í t Î [0, T ] :
ïîï
ò
t
T
ü
ï
l ( u )h ( u ) d u ³ 1 ý
ïþ
ï
The Secretary Problem in Continuous Time
h ( t ) = P (A r r iv a l k a su ccess | A r r iv es a t t im e t )
= P (A r r iv a l k la r gest so fa r | A r r iv es a t t im e t )
= E P éêA r r iv a l k la r gest so fa r | m it em s in [0, t ) ù
ú
ë
û
æ 1 ö
÷
÷
= E çç
ççè m + 1 ÷
÷
ø
- 1ö
æé
t
ù
æ
ö
÷
ç
÷
ç
ç
ê
ú
= E ç 1+ P o ç ò l ( u ) d u ÷ ÷
÷
÷
÷
ç
çç êë
è 0
øú
÷
û ÷
è
ø
(
)
The Secretary Problem with
Rejection
Suppose we desire to model the fact each
secretary might reject an offer of employment,
with probability 1 – p (independent of
everything else).
What’s the Objective?
Best of all
Best of all available
“No regrets”
Best of all
Difficult to model using the indicator approach
Might be tempted to use
1
1
1k = 1 B est
{
so fa r a n d a ccep t s em p lo y m en t }
But what if the best secretary of all refuses
employment?
Smith (1975) and Freeman (1983) find that the best
strategy is to explore until s = np1/(1 – p)
Best of all – Numerical Results
Performance of Strategies with Varying “Exploration
Thresholds” s, Based on 150,000 Simulations
Probability of Success
Predicted
best
s
“No Regrets”
1
1
We want to pick the last success from
1k = 1 B est
{
so fa r a n d a ccep t s em p lo y m en t }
“No Regrets”
We want to pick the last success from
1k = 1 B est
{
so fa r a n d a ccep t s em p lo y m en t }
p k = E ( 1k ) = P ( A ccep t s) ×P ( B est so fa r ) = p
å
n
j= s
ò
s
rj =
n
p
k- p
å
n
p
k
j = s 1-
p
å
=
n
p
k= s k- p
k
d k = p log
n - p
s- p
s » ne
- 1/ p
» 1
» 1
1
k
“No Regrets” – Numerical Results
Performance of Strategies with Varying “Exploration
Thresholds” s, Based on 150,000 Simulations
Simulation
Probability of Success
Prediction from
the odds algorithm
s
Best of all available
1
1
1
1
1
We want to pick the last indicator from
1k = 1 B est
{
o f t h o s e a c c e p t e d so fa r a n d a ccep t s em p lo y m en t }
Partial information case harder! See Tamaki (1991)
Best of All Available – Full Information
We want to pick the last indicator from
1k = 1 B est
{
({
p k = E 1 B est
o f t h o se a ccep t ed so fa r a n d a ccep t s e m p lo y m en t }
é
= p E E ê1 B est of t h ose a ccep t ed
ë{
æ 1 ö
÷
÷
= p E çç
÷
ççè m + 1 ø
÷
æ
ö
1
÷
ç
÷
= pE ç
÷
ççè B in [k - 1, p ] + 1 ø
÷
(
)
Max of Bin(k – 1, p) + 1 values
of t h ose a ccep t ed so fa r a n d a ccep t s e m p loy m en t }
so fa r }
|
Bin(k – 1, p)
maccepted
a ccep t ed
ù
so fa r ú
û
)
k
k – 1 items
Best of All Available – Numerical Results
Performance of Strategies with Varying “Exploration
Thresholds” s, Based on 150,000 Simulations
Probability of Success
Simulation
Prediction from
the odds algorithm
s
… However …
In this particular problem, we discover new, separate
data as we observe the indicators
We originally assume the number of availabilities is
binomially distributed. But as we observe the
indicators, we start observing actual availabilities.
The previous strategy is indeed the best if we restrict
ourselves to a fixed threshold chosen at the start.
But there must be a way to exploit this new data.
The Odds Theorem on Steroids
Tamaki (1991) solves this problem for the particular
case of the secretary problem with rejection
More interesting is Ferguson (2008), who generalizes
the odds Theorem to a situation in which external
data becomes available during the selection process.
For the sake of this project, we will take a more
pedestrian approach. We will recalculate the optimal
threshold at each step using newfound information.
Best of All Available – Full Information
But consider – if we’ve now observed secretary v,
and so far, x secretaries have accepted (including v, if
applicable)…
({
p k = E 1 B est
)
Max of x + Bin(k – v – 1, p) + 1 values
of t h ose a ccep t ed so fa r a n d a ccep t s e m p loy m en t }
Bin(k – v – 1, p)
é
ù
accepted
= p E E ê1 B est of t h ose a ccep t ed sox accepted
|
m
a
ccep
t
ed
so
fa
r
ú
fa r }
{
ë
û
æ 1 ö
÷
v
1
÷
= p E çç
÷
k – v – 1 items
ççè m + 1 ø
÷
æ
ö
1
÷
ç
÷
= pE ç
÷
ççè x + B in [k - v - 1, p ] + 1 ø
÷
(
)
k
Best of All Available – Numerical Results
Improvements Obtained using a Dynamic Algorithm
over a Static one – based on 150,000 simulations
Additional Probability
of Success using
Dynamic Algorithm
Number of secretaries
The Secretary Problem with
IID Utilities from a known Distn
V k = V a lu e of k
1k = 1 S ecr et a r y
{
th
IID
sec. ~ U [0, 1]
k is t h e b est o n e so fa r }
Maximum of n IID Uniform RVs
Consider n independent U[0,1] RVs
f (x ) = 1
F (x ) = x
F (x ) = 1 - x
Let M be the max of those n RVs. Then
n
P (M Î [u , u + d u ]) = C 1 P (n - 1 R V s £ u ) P (O n e R V Î [u , u + d u ])
= nu
=
n- 1
du
G( n + 1)
×u
n- 1
du
G( n ) G(1)
As such M
~ B et a (n , 1 )
.
IID Case – Known Distribution
1k = 1 S ecr etMaximum
a r y k is tish emb est
{
o n e so fa r }
= 1V
{
k
= m a x [V 1 , L ,V k ]}
k
v
Imagine we1 have observed all
secretaries up to v, and
k – v items
we have found the maximum so far to be m.
p k = P (V k b est so fa r | m a x [V 1 , L , V v ] = m
)
= P (m a x [V v + 1 , L , V k ] ³ m a n d m a x [V v + 1 , L , V k ] = V k )
= P (m a x [V v + 1 , L , V k ] = V k ) P (m a x [V v + 1 , L , V k ] ³ m
=
1
k - v
P (B et a[k - v , 1] ³ m
)
)
IID Case – Numerical Results
Based on 150,000 trials with 500 secretaries, the best
secretary is chosen with probability 0.5409.
This approaches the “best” probability of success, of
0.5802 (Gilbert and Mosteller, 1966. Tamaki, 2009).
Stopping Time
Stopping Time
Other Literature
• Bruss (2003) – bounds on the performance of the Odds
Algorithm.
• Tamaki (2009) – the secretary problem with rejection and
IID secretary values.
• Tamaki (2010) –extension of the Odds Theorem to picking
the last k successes, with application to the k-secretary
problem with IID secretary values.
• Ferguson (2008) – odds theorem with extra info
• etc…
Questions, Comments, Suggestions,
Personal Stories or Jokes?