6
$\begingroup$

Currently failing at basic probability…

Given a sequence of items, linear search means looking at each in turn and seeing if it's the one we're looking for. (I.e. in the worst case, it's the last item in the sequence or not in the sequence at all and we'll have to look at all items to find it/determine it's not there.)

How many elements of the input sequence need to be checked on average, assuming that the element being searched for is equally likely to be any element in the array?

Ok, we know two things:

  • the element we're looking for is in the array
  • P[the i-th item is the one we're looking for] = $\frac{1}{n}$ for all $i\in\{1,..,n\}$

And I think I'm supposed to get $\frac{n+1}{2}$ or $\frac{n}{2}$ or something thereabout.

Let $X$ be the number of items the linear search algorithm is looking at.

$$\begin{align} P[X=1] &= \frac{1}{n} \\ P[X=2] &= \left(1-\frac{1}{n}\right)\frac{1}{n} \\ P[X=3] &= \left(1-\frac{1}{n}\right)^2\frac{1}{n} \\ & \ \ \vdots \\ \end{align}$$

So

$$\begin{align} \mathbb{E}(X) &= \sum_{i=1}^n i\left(1-\frac{1}{n}\right)^{i-1}\frac{1}{n} \\ &= \frac{1}{n}\sum_{i=1}^n i\left(1-\frac{1}{n}\right)^{i-1} \\ \end{align}$$

That's not something I want to solve myself, so I gave it to Wolfram Alpha and got

$$\left(1-2\left(\frac{n-1}{n}\right)^n\right)n$$

This doesn't look particularly close.

Where did I go wrong?

$\endgroup$
  • $\begingroup$ You say the location is uniform, thus the probability that it is in slot $i$ is $p_n=\frac 1n$ for all $i$, yes? Thus the answer is $\sum i\times \frac 1n=\frac {n+1}2$. This needs to be altered in a small way if you want to allow for the possibility that it isn;t in the list. (in that case $p_n$ is greater than all the others and all the others are equal). $\endgroup$ – lulu Sep 12 '17 at 12:05
  • $\begingroup$ In case you assume $n = 2$ and you are sure that the element is in the array, then $P[X = 1] + P[X = 2] = 1$. But as per your (@User1291) calculation, it is $\dfrac{1}{2} + \dfrac{1}{4} \neq 1$. Hence you should reconsider the calculation of probability for each event. $\endgroup$ – Nash J. Sep 12 '17 at 12:16
4
$\begingroup$

Assuming that there is exactly one item of interest: $$P[X=i]=\frac1n\text{ for }1\le i\le n$$ $$E[X]=\sum_{i=1}^n\frac in=\frac1n\sum_{i=1}^ni=\frac{n(n+1)}{2n}=\frac{n+1}2$$ If $P[X=i]=\left(1-\frac1n\right)^{i-1}\frac1n$ instead then there is a geometric distribution, which can be realised as (say) there are $n$ rolls of an $n$-sided die and we are searching for the first 1 rolled. Here there is an extra $\left(1-\frac1n\right)^n$ probability of doing $n$ comparisons and not finding the desired item, leading to the expectation in this case as $$\left(1-2\left(\frac{n-1}n\right)^n+\left(1-\frac1n\right)^n\right)n$$ $$=\left(1-\left(1-\frac1n\right)^n\right)n$$ which is different from $\frac{n+1}2$ because the desired element may appear more than once in the array.

$\endgroup$
  • $\begingroup$ Why is $P[X=i] = \frac{1}{n}$? $\endgroup$ – User1291 Sep 12 '17 at 12:08
  • 1
    $\begingroup$ @ParclyTaxel What should be the statement in order for his(of @user1291) reasoning to be correct? $\endgroup$ – John D Sep 12 '17 at 12:13
  • 1
    $\begingroup$ @Magnusseen The calculations in the question body imply something like this: we have $n$ rolls of an $n$-sided die and are looking for the first 1 rolled. A geometric distribution. $\endgroup$ – Parcly Taxel Sep 12 '17 at 12:16
  • 1
    $\begingroup$ @ParclyTaxel In his reasoning, he computed $P_k,$ the probability that the amount of search is exactly $k.$ That computation seems correct. If we assume that we will find the element in the array, we should have then $\sum_{k=1}^n P_k=1.$ $\endgroup$ – John D Sep 12 '17 at 12:23
  • 1
    $\begingroup$ @Magnusseen There, he makes the mistake. Not all assumptions in the question were used, in particular that there is exactly one item of interest. $\endgroup$ – Parcly Taxel Sep 12 '17 at 12:25
5
$\begingroup$

Your calculations for $P(X=2), P(X=3)$, etc are incorrect.

For instance you should have, $P(X=2)=P(X=2\mid X\ne 1)\cdot P(X\ne 1)=\frac{1}{n-1}\cdot\frac{n-1}{n}=\frac1n$.

In fact as noted by others $P(X=k)=\frac1n$ for $k=1, 2,\cdots, n$.

$\endgroup$
2
$\begingroup$

This is a matter of conditionality.

In your calculation, you took $1/n$ to be the probability that the element is in the $i$th position under the condition that it was not in any of the positions before $n$. If this were the case, then your calculation of the probabilities for $i\geq2$ would be correct. Unfortunately though, the probabilities don't sum up to one.

Instead, the probability to find the element in the $i$th position is precisely $1/n$ for every $i\in\{1,\dots,n\}$. The probabilities are given, and there is no need to find them. The probabilities are unconditional; events for $i<j$ have no bearing on $P[X=j]$. If you want, you can use this information to find the conditional probabilities. They are not needed in this problem, but you will find that they are not $1/n$.

There is two alarming things in your calculations, hinting at a problem:

  1. You assumed $P[X=2]=\frac1n$ and the calculated that $P[X=2]=(1-\frac1n)\frac1n$.
  2. The probabilities don't sum up to one although they should.
$\endgroup$
1
$\begingroup$

If you wish to include the possibility that the desired object isn't in the array:

Denote by $\psi$ the probability that the desired object isn't in the array. Let $p_i$ denote the probability that it is in slot $i$. Then, since all the $p_i$ are equal, we must have $$\sum_{i=1}^np_i=1-\psi\implies p_i=\frac {1-\psi}n$$

For every $i<n$ the probability that you look at exactly $i$ objects in your search is $p_i$. For $i=n$ the probability is $p_i+\psi$. Thus in this case the expected value is $$\sum_{i=1}^n i\times \frac {1-\psi}n+n\times \psi=\frac {(n+1)(1-\psi)}2+n\psi=\frac {n+1+n\psi-\psi}2$$

Sanity checks: Note that if $\psi=0$ this reduces to the formula we know. Then again, note that if $\psi =1 $ this reduces to $n$, as it should.

$\endgroup$
1
$\begingroup$

Let us assume that the key is present in the list. The expectations of the "cost" of finding the key equiprobably in every position $k$ are $\dfrac kn$, the sum of which is

$$\frac{n(n+1)}2\frac1n=\frac{n+1}2.$$

The correction for the possibility of the key being absent with probability $q=1-p$ yields

$$p\frac{n+1}2+qn.$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.