Average number of inspections

Question

Consider a set of n elements whose key values are $$0, 1, ..., n−1.$$ Let $p(i) (0 ≤ i ≤ n−1) $ be the probability that the element with key i is searched. Assume the following distribution of $p(i)’s$:

$$p(i) = \begin{cases} 1/2^{n−1}, & \text{if i = 0} \\ 1/2^i, & \text{otherwise} \end{cases}$$

Assume linear search is used and every search is successful - every element we look for exists.

What is the average number of nodes inspected for a search under random(elements in the linked list are stored in a random order) organisation and what is the average number of nodes if sorted based on their decreasing probability(i.e., it starts with the element ‘1’, followed by element ‘2’, then ‘3’, and so on, with the last node containing element ‘0’.) for large values of n?

I know the answer for the first part is surely not $n/2$(since the probability is not the same for all of the elements) but I do not really know much more than that... but when sorted, I suspect it should be something close to $$\sum_{i=1}^{n-1} i*{1/2^{i}} + n * 1/2^{n-1}$$ because it takes one comparison to get to first element, two to the second, etc. and the last one takes n comparisons times the probability of 0. I also found the $$\sum_{i=o}^{∞} a*b^a = b/(1-b)^2$$ which in this case would be equal to 2 (b = 1/2) but I have no clue how to tackle the edge case - '0'. :(

I am also aware of this thread but there each of the numbers had the same probability and it is not exactly the same.

I hope to find an answer to this as it has been bothering me for quite a while and I am truly curious about the result.
Any hint will be greatly appreciated!

Answer 1

Well, let's see. Please point out if I understood the problem model incorrectly.

Suppose we have $n = 5$ elements. Suppose it's sorted in the way $s = [1, 3, 4, 0, 2]$. Then using linear search we are going to with probability $(1/2)^3$ have 2 steps in our search and with probability $(1/2)^4$ have 4 steps in our search.

So, what's the average number of steps we need to find an element giving arbitrary sorting $s$? Let's say $X$ - number of steps needed in our search. Probability to get $X=i$ steps is equivalent to request a search for an element $k \in \{0,1,2,..,n-1\}$ giving we have it at the $i$th position. That is $$P(X = i) = \sum_{k=0}^{n-1} P(search\ for\ k\ |\ the\ element\ k\ is\ at \ ith\ position)P(the\ element\ k\ is\ at\ ith\ position)$$ Then we notice that $P(the\ element\ k\ is\ at \ ith\ position) = \frac{(n-1)!}{n!} = \frac{1}{n}$ because we have an element at a fixed position and $(n-1)!$ possible permutations for other elements out of the total $n!$ possible permutations of our $n$ elements. Then we notice that $\sum_{k=0}^{n-1} P(search\ for\ k\ |\ the\ element\ k\ is\ at \ ith\ position) = 1$. It means that $P(X=i) = \frac{1}{n}$. So, the expectation is just $\sum_{k=1}^{n} \frac{k}{n} = \frac{n+1}{2}$.

Of course, the second part is much easier to derive, it's just $$E(X|sorted\ in\ decreasing\ probability) = \sum_{k=1}^{n-1} \frac{k}{2^{k}} + \frac{n}{2^{n-1}}$$ (just notice that the elements are going to be from $1$ to $n-1$ and then the element $0$, however $0$ could be the pre-last element because it have same probability as $n-1$). So, we just calculating the expectation of the probability distribution, though this time not for the joint probability but conditional.