5
$\begingroup$

So I just came across this question and can find nothing like it online.

Suppose you have the numbers $1- 18$ and you randomly distribute them around a circle. What is the expected number of numbers that are greater than both numbers next to them? For example, if you had the sequence $. . . 3 6 4 . . . $, $6$ fulfills the condition but $3$ and $4$ cannot.

You need to do each number individually. I thought for any number $i$ the probability is $1/3$ as it needs to be greater than both of them. However, I think this is wrong. The probability it is greater than any one of its neighbors is obviously $1/2$, but the condition of being greater than one of the neighbors changes the condition of being greater than the second one I assume.

If I found this, then the expected value would just be $18$ times this number. Does anyone have ideas for this? Thanks

$\endgroup$
4
  • $\begingroup$ The probability of fulfilling the criterion is not the same for every number. In the extreme cases $18$ fulfils the criterion with probability $1$ and $1$ fulfils it with probabilty $0$. $\endgroup$
    – Enforce
    Commented Aug 12 at 22:07
  • $\begingroup$ Don't do it for each number, but do it for each space. That's the idea (indicator variable) that I think you're going for. $\endgroup$
    – Calvin Lin
    Commented Aug 12 at 22:11
  • 1
    $\begingroup$ Re Will's answer, see Linearity of Expectation, which includes a proof that the formula applies even when the events are not independent of each other. $\endgroup$
    – user2661923
    Commented Aug 12 at 22:24
  • $\begingroup$ A related problem: What is the expected no. of local maxima in a circular permutation of $n$ numbers? $\endgroup$
    – Amir
    Commented Aug 14 at 15:31

1 Answer 1

Reset to default
7
$\begingroup$

By linearity of the expected value it is indeed $18$ times the probability that a number at a given position is greater than its neighbours.

By symmetry that probability is $1/3$.

So the answer is $18/3=6$.

$\endgroup$
2
  • $\begingroup$ Could you expand on the ‘By symmetry…’?  (I can see that the probability is ⅓, by considering that there are 6 equally-likely ways of arranging any three different numbers, and 2 of those 6 put the largest in the middle.  But I suspect you have a more elegant approach…?) $\endgroup$
    – gidds
    Commented Aug 13 at 10:38
  • $\begingroup$ $X$ is either the largest, in the middle or the lowest among three distinct numbers $X$, $Y$, $Z$. By symmetry those three possibilities happen with the same probability, hence $1/3$. I don't know if that's more elegant than what you wrote, maybe yes if you consider the fewer calculation, the more elegant :) $\endgroup$
    – Will
    Commented Aug 13 at 19:21

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .