Report

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?