Uma sequência de n candidatos a um trabalho são preparados para serem entrevistados. Nós gostaríamos de contratar o melhor candidato, mas não temos informações para distinguir os candidatos antes de entrevistálos. Nós assumimos que o melhor candidato é igualmente provável de ser qualquer um dos n candidatos na sequência antes da entrevista começar. Depois que as entrevistas começam, nós podemos ranquear os candidatos já entrevistados, mas não temos nenhuma informação sobre onde os candidatos restantes se localizam no ranque geral. Depois de cada entrevista, nós temos que ou contratar o candidato atual imediatamente, ou deixar o candidato ir embora e nunca mais contactá-lo. A seguinte regra é utilizada: um número r é selecionado e nós entrevistamos os primeiros r candidatos sem intenção de contratá-los. Iniciando com próximo candidato r+1, nós continuamos entrevistando até que o candidato atual é o melhor que vimos até o momento; a entrevista para e contrata o candidato atual. Se nenhum dos candidatos de r+1 até n é o melhor, o candidato n é contratado. Nós gostaríamos de selecionar r de tal forma que maximize a probabilidade de contratar o melhor candidato. Seja A o evento de que o melhor candidato é contratado, e seja Bi o evento de que o melhor candidato está na posição i na sequência de entrevistas.
(a) Seja i>r. Encontre a probabilidade de que o candidato que é relativamente o melhor entre os i primeiro entrevistados apareça nas primeiras r entrevistas.
(b) Prove que Pr(A mid Bi)=0 para i <= r e Pr(A mid Bi)=ri-1 para i>r.
© Para r fixo, seja pr a probabilidade de A usando aquele valor de r. Prove que pr=(r / n) sumi=r+1^n(i-1)^-1.
(d) Seja qr=pr-pr-1 para r=1, ldots, n-1, prove que qr é uma função estritamente decrescente em r.
(e) Mostre que o valor de r que maximiza pr é o último r tal que qr>0.
(f) Para n=10, encontre o valor de r que maximiza pr, e encontre o valor de pr correspondente.

Passo 1

Resumo do enunciado e conteúdo
– Enunciado em poucas palavras: há uma lista aleatória de candidatos, todos igualmente prováveis de serem o “melhor”. A regra é: rejeitar os primeiros candidatos sem contratar ninguém; a partir de então contratar o primeiro que supere todos os vistos até ali (ou, se não aparecer ninguém melhor, ficar com o último). Queremos achar que maximize a chance de pegar o melhor.
– Matéria usada: probabilidade condicional, lei da probabilidade total, simetria em permutações e séries harmônicas.
– O que precisaremos:
  1. Entender , onde = “o melhor está na posição ”.
  2. Usar .
  3. Saber que (números harmônicos).

Passo 2

(a) Para Pr(relativo-melhor em 1,dots,r) =ri, : qual a probabilidade de que, entre os primeiros entrevistados, o “melhor até ali” tenha vindo de um índice ?
– Como cada ordem de candidatos é equiprovável, o mais alto entre eles está uniformemente em qualquer posição de a .
– Logo

Passo 3

(b) Queremos Pr(Amid Bi)=r,i-1,, .
  1. Se , o melhor está num dos rejeitados, então .
  2. Se , para contratar o melhor na posição , é preciso que nenhum dos candidatos em seja melhor que todos os vistos até então. Isso equivale a dizer que, entre os primeiros, o “máximo relativo” caiu em . Pelo item (a), com trocado por , vem

Passo 4

© Pela probabilidade total, sabendo que pr=Pr(A) =sumi=1^nPr(Bi),Pr(Amid Bi) =sumi=r+1^n1ncdotri-1 =rnsumi=r+1^n1i-1 =rnsumk=r^n-11k, para todo ,

Passo 5

(d) Defina pr=rnsumk=r^n-11k, pr-1=r-1nsumk=r-1^n-11k para qr =1nl(sumk=r^n-11k-1r) Longrightarrow qr-qr+1 =1nl(1rr)>0 . Então
Fazendo a conta (ou brincando com as somas), obtém-se
Logo é estritamente decrescente.

Passo 6

(e) Como , enquanto o cresce; ao primeiro , . Portanto o máximo de ocorre exatamente no último com .

Passo 7

(f) Para pr= r10sumk=r^91k calculemos
rapidamente (em décimos):
:
:
:
: já cai de novo.

Resposta

O p3=310l(tfrac13+tfrac14+cdots+tfrac19r)approx0.3987 que maximiza em é , e nesse caso

Exercícios relacionados