Блог пользователя Harshlyn94

Автор Harshlyn94, история, 4 года назад, По-английски

Hi everyone ! Can anyone knows the expected number of elements p[i] with the following property in a permutation of size N ? Property: p[i-1] < p[i] > p[i+1] i.e., it is the local maxima in the permutation ? Note : Please do mention the mathematical proof if possible !

  • Проголосовать: нравится
  • +9
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

You can use the "Contribution to the sum" technique (Have a look into this post)

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    It's not clear how can i apply this technique to solve the above problem . Can you explain how ?

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +12 Проголосовать: не нравится

      If I'm correct, for each $$$1<i<n$$$ , the possibility that it is the biggest one among $$$p_{i-1},p_i,p_{i+1}$$$ is $$$\frac{1}{3}$$$, so the answer is $$$\frac{n-2}{3}$$$

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится -10 Проголосовать: не нравится

        How all the events for 1 < i < n can be independent and we adding here simply , since if p[i] is max then why the p[i + 1] is max will carry 1/3 probability ? What my rough guess is it should be O(log(N)) cause let the max element is in the middle and then the next smaller element will be possibly found in N/2 elements to the left or the right and then the next smaller element will be possibly found in N/4 elements to the left or the right and so on ... i.e., if we simulate from N to 3 then we can have something like the above ? P.S. Note that it's my guess .

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится +5 Проголосовать: не нравится

          I just wrote a bruteforce to ensure that I'm correct. You can check the code below.

          Spoiler

          I think you just didn't understand the "contribution to the sum" idea. We don't care if they are independent or not, we are calculating the sum of contribution that the $$$i$$$-th index added to the answer among all permutations.