Nombre moyen d'inspections

Question

considérer un ensemble d'éléments n dont les valeurs de clé sont $$ 0, 1, ..., n-1. $$ laisser $ p (I) (0 ≤ i ≤ n-1) $ Soyez la probabilité que l'élément avec la clé I est recherché. Supposons la distribution suivante de $ P (I) 'S $ :

$$ p (i)= \ commencer {cas} 1/2 ^ {N-1}, & \ Text {si i= 0} \\ 1/2 ^ i, & \ text {sinon} \ fin {cas} $$

assumer la recherche linéaire est utilisé et chaque recherche réussit - chaque élément que nous recherchons existe.

Quel est le nombre moyen de nœuds inspectés pour une recherche sous aléatoire (les éléments de la liste liée sont stockés dans un ordre aléatoire) et quel est le nombre moyen de nœuds si triés en fonction de leur probabilité décroissante (c'est-à-dire qu'elle commence Avec l'élément "1", suivi de l'élément "2", puis "3 ', et ainsi de suite, avec le dernier nœud contenant l'élément" 0 ".) Pour les grandes valeurs de n?

Je sais que la réponse de la première partie n'est sûrement pas $ n / 2 $ (puisque la probabilité n'est pas la même pour tous les éléments) mais je fais Je ne sais pas vraiment beaucoup plus que ça ... mais quand trié, je soupçonne que cela devrait être quelque chose près de $$ \ sum_ {i= 1} ^ {n-1} i * { 1/2 ^ {i}} + n * 1/2 ^ {n-1} $$ Parce qu'il faut une comparaison pour se rendre au premier élément, deux à la seconde, etc. et le dernier prend n Comparaisons fois la probabilité de 0. J'ai également trouvé la $$ \ SUM_ {I= O} ^ {∞} A * B ^ a= B / (1-B) ^ 2 $ $ Dans ce cas, il serait égal à 2 (B= 1/2) mais je n'ai aucune idée de la possibilité de faire face à l'étui de bord - '0'. : (

Je suis également au courant de Ce fil mais là, chacun des chiffres avait la même probabilité et ce n'est pas exactement la même chose.

J'espère trouver une réponse à cela car cela me dérange depuis un certain temps et je suis vraiment curieux du résultat.
Tout indice sera grandement apprécié!

Answer 1

Eh bien, voyons. Veuillez indiquer si j'ai bien compris le modèle de problème de manière incorrecte.

supposons que nous ayons $ n= 5 $ éléments. Supposons qu'il soit trié dans la voie S= [1, 3, 4, 0, 2] $ . Ensuite, utilisez la recherche linéaire, nous allons avec une probabilité $ (1/2) ^ 3 $ avoir 2 étapes dans notre recherche et avec probabilité $ (1/2) ^ 4 $ avoir 4 étapes dans notre recherche.

Donc, quel est le nombre moyen d'étapes que nous devons trouver un élément donnant un tri arbitraire $ s $ ? Disons $ x $ - nombre d'étapes nécessaires dans notre recherche. Probabilité d'obtenir $ x= i $ est équivalente à demander une recherche d'un élément $ k \ \ {0, 1,2, .., n-1 \} $ Donnant que nous l'avons à la $ I $ TI POSITION. C'est $$ p (x= i)=sum_ {k= 0} ^ {n-1} p (recherche \ for \ k \ | \ \ \ \ \ k \ est \ a \ sur \ position) p (\ ELLE \ K \ IS \ AT \ ITH \ POSITION) $$ Nous remarquons que $ P (\ ELEMENT \ k \ is \ at \ ith \ position)=frac {(n-1)!} {n!}=frac {1} {n} $ parce que nous avons un élément à une position fixe et $ (n-1)! $ permutations possibles pour d'autres éléments hors du total $ n! $ possible Permutations de notre N $ N $ Éléments. Ensuite, nous remarquons que $ \ sum_ {k= 0} ^ {n-1} p (recherche \ for \ k \ | \ \ \ \ \ k \ est \ \ ème position)= 1 $ . Cela signifie que $ p (x= i)=frac {1} {n} $ . Donc, l'attente est juste $ \ sum_ {k= 1} ^ {n} \ frac {k} {n}=frac {n + 1} {2} $ .

Bien sûr, la deuxième partie est beaucoup plus facile à dériver, c'est juste $$ e (x | trié \ in \ décroissant \ probabilité)=sum_ {k= 1} ^ {n-1} \ frac {k} {2 ^ {k}} + \ frac {n} {2 ^ {n-1}} $$ (remarquez simplement que les éléments vont provenir de < SPAN CLASS="MATH-CONTENEUR"> $ 1 $ à $ N-1 $ puis l'élément $ 0 $ , cependant $ 0 $ pourrait être l'élément pré-dernier, car il a la même probabilité que $ n-1 $ ). Donc, nous calculons simplement l'attente de la distribution de probabilité, bien que cette fois pas pour la probabilité conjointe mais conditionnelle.