Вероятность, ожидаемое число

Question

В несортированном массиве элемент является локальным максимумом, если он больше обоих из двух смежных элементов. Первый и последний элементы массива считаются локальными максимумами , если они больше, чем единственный соседний элемент. Если мы создадим массив случайным образом , переставляя числа от 1 до n, каково ожидаемое число локальных максимумов? Докажите ваш ответ правильно, используя аддитивность ожиданий.

Im застрял с этим вопросом, я понятия не имею, как решить эту проблему ...

Answer 1

У вас есть несортированный массив массивов с n элементами. У вас есть две возможные позиции для локальных максимумов. Локальные максимумы могут быть либо на конце, либо между первым и последним элементами. Случай 1: Если вы смотрите на элемент в первом или последнем индексе (массив [0] или массив [n-1]) Какова вероятность того, что элемент является локальным максимумом? Другими словами, какова вероятность того, что значение этого элемента будет больше, чем элемент справа от него? Существует 10 возможных значений, которые могут иметь каждый индекс {0,1,2,3,4,5,6,7,8,9}. Поэтому вероятность 50% в среднем элемента в первом индексе будет больше, чем элемент во втором индексе. (array [0]> array [1]) Случай 2: Если вы смотрите на любой элемент, который ISNT является первым или последним элементом массива (n-2 элемента), то какова вероятность того, что каждый из них будет локальный макс. Как и в первом случае, мы знаем, что существует 10 возможных значений, которые может иметь каждый индекс, поэтому вероятность 1/3, что в среднем, выбираемый элемент будет больше, чем тот, который был до него, и больше, чем тот, который был после него. Объединяя все это: Есть 2 случая, которые имеют 1/2 вероятности локальных максимумов, и есть n-2 случая, которые имеют 1/3 вероятности локальных максимумов. (2 + n-2 = n, все возможные случаи). (2) (1/2) + (n-2) (1/3) = (1 + n)/(3).

Answer 2

разрешима, конечно, но не лишит вас удовольствие делать это самостоятельно. Я дам вам совет. Рассмотрим этот эскиз. Как вы думаете, что представляет? Если вы это выясните, вы узнаете, что шаблон доступен для обнаружения любых n, нечетных и четных. Удачи. Если вы все еще застряли, вам больше понравится.