Expected number of items looked at

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$.


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.


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.