Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

O que é o problema conhecido como Problema da Secretária?

0 votos
164 visitas

1 Resposta

+1 voto
respondida Dez 12, 2015 por danielcajueiro (5,186 pontos)  

A imagem será apresentada aqui.

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:

Secretary problem

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.

...