# A tricky probability question related to expected value

Suppose I order integers $$1,2,3,...,n$$ in some random permutation, such that the integers are lined up like $$a_1, a_2, .., a_n$$. I choose some random index $$j$$ and look at the left of $$a_j$$. I am interested to know what is the expected number of steps I need to take to the left for me to encounter another integer greater than or equal to $$a_j$$? By default, if no value greater than or equal to $$a_j$$ exists to the left, then the number of steps taken is $$j$$.

My approach is the following:

For $$j=1$$, $$E(j)=1$$; For $$j=2$$, there is 1 left neighbor $$a_1$$ which could has equal chance of either being greater or being smaller than $$a_2$$. So, the steps that will be taken is 1 step with probability 1/2 and 2 steps with probability 1/2. So, $$E(2) = 1*1/2 + 2*1/2 = 2$$. For $$j=3$$, there are 2 left neighbours $$a_1, a_2$$. The probability of $$a_2>a_3$$ is 1/2 and the probability $$P(a_1>a_3|a_2.Thus, $$E(3) = 1*1/2 + 2*1/4 + 3*(1-1/2-1/4)$$ Thus, in general $$E(j) = \sum_{i=1}^{j-1}\frac{i}{2^i}+j\times\left(1-\sum_{i=1}^{j-1}\frac{1}{2^i}\right).$$

Does this seem reasonable?

• For $j=1$, $E(j)=1$. For $j=2$, $E(j)=2$, and so on, because the expectation of a constant is the constant. Oct 25, 2021 at 21:51
• @paperskilltrees I suspect $E(j)$ is supposed to be the expected number of steps rather that the expectation of $j$. So for $j=2$ you have $E(j)$ as $\frac32$ Oct 25, 2021 at 22:29
• If $j > 2$ then the probability you take exactly two steps is not $\frac1{4}$ but $\frac{1}{6}$. Consider $P(a_1>a_3>a_2) = \frac16$ while $P(a_1>a_3\mid a_2<a_3) =\frac13$ Oct 26, 2021 at 0:18
• Does that mean that for $j>2$, the probability that you take exactly $n$ steps is $1/(n+1)!$? Oct 26, 2021 at 2:11
• @Henry Any non-standard notation should be explicitly introduced. Sometimes writing a question properly might help answering it (and in any case will help the efforts of others). Oct 26, 2021 at 2:58