TYI 26: Attaining the Maximum

(Thanks, Dani!) Given a random sequence a_1,a_2,\dots , a_n, ***a_i \in \{-1,1\}***, n>2, let S_k=a_1+a_2+\cdots +a_k. and assume that S_n=0.  What is the probability that the maximum value of S_k is attained only for a single value of k?

Test your intuition: is this probability bounded away from 0? tends to 0 like 1/\sqrt n? Quicker? Slower? Is there a nice formula?

This entry was posted in Combinatorics, Probability, Test your intuition and tagged . Bookmark the permalink.

21 Responses to TYI 26: Attaining the Maximum

  1. arnabb2015 says:

    What is the probability space?

  2. K says:

    Are $a_i$ independent signed Bernoulli? If not, what is the distribution?

    • Gil Kalai says:

      Yap, I managed to make this very simple question confusing. The a_i are independent Bernoulli conditioned on their sum being zero, or alternatively you can consider the uniform probability distribution on all {-1,1} sequences whose sum is 0.

  3. Devdarsh says:

    1/2 ?

  4. kodlu says:

    Goes to zero as some negative fractional power, maybe -1/3. Since n is even, a fraction f=(1-(1/\sqrt{n}))/2 have max zero, due to more – than + occurring. A fraction f/4 have at least two maxima S_k=+1 for k=1,n-1 by similar argument. But then a fraction 2*(1/16)f Have at least two maxima at 2i+1,n-1-2i for i=0,1 etc.

  5. gowers says:

    My intuition says that the probability is bounded away from zero. (Rough, nonrigorous, and possibly completely incorrect reason — that it is easy to transform a typical sequence with just one maximum to one where there are more, by reversing the choices on either side.)

  6. doron says:

    I’d guess 1/4. Among all dyck paths of length 2n, roughly 1/4 don’t touch the x-axis before the end.

  7. Lear Bahack says:

    Let’s cut the sequence to minimal intervals that each sum up to zero. There are O Sqrt(n) such intervals. The maximal S is also O (sqrt(n)) so there is a bounded chance that this maximum is attained only in one such interval (I would even say this probability tends to one).

    So we reduce the question to cases where the S is never zero except for the very end and beginning. Intuitively, the maximum is very lockal, meaning that it it appears more than once the apperences are probably very close. So N is not so important, and my guess is that the probability is bounded from zero.

  8. K says:

    If the value of k for which $S_k$ attains its maximum is not too large compared to $n$, say, $kn$ remains trapped in the negative side of the axis. This, unconditionally has probability $O(1/ \sqrt{n}$, but even given the condition $S_n=0$, must have a probability going to zero.

  9. Amir Abu-Fraiha says:

    Maybe completely wrong but:
    From counting some specific cases it seems that the amount of sequences with maximum equal to some value M and attained only once is equal to the amount of sequences with maximum equal to M-1 and attained more than once.
    If this is correct that means that the probability in the question is exactly 1/2.

    • Amir says:

      For example there is 1 sequence (of length 2n) admitting a maximum n, and there is also only 1 sequence attaining maximum n-1 more than once (twice actually).

      Another and more convincing example is of sequences with maximum 0, reaching it at least twice. There are C_n such sequences (catalan number). Also the amount of sequences reaching maximum 1 only once is (not hard to compute) the sum of the products C_k*C_(n-1-k), which equals to C_n ofcourse.

      • domotorp says:

        That’s it, the Catalan numbers! It’s not hard to determine the exact number of sequences with a single/multiple maximum using them, but somehow one doesn’t think about them as they are 45 degrees rotated… Btw, when I’ve first read this, I’ve thought that this was an April’s fools’ edition with the distribution intentionally not specified and the question anyhow didn’t make much sense for non-discrete distributions.

  10. Amir Abu-Fraiha says:

    SPOILER ALERT:
    If you still want to think of the question above don’t read further

    ANSWER:
    The terminology here is not perfect, since I thought of this question as concerning “mountain ranges” but I tried to write as the question is phrased – using sequences that sum up to zero.

    The sets of sequences I’ve specified above indeed has the same size.
    Actually, denote by A_m the set of all sequences of length 2n that has maximum m and achieve it only once. (and ofcourse sum up in total to zero).
    Denote by B_m the set of all sequences of length 2n that has maximum m-1 and it appears more than once.
    Lastly, denote by D_m the set of all pairs (s,k) where s is a sequence of length 2n-2 that sum up to zero and has maximal partial sum equal to m-1, and k is such that the sum up to k is m-1.
    When m is at least 1, all three sets has the same size.
    We have a bijection from D_m to A_m by taking the sequence s = a_1, a_2, …, a_(2n-2) along with apropriate k to the sequence s’ = a_1, a_2, …, a_k, 1, -1, a_(k+1), …,a_(2n-2) which ofcourse belongs to A_m. This map is clearly a bijection since we can just remove these added 1,-1 from where a sequence in A_m gets its unique maximum, together with that right index k and have the inverse map.
    We also have a bijection from D_m to B_m. This one is a bit more complicated.
    Consider a pair (s,k) in D_m. The sequence s attain its maximum for the first time for some index i that is at most k. We map (s,k) then to s’ = a_1, a_2, …, a_i, -1, a_(i+1), …, a_k, 1, a_(k+1), …,a_(2n-2) (where the elements in s named as before). This one is a bit tricky, but some observsation gives the inverse map to this one: for a sequence in B_m remove -1 after the first maximum and remove 1 before the second maximum. Could be explaind better or proven rigurously but i will leave it to whoever reads this.

    This all means that the amount of all sequences with a unique maximal partial sum is equal to the amount of all sequences with a maximum point that is not unique.
    That implies that the probability in question is exactly 1/2.

    • The explanation is fine. I just had to write down three examples for the second bijection.

      My intuition was totally off. I thought that the probability is 0.

      • Amir Abu-Fraiha says:

        Yes it is easier to understand when looking at the sequences as consisting of upstrokes and downstrokes along a segment drawing a picture resembling a mountain (“mountain range”).
        /\
        / \/\
        \/
        For example the drawing corresponds to the sequence 1, 1, -1, -1, 1, -1, -1, 1.

        Then what the se ond bijection does is basicly taking the whole segment between the first m-1-high peek and the peek on the index k and lowers it by 1.

  11. Liran Katzir says:

    Thanks for this is a beautiful question.

    The short answer is 1/2.
    The longer answer is:
    0. n must be even so we “rename” it to 2n.
    1. There are a total of (2n choose n) {-1,+1} sequences
    2. There are (2n-1 choose n-1) legal sequences (with a single maximum).
    3. Thus the probability of getting a legal sequence is (2n-1 choose n-1)/(2n choose n)=1/2

    To see why 2. is true consider all possible sequences with n ‘1’ and n-1 ‘-1’.
    There are (2n-1 choose n-1) such sequences. We now show a 1-to-1 correspondence to the set of legal 2n sequences.
    Add a ‘-1’ immediately after the first maximum.
    Note since the sequence start with 0 sum and ends with 1 sum we must have a maximum >= 1 (and at least one).
    After adding a ‘-1’ right after the first maximum, all other maximum values are reduced by 1.
    This processes is reversible thus we get a 1-to-1.

    Cheers,
    Liran.

  12. kodlu says:

    @liran katzir, @amir abu-fraiha, well done. clearly my intuition failed miserably.

  13. victor says:

    Can we extend this to continuous time? Then, the question would ask, For a Brownian Bridge process, what is the probability that a path has a unique maximum?

    This analysis shows the answer should be 1/2. Any obvious reason we can’t extend this result to Brownian Bridge?

  14. Austin says:

    In my first reading of the problem, I missed the S_n = 0 condition, and considered all 2^n possible sequences of +1’s and -1’s. This version is also interesting to think about!

    ** SPOILERS BELOW **

    In this version of the problem, the probability that S_k attains its maximum for a single value of k is greater than 1/2. To see why, it’s helpful to first consider an infinite series of random +1’s and -1’s. Each time the partial sum sets a new record, the probability that this record is immediately broken by the next term is 1/2. If the record isn’t immediately broken, then it must be tied later before the next record can be set. Therefore, on average, each record sum occurs 2 times before being surpassed. This implies the following: If we pick a positive integer N, and truncate the infinite series at a random time during the interval in which N is the reigning record partial sum, then the chance that this record has been attained only once up to that time is 1/2.

    For a *finite* series of random +1’s and -1’s, part of this argument doesn’t hold up: a record which isn’t immediately broken may or may not be tied before the series terminates. So, the last record sum occurs, on average, less than 2 times. Thus the probability that the record sum is attained only once is more than 1/2. (Test *your* intuition: Does this probability converge to a constant? If so, is that constant 1/2? More than 1/2?)

    I wonder if the infinite series reasoning can also settle the original problem, with the S_n = 0 condition in place. This seems plausible, since an infinite random walk on the integers is recurrent and thus “simulates” the finite problem infinitely many times…

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s