O problema clássico conhecido como Problema da Secretária (e algumas vezes chamado de problema do casamento) é um problema apresentado da seguinte forma:
1) Existe uma posição de secretária disponível
2) O número de secretárias interessadas é conhecido e igual a \(n\)
3) As interessadas são intrevistadas sequencialmente e aleatoriamente (não necessariamente as melhores secretárias estão no início o no fim da fila)
4) Supõe-se que depois que cada uma das interessadas é analisada, você consegue dizer claramente qual delas é a melhor
5) Depois de entrevistar cada uma delas, você deve contrata-la ou rejeita-la. Depois de rejeita-la, você NÃO pode mais chama-la novamente.
6) Você fica satisfeito apenas com a melhor secretária. Ou seja, você ganha 1 ponto se encontrar a melhor secretária e 0 se ganhar qualquer outra que não seja a melhor.
Com o objetivo de simplificar a apresentação do problema, vamos associar cada secretária a um número inteiro. Aquela que possui o menor número inteiro é a melhor no rank.
Exemplo:
Considere que existam apenas 3 secretárias com nome Alice, Beatriz e Cecília, onde Alice é a melhor, seguida de Beatriz e depois Cecília.
Qual a chance de Alice (que você está interassado) ser a primeira a ser entrevistada?
Como elas são entrevistadas aleatoriamente a chance é 1/3.
Se você escolher a primeira interessada, com 1/3 de chance você vai escolher a secretária correta. Será que você pode fazer melhor?
Considere a seguinte heurística:
Escolha a segunda interessada se ela for melhor que a primeira e, em caso contrário, escolha a terceira.
Qual a probabilidade de você escolher a secretária desejada usando essa heurística. Fácil! Vamos olhar as sequências de eventos possíveis:
Caso 1: Alice, Beatriz, Cecília [Nâo escolho a melhor secretária]
Caso 2: Alice, Cecília, Beatriz [Nâo escolho a melhor secretária]
Caso 3: Beatriz, Alice, Cecília [Escolho a melhor secretária (na segunda rodada), pois Alice é melhor que Beatriz]
Caso 4: Beatriz, Cecília, Alice [Escolho a melhor secretária (na terceira rodada), pois Cecília é pior que Beatriz]
Caso 5: Cecília, Alice, Beatriz [Escolho a melhor secretária (na segunda rodada), pois Alice é melhor que Cecília]
Caso 6: Cecília, Beatriz, Alice [Não escolho a melhor secretária]
Logo, usando essa heurística, escolhemos corretamente com probabilidade 1/2 que é muito melhor que escolher aleatoriamente a primeira, a segunda, ou a terceira.
Será que essa solução pode ser generalizada?
Sim!! Essa idéia é bem simples.
Suponha que \(P_i\) seja a probabilidade de vencer (escolher a secretária correta) usando uma estratégia ótima que considera apenas as secretárias que foram entrevistadas em \(\{i+1,\cdots,n\}\) e \(P_{i+1}\) seja a probabilidade de vencer (escolher a secretária correta) usando uma estratégia ótima que considera apenas as secretárias que foram entrevistadas em \(\{i+2,\cdots,n\}\). Note que \(P_i\ge P_{i+1}\), pois no primeiro conjunto tem mais secretárias e estamos usando a mesma estratégia em ambos os casos. Note também que é ótimo parar na secretária \(i\), se \(i/n\gt P_i\), pois a probabilidade de a secretária estar no conjunto \(\{1,\cdots,i\}\) é maior que a probabilidade de a secretária estar no conjunto \(\{i+1,\cdots,n\}\). Logo, é ótimo parar quando \( i/n \gt P_i \).
Logo, podemos considerar a seguinte estratégia:
Rejeitar as primeiras \(s-1\) secretárias para estabelecer um benchmark e depois escolher a primeira secretária que for melhor que aquelas rejeitadas. Se ela não for melhor que as anteriores, simplesmente ficamos com a última e, consequentemente, bem insatisfeitos..
Por que a primeira?
Note que qualquer outra estratégia que não escolha a primeira estratégia, estará fazendo a escolha em um conjunto menor e, portanto, terá a mesma ou uma pior probabilidade de estar escolhendo corretamente.
Álgebra:
Seja \(\pi(s,n)\) a probabilidade de escolher a secretária desejada rejeitando as \(s-1\) primeiras interessadas e escolhendo a partir daí a primeira secretária que seja melhor que todas as outras já rejeitadas.
Logo, usando o teorema de Bayes,
\[\pi(s,n)=\sum_{k=s}^{n} P(k\text{-esima ser a melhor e ser selecionada})\]
\[\small{=\sum_{k=s}^{n}P(k\text{-esima ser a melhor})P(k\text{-esima ser selecionada / Ela eh a melhor})}\]
Note que
(1) \(P(k\text{-esima ser a melhor})=1/n\)
(2) \(P(k\text{-esima ser selecionada / Ela eh a melhor})\) pode ser calculada percebendo o seguinte. Se \(k\lt s\), então essa probabilidade vale 0, pois a melhor secretária estava na região de experimentação e nunca poderá ser selecionada. Para \(k\ge s\), a estratégia irá funcionar se uma das \(s-1\) primeiras interessadas for a melhor entre as \(k-1\) interessadas. Ou seja, você vai justamente escolher a \(k\), pois seu conjunto de experimentação formado pelas \(s-1\) possui as melhores secretárias dentre aquelas \(k-1\) que você não deve selecionar.
Logo,
\[\pi(s,n)=\frac{1}{n}\sum_{k=s}^{n} \frac{s-1}{k-1}=\frac{s-1}{n}\sum_{k=s-1}^{n-1}\frac{1}{k}, \;\; 1\lt s\le n\]
Para o caso de \(n=100\), veja a distribuição \(\pi(s,n)\) na figura abaixo:
O valor ótimo \(s^\star\) é igual a menor valor de \(s\) (inteiro) que satisfaz a desigualdade
\[\frac{s}{n}>\pi(s+1,n)\]
Ou seja,
\[\frac{s}{n}>\pi(s+1,n)=\frac{s}{n}\left( \frac{1}{s}+\frac{1}{s+1}+\cdots+\frac{1}{n-1} \right)\]
que implica que
\[\frac{1}{s}+\frac{1}{s+1}+\cdots+\frac{1}{n-1}< 1\]
Aproximação para \(n\) grande:
Uma aproximação importante para \(\pi(s,n)\) ocorre quando \(n\) (o número de secretárias é muito grande). Nesse caso,
\[\pi(s,n)=\frac{s}{n}\log(n/s)\]
Existem referências interessantes em que posso conhecer extensões desse problema?
Sim! Veja essa resposta.