Uma sequência de
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
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
é selecionado e nós entrevistamos os primeiros
candidatos sem intenção de contratá-los. Iniciando com próximo candidato
, 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
até
é o melhor, o candidato
é contratado. Nós gostaríamos de selecionar
de tal forma que maximize a probabilidade de contratar o melhor candidato. Seja
o evento de que o melhor candidato é contratado, e seja
o evento de que o melhor candidato está na posição
na sequência de entrevistas.
(a) Seja
. Encontre a probabilidade de que o candidato que é relativamente o melhor entre os
primeiro entrevistados apareça nas primeiras
entrevistas.
(b) Prove que
para
e
para
.
© Para
fixo, seja
a probabilidade de
usando aquele valor de
. Prove que
.
(d) Seja
para
, prove que
é uma função estritamente decrescente em
.
(e) Mostre que o valor de
que maximiza
é o último
tal que
.
(f) Para
, encontre o valor de
que maximiza
, e encontre o valor de
correspondente.
(a) Seja
(b) Prove que
© Para
(d) Seja
(e) Mostre que o valor de
(f) Para
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:
– Enunciado em poucas palavras: há uma lista aleatória de
– Matéria usada: probabilidade condicional, lei da probabilidade total, simetria em permutações e séries harmônicas.
– O que precisaremos:
- Entender
, onde = “o melhor está na posição ”. - Usar
. - Saber que
(números harmônicos).
Passo 2
(a) Para
: 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
– Como cada ordem de
– Logo
Passo 3
(b) Queremos
.
- Se
, o melhor está num dos rejeitados, então . - 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
para todo
,
Passo 5
(d) Defina
para
. 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
calculemos
rapidamente (em décimos):
– :
– :
– :
– : já cai de novo.
–
–
–
–
Resposta
O
que maximiza
em
é
, e nesse caso