Остаток в формуле суммирования Эйлера - Маклорена

[vicvolf]

_hum_ в сообщении #1465169 писал(а):

vicvolf в сообщении #1465141 писал(а):

Но вот при $\sigma \to 0$ функция Лапласа стремится к 1 и логарифм отношения $x \to -\infty$, поэтому $e^{\sum {\log x}} \to 0$.

Не совсем так. Аргументом функции является $ (u - \mu)/\sigma$, а потому даже при очень малых $ \sigma$ для значений $u$ из достаточно малой окрестности $\mu$ логарифм отношения не будет вести себя как бесконечно большая величина. Грубо говоря, в этом случае распределение вероятностей просто станет более острым, стремящемся сосредоточится на одном-единственном значении.

Вас что интересует это малая окрестность? Здесь действительно все понятно и сосредоточено на одном значении. Вот, если рассматривается более широкая окрестность, то имеет смысл разговор об асимптотике по переменной $y= (u - \mu)/\sigma$?

[_hum_]

vicvolf
вся наша жизнь проходит в малой окрестности среднего :)

[DeBill]

_hum_ в сообщении #1465023 писал(а):

Не так поняли. Связь между вероятностью и суммой следующая: $p_l = e^{S_{l_o, \mu, \sigma}(l)}$

Т.е., чтобы найти асимптотику вероятности, нужно найти асимптотику суммы. Что, собственно, и было сделано...
И что Вам не нравится? Ответ? Ну, что выросло, то выросло...
Другое дело, что ответ нехорош - Ваша "вероятность" либо ну очень маленькая, либо ну очень большая (в зависимиости от $l$) (вероятность - стремится к бесконечности! Во как... ). И означает это, что, по всей видимости, в выводе формулы для $p_l$ имеются ошибки....
Не могли бы Вы привести соответствующий вывод (прям стартуя с инженерной постановки задачи)?

[_hum_]

DeBill
В самом простом варианте иженерная задача выглядит примерно следующим образом: пусть имеется простейший (только с двумя конфликтными направлениями движения) регулируемый перекресток с заданной фиксированной длительностью цикла $C$ переключения сигналов. Предположим, что длительность зеленого сигнала одного из направлений мы можем менять следующим образом:
- если к концу зеленого сигнала очередь все еще остается, то увеличиваем во всех последующих циклах длительность этого зеленого сигнала на $\Delta$ секунд (с сохранением общей длительности цикла, то есть, отбираем одну секунду зеленого у конфликтного направления);
- в противном случае забираем $\Delta$ секунд (и отдаем в зеленый сигнал конфликтного направления).
Спрашивается,
1) каково будет распределение вероятностей длительностей зеленого сигнала (чтобы понять, насколько вероятен случайный "дрейф" зеленого сигнала далеко от нужного для пропускной способности значения), и как именно она будет зависеть от величины $\Delta$ ;
2) как быстро при смене средней интенсивности движения произойдет "подстройка" зеленого сигнала под новую нагрузку, и насколько эта скорость будет зависеть от $\Delta$ .

Эта задача вроде бы у меня свелась к задаче неоднородного случайного блуждания в варианте:
- пространство состояний $\{0, 1,..., l_o\}$, где $l_o = C/\Delta$,
- вероятности регулярных (то есть, не из крайних состояний) переходов (при допущении, что количество прибывающих за цикл транспортных средств распределено примерно по нормальному закону):
$p_{l \to l} = 0,$
$p_{l \to l+1} = 1-\Phi\bigg(\dfrac{\frac{l}{l_o} - \mu}{\sigma}\bigg)$,
$p_{l \to l-1} = \Phi\bigg(\dfrac{\frac{l}{l_o} - \mu}{\sigma}\bigg)$,

где $ \mu, \sigma$ - матожидание и ско нормированной на максимальную пропускную способность интенсивности прибытия транспортных средств.
В крайних состояниях вероятности переходов для простоты можно положить единицами для выхода из состояния.

Отдельно исследование такого рода блужданий я не нашел, потому обратился к теории марковских цепей. В этом ключе интересующее меня распределение вероятностей - это стационарное распределение в соответствующей марковской цепи. Его выражение описывается формулой, наподобие этой для $\pi_k$. Все остальное - мои попытки проанализировать эту формулу (в том числе с целью использовать ее для последующей оценки зазора спектрального радиуса, который напрямую связан со скоростью сходимости к этому распределению).

[vicvolf]

_hum_ в сообщении #1464897 писал(а):

vicvolf
хотелось бы каких-то обоснований, а не верь на слово

Посмотрите Прахара "Распределение простых чисел" стр. 422 Теорему 1.5 формулу (1.8) и Примечание 1 на стр. 423.

[_hum_]

vicvolf
Спасибо, но похоже, эта формула - частный случай формулы Эйлера - Маклорена. Соответственно, следует ожидать все тех же трудностей при ее использовании. Например, для применения формулы (1.8) необходимо показать (как того требуют условия теоремы 1.5), что производная монотонна. А это не так просто сделать. (Примечание же на следующей странице помимо того, что требует проверки условий на производную, так еще и включает интеграл от производной в конечную формулу, что делает ее ничуть не привлекательнее использования формулы оценки остатка в формуле Э-М напрямую).

[vicvolf]

_hum_ в сообщении #1467788 писал(а):

Спасибо, но похоже, эта формула - частный случай формулы Эйлера - Маклорена.

Да, частный случай.

Цитата:

Соответственно, следует ожидать все тех же трудностей при ее использовании. Например, для применения формулы (1.8) необходимо показать (как того требуют условия теоремы 1.5), что производная монотонна. А это не так просто сделать. (Примечание же на следующей странице помимо того, что требует проверки условий на производную, так еще и включает интеграл от производной в конечную формулу, что делает ее ничуть не привлекательнее использования формулы оценки остатка в формуле Э-М напрямую).

Нет таких сложностей нет, именно по тому, что это частный случай формулы Эйлера-Маклорена. Там требуется не монотонность производной, а монотонность самой функции, что выполняется.

[_hum_]

vicvolf в сообщении #1467808 писал(а):

Нет таких сложностей нет, именно по тому, что это частный случай формулы Эйлера-Маклорена. Там требуется не монотонность производной, а монотонность самой функции, что выполняется.

Да, точно, там требуется только монотонность функции. Но в таком варианте пользы от указанного разложения все же нет, поскольку непонятно, насколько может быть велик по порядку остаток.

[DeBill]

_hum_
Все -не так, как нам кажется...
1. Вы используете аппроксимацию нормальным законом. Однако случайная величина "количество подъехавших машин" обычно описывают пуассоновским распределением (ибо считают поток машин - простейшим потоком). Конечно, для распределения Пуассона тоже можно применить ЦПТ, и аппроксимировать его нормальным; однако при этом будет иметь жесткая связь между матожиданием (это у Вас $\mu$), и СКО ....
2. Расчетные формулы (из ссылки) - это для цепей с непрерывным временем (и те лямбды и мю - это не вероятности переходов, а их интенсивности - то , что в ссылке называют rate of birth). Так что формулы те нам не помогут, и уточнять их - излишне...
3. Асимптотика (при сигме, стремящейся к нулю) - мне кажется не очень разумной - в силу замечания 1). Но - пусть так. Тогда при сигме, меньшей трети дельты, процесс быстро-быстро скатится на два состояния, ближайших к $\mu\Delta$, и будет там болтаться. При этом время (кол-во циклов работы сфетофора) скатывания в этот режим будет практически равно расстоянию от начального состояния до этого "периодического", ( отличие будет иметь порядок $e^{-\frac{\Delta}{\sigma^2}}$ - т.е., офигенно малым)
4. О марковости: что же, получается, те , кто не успел проехать - аннигилируются? Или очередь накапливается таки - тогда есть память о прошлом - нет марковского процесса.
5. О предельных вероятностях для марковской цепи: это вещь полезная , но....Вот пусть Ваши светофоры работают по идиотски, а именно: после каждого цикла, время работы либо не меняется - с вероятностью 0.5, либо уменьшается на секунду. После достижения длитетьности в 1 секунду, вместо убавления - увеличение (до достижения макс. длительности в 1 минуту - потом - снова уменьшение, и т.д.). Вот это - чисто марковская цепь; ее предельные вероятности : все состояния (а их - 120 штук: состояния определяется временем работы и типом этапа убывание/возрастание) равновероятны. И как же они работают по "почти достижению предельных верятностей"? Да по-идиотски: время работы так и будет меняться от 60 до 1, и обратно, с зависанием на некоторых местах, со случайным периодом - ужасно, короче. И чем нам поможет знание о времени, за которое мы выйдем на этот "стационарный режим" ? Кстати, для этого простого примера можно явно посчитать вероятности перехода прям за много шагов - по Бернулли, из начального состояния, например, 30; - и смотреть на этот ползущий горбик и его размазывание - и чё?
6. Если все же нужда в предельных вер-х есть, то модель надо бы использовать другую. И ближе всего - системы массового обслуживания. Это тоже даст марковскую цепь, но... Именно, следует считать поток автомашин - простейшим, с заданной интенсивностью. Светофор будем считать каналом обслуживания, со (средним) временем обслуживания, равным времени на проезд светофора. Как то еще надо заформализовать то, что время работы фиксировано, и есть период "красный" - непросто, вобщем, и состояний придется ввести до фига - но, видимо, возможно...

[_hum_]

DeBill
Спасибо за интерес к моей проблеме. Отвечаю по порядку.

DeBill в сообщении #1468014 писал(а):

1. Вы используете аппроксимацию нормальным законом. Однако случайная величина "количество подъехавших машин" обычно описывают пуассоновским распределением (ибо считают поток машин - простейшим потоком).

Пуассоноским распределением обычно описываются "свободные потоки", когда транспортные средства друг с другом не взаимодействуют. Таких очень мало в городских условиях (где много светофоров, на которых происходит образование групп транспортных средств (ТС)).

DeBill в сообщении #1468014 писал(а):

Конечно, для распределения Пуассона тоже можно применить ЦПТ, и аппроксимировать его нормальным; однако при этом будет иметь жесткая связь между матожиданием (это у Вас $\mu$), и СКО ....

С учетом сказанного выше нормальный закон будет аппроксимировать неизвестное распределение случайных прибытий, а потому хоть дисперсия и останется пропорциональна матожиданию, но коэффициент пропорциональности будет отдельной степенью свободы (итого, получаем нормальный закон с теми же двумя параметрами).

DeBill в сообщении #1468014 писал(а):

2. Расчетные формулы (из ссылки) - это для цепей с непрерывным временем (и те лямбды и мю - это не вероятности переходов, а их интенсивности - то , что в ссылке называют rate of birth). Так что формулы те нам не помогут, и уточнять их - излишне...

Я не говорил, что это в точности эти формулы, я говорил "наподобие". Аналогичные формулы есть и для случая дискретного времени, просто прямые ссылки дать проблематичнее (те, что я нашел, - в книгах и статьях. См, например, R. Serfozo, Basics of Applied Stochastic Processes, Probability and its Applications. Springer-Verlag Berlin Heidelberg 2009, p. 62, Example 94. Random Walk.).

DeBill в сообщении #1468014 писал(а):

3. Асимптотика (при сигме, стремящейся к нулю) - мне кажется не очень разумной - в силу замечания 1).

Я так понимаю, поскольку замечание 1 , с учетом сказанного, не действует, то данный пункт можно опустить?

DeBill в сообщении #1468014 писал(а):

4. О марковости: что же, получается, те , кто не успел проехать - аннигилируются? Или очередь накапливается таки - тогда есть память о прошлом - нет марковского процесса.

Да, это хорошее замечание. Но наверное тут можно ответить так - если нет постоянного накопления очереди (а такого, по идее, в длительной перспективе быть не должно, поскольку система тогда начнет устойчивый тренд на увеличение зеленого, и через определенное время накопление очереди исчезнет - останется только случайная остаточная очередь из-за случайных флуктуаций интенсивности), и если $ \sigma / \mu$ достаточно мало, то остаточная очередь будет мала по сравнению с основной интенсивностью прибытия. И если считать, что $\Delta$ не очень велика, то статистической зависимости от этой остаточной в предыдущем цикле очереди практически не будет (тот остаток флуктуации интенсивности, которая образовала остаточную очередь в предыдущем цикле, даcт незначительную независимую случайную прибавку к интенсивности в текущем цикле).

DeBill в сообщении #1468014 писал(а):

5. О предельных вероятностях для марковской цепи: это вещь полезная , но....Вот пусть Ваши светофоры работают по идиотски, а именно: после каждого цикла, время работы либо не меняется - с вероятностью 0.5, либо уменьшается на секунду. После достижения длитетьности в 1 секунду, вместо убавления - увеличение (до достижения макс. длительности в 1 минуту - потом - снова уменьшение, и т.д.). Вот это - чисто марковская цепь; ее предельные вероятности : все состояния (а их - 120 штук: состояния определяется временем работы и типом этапа убывание/возрастание) равновероятны. И как же они работают по "почти достижению предельных вероятностей"? Да по-идиотски: время работы так и будет меняться от 60 до 1, и обратно, с зависанием на некоторых местах, со случайным периодом - ужасно, короче.

Если я правильно понял вашу мысль, она было наподобие, а давайте организуем обычное случайное блуждание (с вероятностью 0.5 - увеличиваем на 1, с вероятностью 0.5 уменьшаем). Спрашивается, какая польза от предельных вероятностей. Работает ужасно.
В таком варианте польза тоже есть, по крайней мере вы будете знать, как часто вы будете оказываться в той или иной длительности (и тем самым сможете предсказать, например,среднюю за час очередь из скапливающихся транспортных средств).
Но, конечно, такой глупый алгоритм применять никто не будет. В приведенном же мною алгоритме предполагается, что вероятности переходов будут зависеть от текущего состояния не только случайно, но еще и детерминированно (то есть, находясь в текущем состоянии мы не просто бросаем монетку, а выбираем для бросания монетку со смещенным центром тяжести, причем смещения зависит от длительности текущего сигнала).
В принципе, именно это изначально и побудило меня заинтересоваться данным вопросом (а именно, насколько случайное блуждание такого типа будет отличаться от обычного случайного блуждания. Например, насколько далеко оно сможет "дрейфовать" от среднего).

DeBill в сообщении #1468014 писал(а):

6. Если все же нужда в предельных вер-х есть, то модель надо бы использовать другую. И ближе всего - системы массового обслуживания. Это тоже даст марковскую цепь, но...

Во-первых, ТМО заточена под непрерывное время, во-вторых, она, как вы сами указываете, использует тот же аппарат анализа марковских процессов. Ну и, в-третьих, классические системы массового обслуживания не подходят, потому что они не работают с нестационарными процессами обслуживания (не рассматривают периоды наличия "красного света" и "зеленого"), а делать какое-то усреднение - выливать с водой ребенка (ведь вся суть в том, что происходит и меняется от цикла к циклу, а не рассматривается "в среднем" за большой период времени)

[DeBill]

_hum_
1. Принято. Видимо, при формировании потока светофорами, порушатся все принципы простейшего потока (будет и неоднородность, и неординарность, да и с последействием - напряг). Будут двигаться "пакеты" из машин. Правда, при отсутствии синхронизации ("зеленой волны"), пакеты эти будут резаться на части - случайно, что и приведет к какому-то непонятному... Кстати, этот вопрос - об описании полученного потока - видимо, заслуживает своего отдельного описания (и, это, скорее всего - вопрос то практически важный - уже сделано).
2. Да, я посмотрел (это легко из формул для равновесия - во всяком случае, когда "блуждание" наше - симметрично, что и есть в Вашем случае - по крайней мере, когда в одной из точек - "центральной" - вероятности перехода равны в точности половинке ) - формулы такие же получатся, да.
3. Мы одинаково непоследовательны... Я: малые сигмы - сомнительны. Но давайте их все-таки посмотрим.
Вы: малые сигмы - важны! Поэтому - опустим этот случай...
4. Возможно... Здесь есть еще одна деталь: при расчете вероятности появления очереди, предполагается, что , типа, все машины поступили на проезд в начале "зеленого" цикла, и терпеливо ждут проезда. Но могло случиться так, что основная масса ожидаемых машин прибыла к концу этого цикла (а так и будет при несогласованной работе соседних светофоров) - и очередь таки образуется.
5.

_hum_ в сообщении #1468126 писал(а):

Если я правильно понял вашу мысль,

Неправильно. Этот пример к Вашей схеме отношения не имеет. Этот пример - просто иллюстрация того, как ужасно может выглядеть режим работы марковской цепи после выхода на предельные вероятности.
2+3. Ваши расчетные формулы (они - правильные - при надлежащем понимании их)дают: для сигмы, равной одной пятой от дельты, предельные вероятности легко считаются: для центрального состояния: 0.4999999997, для соседних: 0.2499999993, для следующих двух: 0.0000000005, дальше точности не хватат (если мой калькулятор не врет). Для сигмы, равной трети дельты - похуже, там уже отличие порядка 5 процентов вылазит.. Но боле-мене ясно: блуждание (для нормального закона) - в пределах"три сигмы, деленные на дельту".
6. Ваш алгоритм - очень хорош: он автоматически подстраивается под интенсивность потока, да, что особо важно в силу нестационарности его (час пик, и т.п.), и даже устанавливает синхронизацию с соседними светофорами, видимо. Но: после достижения оптимума, он, собака, все время пытается выйти из него...Я так и вижу: водитель, после светофора, бешено мчится, чтоб успеть на зеленый на следующем...Уф, успел! Светофор: успел? Уменьшим время работы! Представляю, как это будет бесить водителей...Может, по достижению режима "все успели проехать" переключить светофор на реагирование по встречному потоку? Тогда, по крайней мере, оптимальное состояние (если таковое есть) станет устойчивым...

[_hum_]

DeBill в сообщении #1468331 писал(а):

Кстати, этот вопрос - об описании полученного потока - видимо, заслуживает своего отдельного описания (и, это, скорее всего - вопрос то практически важный - уже сделано).

Из того, что я видел, ничего путного под описание таких потоков пока не придумали (да и вряд ли можно найти, ведь зависит от многих факторов, начиная от расположенных рядом светофоров, и оканчивая, насколько согласованно они работают) - классически предлагают смесь пуассоноского с эрланговским, но там столько параметров, что лично я смысла в использовании их в подобных расчетах не вижу.

DeBill в сообщении #1468331 писал(а):

4. Возможно...

Все-таки, подумав, пришел к выводу, что в таком варианте (когда считается, что остаточная очередь пренебрежимо мала), исследование получается не очень интересным (Получается, в этом случае ничего нельзя сказать о распределении вероятностей длительностей при которых будут накапливаться значительные остаточные очереди. А ведь это почти самое интересное. Да и тогда оценку скорости перехода в стационарное состояние нельзя будет использовать :( ). Есть идея, что поскольку в стационарном состоянии остаточная очередь как случайная величина будет иметь стационарное распределение, то можно попробовать как-то его найти, и тогда просто нужно будет учесть его в выражении для переходных вероятностей (там тогда будет фигурировать распределение суммы независимых случайных величин - остаточной очереди и количества прибывших за цикл транспортных средств). Но вот как найти распределение очереди - вопрос...

DeBill в сообщении #1468331 писал(а):

Здесь есть еще одна деталь: при расчете вероятности появления очереди, предполагается, что , типа, все машины поступили на проезд в начале "зеленого" цикла, и терпеливо ждут проезда. Но могло случиться так, что основная масса ожидаемых машин прибыла к концу этого цикла (а так и будет при несогласованной работе соседних светофоров) - и очередь таки образуется.

Можно рассматривать, что цикл начинается с красного сигнала и оканчивается выключением зеленого. В итоге, те, кто прибывают в конце, и потому не успевают проехать на зеленый относятся уже к прибывающим на красный в следующем цикле.

DeBill в сообщении #1468331 писал(а):

Ваши расчетные формулы (они - правильные - при надлежащем понимании их)дают: для сигмы, равной одной пятой от дельты, предельные вероятности легко считаются: для центрального состояния: 0.4999999997, для соседних: 0.2499999993, для следующих двух: 0.0000000005, дальше точности не хватат (если мой калькулятор не врет).

Вы о каких формулах ведете речь - о приближенных с помощью Эйлера-Маклорена, или исходных произведениях?:)

Насчет 6. Этот алгоритм не предназначен для работы на тех регулируемых направлениях, которые отвечают за координацию (там совсем другие принципы используются). Он либо для случая, когда вовсе нет координации , либо она, например, по главным прямым направлениям, а алгоритм работает по поворотным и/или второстепенным.

[DeBill]

_hum_ в сообщении #1468676 писал(а):

Можно рассматривать, что цикл начинается с красного сигнала и оканчивается выключением зеленого. В итоге, те, кто прибывают в конце, и потому не успевают проехать на зеленый относятся уже к прибывающим на красный в следующем цикле.

Это я неудачно сформулировал: конечно, цикл начинается с красного, и, поскольку весь цикл "красный-зеленый" имеет фиксированную длину, то мы можем сосчитать вероятность того, что за весь этот период прибыло не более $l$ машин. Я же имел в виду, что из этих $l$ машин многие прибыли - возможно - в конце зеленого цикла. Так что по формулам - успели проехать, а реально - не факт...

_hum_ в сообщении #1468676 писал(а):

Вы о каких формулах ведете речь - о приближенных с помощью Эйлера-Маклорена, или исходных произведениях?:)

О точных (про Эйлера-Маклорена - я по прежнему полон скепсиса...). Тут есть одна деталь: формулы эти - для цепи, "обрезанной по левому концу" (я так думаю - литературу я не смотрел). И что же будет для Вашей цепи ($l_0=60, \mu=25,\sigma =1$)? Пусть $p_0$ - вероятность самого левого состояния. Далее будут перемножаться числа порядка $10^{100}$, и к 25-му состоянию произведение вырастет до, типа, $10^{1000}$, затем начнут уменьшатся, и на 60-м станут порядка $10^{-300}$. Теперь эти все числа мы должны сложить, (будет что-то навроде $10^{1000}$), и из условия нормировки (сумма всех вероятностей равна 1) найти, наконец, $p_0$ (будет типа $10^{-1000}$...) . Жуть!
Вместе с тем, можно чуток схитрить (по крайней мере, для случая, когда $l_0\mu$ - целое: когда цепь "почти симметрична", и из симметрии тогда следует, что вероятности симметричных относительно центра состояний равны): сложить ее вдвое, склеивая воедино симметричные состояния. Тогда "начало" цепи придется на значимый участок, и - для малых сигм, по крайней мере - все легко сосчитается... Вот и сосчитайте для нескольких конкретных значений - возможно, вопрос про Э-М снимется сам собой....

[_hum_]

DeBill в сообщении #1468684 писал(а):

Это я неудачно сформулировал: конечно, цикл начинается с красного, и, поскольку весь цикл "красный-зеленый" имеет фиксированную длину, то мы можем сосчитать вероятность того, что за весь этот период прибыло не более $l$ машин. Я же имел в виду, что из этих $l$ машин многие прибыли - возможно - в конце зеленого цикла. Так что по формулам - успели проехать, а реально - не факт...

Такого не может быть. Если они подъезжают к перекрестку, и очереди нет и горит зеленый сигнал, то они проедут обязательно. Если же начинается красный, то та часть, что не успела проехать стоп-линию на зеленый может рассматриваться как относящаяся уже к следующему циклу (в нашей модели неважно, в какие моменты приезжают транспортные средства внутри цикла. Главное, сколько всего приезжает)

DeBill в сообщении #1468684 писал(а):

Тут есть одна деталь: формулы эти - для цепи, "обрезанной по левому концу" (я так думаю - литературу я не смотрел).

Нет. Эти формулы с обрезкой по обоим концам.
Насчет перемножения и жути - так потому и используется потенцирование и сведение к сумме логарифмов, чтобы такого не было.
И, на всякий случай, $\mu$ - из интервала [0,1] (это не само среднее количество авто, а нормированное на максимальную пропускную способность полосы движения).

[DeBill]

_hum_ в сообщении #1468706 писал(а):

Нет. Эти формулы с обрезкой по обоим концам.

"Обрезка по обоим концам" влечет "есть обрезка слева"....

_hum_ в сообщении #1468706 писал(а):

Насчет перемножения и жути - так потому и используется потенцирование и сведение к сумме логарифмов, чтобы такого не было.

Так логарифмируй - не логарифмируй - жуть никуда не денется...
Я Вам предлагая эффективный способ расчета - а Вы упорно держитесь за "жуткий"....
Про $\mu$: ну да, это я маху дал - в тех моих прикидках все (мю и сигма) было размерное (помножено на эль-ноль).
Ладно.......