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<a_3)=1/2*1/2=1/4$.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?

  • $\begingroup$ For $j=1$, $E(j)=1$. For $j=2$, $E(j)=2$, and so on, because the expectation of a constant is the constant. $\endgroup$ Oct 25, 2021 at 21:51
  • $\begingroup$ @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$ $\endgroup$
    – Henry
    Oct 25, 2021 at 22:29
  • $\begingroup$ 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$ $\endgroup$
    – Henry
    Oct 26, 2021 at 0:18
  • $\begingroup$ Does that mean that for $j>2$, the probability that you take exactly $n$ steps is $1/(n+1)!$? $\endgroup$
    – titanium
    Oct 26, 2021 at 2:11
  • $\begingroup$ @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). $\endgroup$ Oct 26, 2021 at 2:58


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.