Numero medio di ispezioni

Question

Considerare un set di elementi n i cui valori chiave sono $$ 0, 1, ..., n-1. $$ Let $ P (i) (0 ≤ I ≤ n-1) $ Sii la probabilità che l'elemento con la chiave sia cercato. Supponiamo la seguente distribuzione di $ P (i) s $ :

$$ p (i)= \ Begin {casi} 1/2 ^ {n-1}, & \ testo {se i= 0} \\ 1/2 ^ I, & \ Text {Altrimenti} \ end {casi} $$

Assumere la ricerca lineare viene utilizzata e ogni ricerca ha esito positivo: ogni elemento che cerchiamo esiste.

Qual è il numero medio di nodi ispezionati per una ricerca in caso di casuale (gli elementi nell'elenco collegato sono memorizzati in un'organizzazione ordine casuale) e quale è il numero medio di nodi se ordinato in base alla loro probabilità decrescente (cioè, inizia Con l'elemento '1', seguito da elementi '2', quindi '3', e così via, con l'ultimo nodo contenente elemento '0'.) Per valori di grandi dimensioni di N?

So che la risposta per la prima parte non è sicuramente $ N / 2 $ (poiché la probabilità non è la stessa per tutti gli elementi) ma lo faccio Non so davvero molto più di quello ... ma se ordinato, sospetto che dovrebbe essere qualcosa di vicino a $$ \ sum_ {i= 1} {n-1} I * { 1/2 ^ {i}} + n * 1/2 ^ {n-1} $$ Perché ci vuole un confronto per arrivare al primo elemento, due al secondo, ecc. E l'ultimo prende n Confronti volte la probabilità di 0. Ho anche trovato la $$ \ sum_ {i= o} ^ {∞} A * b ^ a= b / (1-b) ^ 2 $ $ che in questo caso sarebbe uguale a 2 (B= 1/2) ma non ho idea di come affrontare il caso del bordo - '0'. : (

Sono anche a conoscenza di Questo thread Ma ognuno dei numeri aveva la stessa probabilità e non è esattamente lo stesso.

Spero di trovare una risposta a questo come mi ha infastidito per un bel po 'e sono veramente curioso del risultato.
Qualsiasi suggerimento sarà molto apprezzato!

Answer 1

Bene, vediamo. Si prega di segnalare se ho capito il modello problema in modo errato.

Supponiamo di avere $ n= 5 $ elementi. Supponiamo che sia ordinato nel modo in cui $ s= [1, 3, 4, 0, 2] $ . Quindi, utilizzando la ricerca lineare, stiamo andando con la probabilità $ (1/2) ^ 3 $ Avere 2 passaggi nella nostra ricerca e con probabilità $ (1/2) ^ 4 $ Avere 4 passaggi nella nostra ricerca.

Allora, qual è il numero medio di passaggi che dobbiamo trovare un elemento dando l'ordinamento arbitrario $ s $ ? Diciamo $ x $ - numero di passaggi necessari nella nostra ricerca. Probabilità di ottenere $ x= I $ passaggi equivalenti a richiedere una ricerca di un elemento $ k \ in \ {0, 1,2, .., n-1 \} $ Dare che lo abbiamo alla $ I $ Posizione. Cioè $$ P (x= i)=sum_ {k= 0} ^ {n-1} P (Search \ per \ k \ | \ \ element \ k \ è \ at \ Ith \ posizione) P (\ element \ k \ è \ at \ ith \ posizione) $$ quindi notiamo che $ P (\ element \ k \ \ ith \ ith \ posizione)=frac {(n-1)!} {n!}=frac {1} {n} $ perché abbiamo un elemento a una posizione fissa e $ (n-1)! $ Possibili permutazioni per altri elementi fuori dal totale $ n! $ Possibile Permutazioni della nostra $ N $ elementi. Quindi notiamo che $ \ sum_ {k= 0} ^ {n-1} P (Search \ per \ k \ | \ \ element \ k \ è \ at \ ith \ Posizione)= 1 $ . Significa che $ p (x= i)=frac {1} {n} $ . Quindi, l'aspettativa è solo $ \ sum_ {k= 1} ^ {n} \ frac {k} {n}=frac {n + 1} {2} $ .

Naturalmente, la seconda parte è molto più facile da ricavare, è solo $$ e (x | ordinato \ in \ diminuzione \ probabilità)=sum_ {k= 1} ^ {n-1} \ frac {k} {2 ^ {k}} + \ frac {n} {2 ^ {n-1}} $$ (basta notare che gli elementi saranno da < Span Class="Math-Container"> $ 1 $ a $ n-1 $ e poi l'elemento $ 0 $ , tuttavia $ 0 $ potrebbe essere l'ultimo elemento perché ha la stessa probabilità come $ n-1 $ ). Quindi, calcoliamo semplicemente l'aspettativa della distribuzione della probabilità, anche se questa volta non per la probabilità comune ma condizionale.