Número médio de inspeções

Question

Considere um conjunto de n elementos cujos valores-chave são $$ 0, 1, ..., n-1 $$ Deixe $ P (I) (0 ≤ i ≤ N-1) $ Seja a probabilidade de o elemento com a tecla que eu é pesquisado. Suponha a seguinte distribuição de $ p (i) 's $ :

$$ p (i)= \ begin {casos} 1/2 ^ {n-1}, & \ text {se eu= 0} \\ 1/2 ^ i, & \ text {de outro modo} \ fim {casos} $$

Assuma a pesquisa linear é usada e toda pesquisa é bem sucedida - cada elemento que procuramos exists.

Qual é o número médio de nós inspecionados para uma pesquisa sob aleatório (elementos na lista vinculada são armazenados em uma ordem aleatória) e qual é o número médio de nós, se classificados com base em sua probabilidade decrescente (isto é, Com o elemento '1', seguido pelo elemento '2', depois '3', e assim por diante, com o último nó contendo elemento '0'.) Para grandes valores de n?

Eu sei que a resposta para a primeira parte é certamente não $ n / 2 $ (já que a probabilidade não é a mesma para todos os elementos), mas eu faço Realmente não sabe muito mais do que isso ... mas quando listado, eu suspeito que deveria ser algo próximo de $$ \ sum_ {i= 1} ^ {n-1} 1/2 ^ {i}} + n * 1/2 ^ {n-1} $$ porque é preciso uma comparação para chegar ao primeiro elemento, dois para o segundo, etc. e o último leva n comparações vezes a probabilidade de 0. Eu também encontrei a $$ \ sum_ {i= O} ^ {∞} a * b ^ a= b / (1-b) ^ 2 $ $ que neste caso seria igual a 2 (b= 1/2), mas não tenho nenhuma pista como enfrentar a caixa de borda - '0'. : (

Eu também estou ciente de este segmento Mas cada um dos números tinha a mesma probabilidade e não é exatamente o mesmo.

Espero encontrar uma resposta para isso, pois tem me incomodado por um bom tempo e estou verdadeiramente curioso sobre o resultado.
Qualquer dica será muito apreciada!

Answer 1

Bem, vamos ver. Por favor, aponte se eu entendi o modelo de problema incorretamente.

Suponha que tenhamos $ n= 5 $ elementos. Suponha que seja classificado no caminho $ s= [1, 3, 4, 0, 2] $ . Em seguida, usando a pesquisa linear, vamos com probabilidade $ (1/2) ^ 3 $ tem 2 etapas em nossa pesquisa e com probabilidade $ (1/2) ^ 4 $ tem 4 etapas em nossa pesquisa.

Então, qual é o número médio de etapas que precisamos encontrar um elemento dando classificação arbitrária $ s $ ? Digamos $ x $ - número de etapas necessárias em nossa pesquisa. Probabilidade de obter $ x= i $ etapas é equivalente a solicitar uma busca por um elemento $ k \ in \ {0, 1,2, .., n-1 \} $ dando nós temos na $ i $ th posição. Que é $$ p (x= i)=sum_ {k= 0} ^ {n-1} p (Search \ for \ k \ | \ the \ element \ k \ é \ \ \ ith \ position) p (o \ element \ k \ is \ \ ith \ posição) $$ então notamos que $ p (o \ elemento \ k \ is \ \ \ ith \ posição)=frac {(n-1)!} {n!}=frac {1} {n} $ porque temos um elemento em uma posição fixa e $ (N-1)! $ possíveis permutações para outros elementos fora do total $ n! $ possível Permutações de nossa $ n $ elementos. Em seguida, notamos que $ \ sum_ {k= 0} ^ {n-1} p (pesquisa \ for \ k \ | \ o \ element \ k \ is \ \ ith \ posição)= 1 $ . Isso significa que $ p (x= i)=frac {1} {n} $ . Então, a expectativa é apenas $ \ sum_ {k= 1} ^ {n} {k} {n}=frac {n + 1} {2} $ .

Claro, a segunda parte é muito mais fácil de derivar, é apenas $$ E (x | classificado \ in \ diminuindo \ probabilidade)=sum_ {k= 1} ^ {N-1} \ FRAC {k} {2 ^ {k}} + \ frac {n} {2 ^ {n-1}} $$ (basta perceber que os elementos serão de < Classe Span="Recipiente de Matemática"> $ 1 $ para $ N-1 $ e, em seguida, o elemento $ 0 $ , no entanto $ 0 $ poderia ser o último elemento porque tem a mesma probabilidade como $ n-1 $ ). Então, nós apenas calculamos a expectativa da distribuição de probabilidade, embora desta vez não para a probabilidade conjunta, mas condicional.