Вероятность и статистика · объяснение и практика

Как случайные точки оценивают площадь и её неопределённость

Как доля случайных попаданий оценивает площадь внутри известной рамки, откуда берётся стандартная ошибка и почему один удачный запуск не является точным доказательством.

Рука ставит оранжевый столбик между двумя синими столбиками разной высоты.

В теме Случайные процессы и имитация: углубление · Учебная карта

В маршруте Вычислительные и планируемые эксперименты · 10 тем

Главная мысль

Если точки независимо равномерны в рамке площади A, площадь области оценивают как A·K/N. Индикатор попадания имеет вероятность p и дисперсию p(1−p), поэтому модельная стандартная ошибка оценки равна A√(p(1−p)/N).

Случайная точка превращает площадь в вероятность

В единичном квадрате выделим область под кривой y=x². При независимом равномерном выборе точки (X,Y) вероятность попадания Y≤X² равна площади этой области. Для каждой точки записываем единицу при попадании и ноль иначе. Среднее этих индикаторов становится оценкой площади, поскольку площадь всей рамки равна единице.

Если рамка имеет площадь A, та же доля оценивает не площадь, а её отношение к A. Поэтому результат нужно умножить на A. Равномерность относится к площади: обе координаты выбирают согласованно с рамкой. Кластер точек у удобного края без весовой поправки изменит вероятность попадания и тем самым саму оценку.

Отдельно считаем результат и его случайный разброс

Допустим, из 1200 точек в область попали 396. Оценка равна 396/1200=0,33. Подставная стандартная ошибка √(0,33·0,67/1200) примерно 0,0136. Нормальная приближённая полуширина 1,96 такой ошибки составляет около 0,0266. Это описание неопределённости по модели независимых точек, а не точная граница ошибки каждого запуска.

Здесь площадь можно отдельно проверить интегралом: ∫₀¹x²dx=1/3. Близость 0,33 к этому значению полезна для проверки реализации, но не доказывает безошибочность метода на любой другой области. При повторных независимых наборах оценка изменяется. Увеличение N вчетверо уменьшает стандартную ошибку вдвое при неизменной модели, а не вчетверо.

Пример

Если одна и та же случайная точка скопирована тысячу раз, появилась ли точность тысячи испытаний?

Нет. Записи полностью зависимы, поэтому формула ошибки для тысячи независимых индикаторов неприменима. Число строк не равно числу независимых выборов.

Результат зависит и от генератора, и от правила остановки

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

Нулевое число попаданий не означает доказанную нулевую площадь. Подставная формула тогда даёт нулевую ошибку, но такая оценка неопределённости ненадёжна для редкого события; нужны подходящие биномиальные границы или иной план. Произвольное продолжение только до красивого ответа также меняет процедуру. Монте-Карло оценивает интеграл с неопределённостью, а не заменяет аналитическое доказательство точного значения.

От чтения к действию

А теперь — вы

В рамке площадью 6 независимо равномерно выбрали 1000 точек, 300 попали в область. Какова оценка её площади методом доли попаданий?

Частые вопросы

Почему результат умножается на площадь рамки?

Доля попаданий оценивает относительную площадь области внутри рамки. Для абсолютной площади требуется её масштаб.

Достаточно ли одного совпадения с точным ответом?

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

Углублённый разбор

Гарантия Хёффдинга для ограниченной оценки Монте-Карло

Граница Хёффдинга даёт заранее заданную вероятность ошибки для ограниченных независимых прогонов. Ей не требуется подставлять оценённую дисперсию из того же запуска.

Перед началом: Ожидание, дисперсия и ковариация; Независимые выборки и взвешенные средние.

Определение и постановка

Пусть Y₁,…,Yₙ независимы, имеют одно среднее μ и лежат в известном интервале [a,b]. Тогда P(|Ȳ−μ|≥ε)≤2exp[−2nε²/(b−a)²].

Вывод и вычислительный критерий

Масштаб интервала входит квадратом. После перехода Z=(Y−a)/(b−a) задача сводится к значениям между нулём и единицей; ошибка ε также делится на ширину интервала. Экспоненциальная оценка объединяет верхний и нижний хвосты, отсюда множитель два.

Для гарантии риска не выше δ достаточно n≥(b−a)²ln(2/δ)/(2ε²). Берут целое округление вверх. Это планирование до опыта: число точек зависит от требуемой ошибки и доказанного диапазона, а не от того, насколько удачно выглядит текущий результат.

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

Условия и границы вывода

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

Если прогоны зависимы, нельзя автоматически подставлять их количество как n независимых испытаний. Для марковских прогонов, повторов одной случайной выборки или общих случайных потоков требуется иное обоснование.

При последовательном просмотре результата и произвольной остановке та же фиксированная граница не становится гарантией одновременно для всех дат. Заранее выбранный горизонт и последовательный доверительный процесс являются разными процедурами. Для модели с неограниченными весами предпосылка ограниченности также может исчезнуть, даже если редкие большие значения ещё ни разу не встретились.

Гарантия относится к случайности исходной выборки при фиксированной вероятности успеха. Она не является апостериорной вероятностью того, что уже вычисленная ошибка мала. Если объём выбирается после просмотра промежуточных результатов, исходное утверждение для одного фиксированного n само по себе не разрешает неограниченное последовательное подглядывание.

Разобранная задача

Условие. Независимые индикаторы попадания оценивают площадь. При n=800 найдите гарантированную верхнюю границу риска ошибки ε=1/10 и сравните её с1/1000.

  1. Для индикаторов a=0,b=1, поэтому ширина диапазона равна единице.
  2. Показатель экспоненты равен−2·800·(1/10)²=−16.
  3. Двусторонняя граница равна2e⁻¹⁶, приблизительно2,25·10⁻⁷.
  4. Она меньше1/1000: достаточно заметить e¹⁶>2¹⁶>2000, поскольку e>2.

Ответ. Вероятность абсолютной ошибки не меньше0,1 ограничена сверху2e⁻¹⁶<0,001.

Проверка. Неравенство без десятичных приближений следует из2e⁻¹⁶<2/65536=1/32768<1/1000. Оно проверяет нужный риск точным рациональным сравнением.

Где легко ошибиться. Случайно малая подставная MCSE не заменяет известную априорную ширину диапазона в гарантии Хёффдинга.

Проверьте понимание

Как меняется достаточное n, если требуемую ε уменьшить вдвое при том же δ и диапазоне?

Вопросы к этой главе

Нужно ли знать истинную площадь?

Нет. Нужны независимость и доказанный диапазон индикаторов. Поэтому границу можно выбрать ещё до запуска, не вычисляя неизвестное среднее.

Можно ли использовать её для важностных весов?

Только если итоговые взвешенные вклады имеют известные конечные границы. Ограниченность самой исходной функции не гарантирует ограниченности после деления на малую плотность предложения.

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • Lafferty, Liu, Wasserman: concentration inequalities

    Прочитан раздел о неравенстве Хёффдинга для независимых ограниченных величин и масштабировании диапазона. Численный сертификат верхней границы получен из рациональной оценки экспоненты.

Две оценки на общей выборке: ошибка разности с ковариацией

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

Перед началом: Ожидание, дисперсия и ковариация; Независимые выборки и взвешенные средние.

Определение и постановка

Пусть нужно μ₁−μ₂. Один парный вклад D=Y₁−Y₂ имеет дисперсию VarY₁+VarY₂−2Cov(Y₁,Y₂). Маргинальные законы обоих выходов должны оставаться правильными.

Вывод и вычислительный критерий

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

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

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

Условия и границы вывода

Отрицательная ковариация здесь увеличивает дисперсию разности. Это противоположно цели антитетических пар, где усредняют два выхода с плюсом. Поэтому слово «зависимость» само по себе не определяет полезность приёма: сначала нужно выписать целевой линейный функционал.

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

Для случайных градиентов и сравнения политик эта идея сохраняется, но минимальная дисперсия зависит от выбранного совместного закона. Одна удачная короткая серия разностей не доказывает, что все будущие внешние режимы будут коррелировать положительно.

Для проверки общего генератора полезно отдельно выписать его совместную таблицу, а затем восстановить обе маргинали. Нужный знак ковариации не оправдывает изменение закона одного выхода. В нашем примере оба способа сохраняют распределения U и2U; меняется только способ соединения реализаций в пары.

Разобранная задача

Условие. Пусть U — честный бит, Y₁=U,Y₂=2U. Сравните дисперсию одного парного вклада разности с вариантом Y₁=U,Y₂=2V при независимом честном V.

  1. В обеих конструкциях средние равны1/2 и1, поэтому целевая разность равна−1/2.
  2. При общем U разность D=−U принимает0 и−1 равновероятно; её дисперсия1/4.
  3. При независимости VarU=1/4, Var(2V)=1; ковариация нулевая.
  4. Дисперсия независимой разности равна5/4, в пять раз больше парной.

Ответ. Общие случайные числа уменьшают дисперсию с5/4 до1/4 в этом примере.

Проверка. Четыре независимые пары(U,V) дают разности0,−2,1,−1. Их среднее−1/2 и прямой центральный второй момент5/4 подтверждают расчёт без ковариационной формулы.

Где легко ошибиться. Для разности нужна положительная связь выходов; механическое использование антитетических входов способно ухудшить сравнение.

Проверьте понимание

Какой знак ковариации уменьшает дисперсию Y₁−Y₂ при тех же маргинальных дисперсиях?

Вопросы к этой главе

Почему среднее не изменилось?

Линейность ожидания использует только отдельные законы Y₁ иY₂. Изменение их совместной зависимости меняет разброс разности, сохраняя оба средних.

По каким значениям считать MCSE?

По независимым парным разностям D₁,…,Dₘ. Умножение или сложение ошибок двух отдельно усреднённых столбцов должно учитывать их ковариацию.

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • Art Owen: Monte Carlo, chapter 8

    Веб-ридер дал timeout; PDF прочитан через urllib и pypdf. Проверены §8.2 антитетики, §8.4 стратификация и стоимость, §8.6 общие числа, §8.9 несколько контролей. Примеры и перекрёстная проверка собственные.

Случайный сдвиг регулярной сетки: несмещённость и зависимость точек

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

Перед началом: Условные вероятности и математическое ожидание; Частоты и поля таблицы.

Рандомизируется вся конструкция

Возьмём фиксированные точки a₁,…,aₙ на единичном торе и один равномерный сдвиг U. Точки Xᵢ=(aᵢ+U) mod 1 по отдельности равномерны. Поэтому Q=(1/n)Σf(Xᵢ) несмещённо оценивает интеграл любой интегрируемой f. Для этого аргумента независимость Xᵢ не нужна: достаточно правильного маргинального закона каждой точки.

Общий сдвиг сохраняет взаимное расположение точек. Произвольная реализация U не превращает сетку в n независимых наблюдений. При конечном втором моменте Var(Q) содержит все ковариации выходов. Их знак и величина зависят от функции и сетки; одно слово «регулярная» не гарантирует улучшение для каждого интегрируемого случая.

Два участка дают точный закон оценки

Для двух точек a₁=0,a₂=1/2 и функции f(x)=x при 0≤U<1/2 среднее равно U+1/4. При 1/2≤U<1 оно равно U−1/4. Оба участка отображаются на один интервал [1/4,3/4), а их вероятности по половине. Поэтому итоговая оценка равномерна на этом меньшем интервале.

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

Неопределённость оценивается между независимыми сдвигами

Повторите весь сеточный расчёт R≥2 раз с независимыми сдвигами Uᵣ. Тогда оценки Qᵣ независимы, и их выборочная дисперсия, делённая на R, несмещённо оценивает дисперсию среднего R сеточных оценок. Для этого вывода нужен конечный второй момент; он не даёт автоматически точный нормальный доверительный интервал при малом R.

Оценка разброса по отдельным f(Xᵢ) внутри одной сетки решает другой вопрос. Например, для f(x)=cos(4πx) обе точки дают одно значение, так что внутренняя выборочная дисперсия нулевая. Между сдвигами Q=cos(4πU) имеет дисперсию 1/2. Общая рандомизация способна оставить полностью невидимую внутри набора ошибку.

Две точки после одного сдвига

Условие. Пусть U равномерна на [0,1), X₁=U,X₂=(U+1/2) mod 1 и Q=(X₁+X₂)/2. Найдите Var(Q), сравните с двумя независимыми точками и с внутренней выборочной оценкой дисперсии среднего.

  1. На двух полуинтервалах Q равно U+1/4 и U−1/4. Поэтому Q равномерна на [1/4,3/4), её среднее равно 1/2.
  2. Длина итогового интервала равна 1/2, значит Var(Q)=(1/2)²/12=1/48. У двух независимых равномерных точек дисперсия среднего была бы 1/24.
  3. Две сеточные точки всегда различаются на 1/2. Их выборочная дисперсия с делителем n−1 равна (X₁−X₂)²/2=1/8.
  4. Наивное деление этого числа на n=2 даёт 1/16, втрое больше настоящей дисперсии 1/48. Это постоянная величина внутри данного двухточечного плана, но она оценивает не ту ковариационную структуру.

Ответ. Var(Q)=1/48; независимая пара дала бы 1/24, а ошибочная внутренняя оценка равна 1/16.

Проверка. Интегрирование квадратов двух линейных кусочных формул даёт E(Q²)=13/48; вычитание (EQ)²=1/4 возвращает 1/48. Это отдельная проверка найденного равномерного закона.

Где легко ошибиться. Несмещённость оценки интеграла и несмещённость оценки её дисперсии — разные свойства. Правильные равномерные законы точек обеспечивают первое, но не оправдывают IID-формулу стандартной ошибки.

Проверьте понимание

Какова точная дисперсия Q в указанном двухточечном плане для f(x)=x?

Вопросы к этой главе

Повтор того же сдвига создаёт независимую реплику?

Нет. При той же функции и сетке он буквально повторяет Q. Независимые реплики требуют новой независимой рандомизации всей конструкции.

Внутренняя ошибка всегда завышена?

Нет. Пример с cos(4πx) даёт нулевую внутреннюю ошибку при положительном межсдвиговом разбросе. Направление ошибки зависит от интегранта и структуры зависимостей.

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • Owen: Quasi-Monte Carlo Sampling, §1.7

    Прочитан индексированный авторский §1.7: общий сдвиг modulo one, правильные маргиналы и независимые повторные рандомизации. Прямой PDF был недоступен инструменту; кусочный пример и контрпример дисперсии составлены отдельно.

Случайное число имитаций: когда среднее остаётся несмещённым

Случайное число вычислений не обязательно смещает среднее. Решающее различие состоит в том, выбрали ли бюджет независимо от результатов или остановились после просмотра первых значений.

Перед началом: Условная вероятность; Точная арифметика.

Независимый бюджет допускает условное усреднение

Пусть Y₁,Y₂,… независимы и одинаково распределены, имеют среднее μ и дисперсию σ². Положительное целое N независимо от всей последовательности. При условии N=n обычное среднее имеет ожидание μ и дисперсию σ²/n. Поэтому безусловное среднее тоже несмещённо, а его дисперсия равна σ²E(1/N), если соответствующие моменты существуют. Замена E(1/N) на 1/EN вообще не точна: случайность знаменателя увеличивает значение по выпуклости.

Наблюдаемая остановка меняет состав записей

Если N определяется уже полученными Y, условный закон Y₁,…,Y_N при данном N не обязан быть исходным независимым законом. Например, ранняя остановка после большого первого результата чаще оставляет именно большие значения в коротких записях. Формула среднего фиксированного объёма под таким условием неприменима. Сохранение ожидания остановленной суммы при некоторых условиях также не означает сохранения ожидания суммы, поделённой на случайное N; отношение требует собственного анализа.

Как задавать воспроизводимый расчёт

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

Разобранная задача

Условие. Yi независимы Bernoulli(1/2). В плане A независимая монета выбирает N=1 или N=2 поровну. В плане B останавливаются при N=1, если Y₁=1, иначе берут N=2. Найдите ожидания средних.

  1. В плане A условное среднее равно 1/2 при любом N. Следовательно безусловное ожидание равно 1/2.
  2. В плане B ветвь Y₁=1 имеет вероятность 1/2 и среднее записи равно единице. Её вклад в ожидание равен 1/2.
  3. При Y₁=0 берут вторую попытку. Условное ожидаемое среднее равно E(Y₂/2)=1/4; вес этой ветви равен 1/2.
  4. Общее ожидание плана B равно 1/2+1/8=5/8. Оба плана имеют одинаковое распределение N и EN=3/2, но разные ожидания результата.

Ответ. Независимый бюджет даёт несмещённое среднее 1/2; остановка по первому успеху повышает ожидание до 5/8.

Проверка. Три конечные записи плана B имеют значения среднего 1,0,1/2 с вероятностями 1/2,1/4,1/4. Их прямая взвешенная сумма равна 5/8 и проверяет расчёт по условным ветвям.

Где легко ошибиться. Нельзя оценить корректность среднего только по распределению размера выборки. Зависимость размера от данных является частью плана, и два одинаковых распределения N могут давать разные смещения.

Проверьте понимание

Почему план B имеет смещение?

Вопросы к этой главе

Достаточно ли заранее ограничить N сверху?

Нет для несмещённости среднего. План B ограничен двумя попытками и всё равно смещён; ограниченная остановка суммы решает другую задачу.

Какая дисперсия у среднего плана A?

Она равна (1/4)[(1/2)·1+(1/2)·(1/2)]=3/16. Использование 1/(EN) дало бы 1/6, что не совпадает с точным значением.

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

Регенеративное Монте-Карло: ошибка отношения награды к длине цикла

Короткий и длинный циклы нельзя считать равными порциями времени. Правильный предел задаёт отношение средних награды и длины. Однако даже это правильное отношение сумм смещено при конечном числе циклов; его асимптотическая дисперсия определяется совместным законом двух величин.

Перед началом: Закон больших чисел и центральная предельная теорема; Линеаризация отношения двух выборочных средних.

Сначала определяют единицу наблюдения

Независимые одинаково распределённые полные регенерационные циклы с длиной T>0 и суммарной наградой R. Предполагаются конечные вторые моменты и начало наблюдения на границе цикла.

Регенерация означает, что после выбранного события будущее системы начинается заново с одним и тем же законом и независимо от предыдущих полных циклов. Поэтому пары (Tᵢ,Rᵢ) независимы между циклами. Внутри пары длина и награда обычно зависимы: длинный рабочий цикл способен накопить больше выпуска. Наличие нескольких возвращений само по себе независимости не доказывает.

Для m полных циклов оценка средней производительности равна μ̂ₘ=ΣRᵢ/ΣTᵢ. При E|R|<∞ и 0<ET<∞ закон больших чисел даёт предел μ=ER/ET. Среднее отдельных скоростей m⁻¹Σ(Rᵢ/Tᵢ) сходится к другой величине E(R/T). Оно взвешивает каждый цикл одинаково, хотя вопрос поставлен о времени.

Линеаризация сохраняет связь награды с длиной

Определим Zᵢ=Rᵢ−μTᵢ. Тогда EZ=0 и точно μ̂ₘ−μ=Z̄ₘ/T̄ₘ. Центральная предельная теорема для независимых Z и сходимость знаменателя дают √m(μ̂ₘ−μ)⇒N(0,v_c), где v_c=Var(R−μT)/(ET)². Раздельное сложение VarR и μ²VarT потеряет член −2μCov(R,T).

В практической оценке используют остатки Rᵢ−μ̂ₘTᵢ и их выборочную дисперсию, делённую на T̄ₘ². Стандартная ошибка имеет порядок √(v̂_c/m). Это большая выборочная аппроксимация по числу независимых циклов. Несколько миллионов записей внутри двух длинных циклов не превращаются в миллионы независимых наблюдений.

Счёт циклов и физическое время дают разные константы

Если горизонт измеряют временем t, число завершённых циклов примерно t/ET. Соответствующая временная дисперсионная константа равна v_t=Var(R−μT)/ET, то есть v_c·ET. Единицы измерения помогают заметить ошибку в знаменателе: переход от числа циклов к длительности не оставляет одну и ту же константу.

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

Два типа производственного цикла

Условие. Каждый независимый цикл с вероятностью 1/2 имеет (T,R)=(1,0), а с вероятностью 1/2 — (3,3). Найдите временную среднюю μ, точное среднее оценки после двух полных циклов и асимптотическую дисперсионную константу по числу циклов.

  1. Средние равны ET=2 и ER=3/2, поэтому μ=3/4. Среднее двух возможных индивидуальных скоростей равно 1/2 и отвечает другому вопросу.
  2. У двух циклов есть четыре равновероятные последовательности типов. Отношения сумм равны 0, 3/4, 3/4 и 1. Их среднее 5/8, то есть конечное смещение равно −1/8.
  3. Центрированная награда Z=R−(3/4)T принимает значения −3/4 и 3/4. Её среднее ноль, дисперсия 9/16.
  4. Следовательно v_c=(9/16)/2²=9/64. Для большого m дисперсия оценки приближённо 9/(64m). Это не точное равенство для m=2.
  5. Временная константа v_t=(9/16)/2=9/32. Она относится к нормировке √t, тогда как 9/64 относится к √m.

Ответ. μ=3/4; Eμ̂₂=5/8 со смещением −1/8; v_c=9/64, v_t=9/32.

Проверка. Прямое усреднение квадратов четырёх оценок даёт Eμ̂₂²=17/32, поэтому точная Var(μ̂₂)=17/32−25/64=9/64. Асимптотическая подстановка v_c/2 дала бы 9/128: на двух циклах она ещё не точна.

Где легко ошибиться. Нельзя усреднять скорости циклов вместо отношения суммарной награды к суммарному времени или объявлять предельную формулу точной дисперсией малой выборки.

Проверьте понимание

Чему равно точное Eμ̂₂ в примере статьи с двумя типами циклов?

Вопросы к этой главе

Почему независимость циклов не позволяет считать R и T независимыми?

Независимость относится к разным парам. Внутри одного цикла длительность и выпуск порождаются одной траекторией; их ковариация входит в Var(R−μT).

Можно ли включить незавершённый последний цикл как полный?

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

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • Kang, Shahabuddin, Whitt: Exploiting Regenerative Structure, §2

    Определяет независимые регенерационные циклы, отношение средних награды и длины и временную дисперсионную константу. Здесь отдельно выведена нормировка по числу циклов и точно перечислено конечное распределение своей двухтипной модели.

Случайное обрывание бесконечного ряда: несмещённость и цена хвоста

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

Перед началом: Абсолютная сходимость и перестановка сумм; Геометрический закон и второй момент.

Редкий дальний уровень получает обратный вес

Абсолютно сходящийся детерминированный ряд Σδₖ и независимый конечный целочисленный обрыв N с вероятностями выживания qₖ=P(N≥k)>0. В примере стоимость одного добавленного слагаемого равна единице.

Возьмём Z=Σₖ₌₀ᴺδₖ/qₖ. Для каждого k среднее индикатора 1{N≥k} равно qₖ, поэтому его взвешенное среднее равно единице. Условие Σ|δₖ|<∞ даёт EΣ|δₖ|1{N≥k}/qₖ=Σ|δₖ|<∞ и разрешает переставить сумму и ожидание. Получаем EZ=Σδₖ, хотя каждый запуск использует лишь конечное число слагаемых.

Условие qₖ>0 для всех потенциально ненулевых δₖ существенно. Жёсткий максимальный уровень с нулевым выживанием дальше него вернул бы исходное смещение. Если сами поправки случайны, независимость обрыва от всей последовательности и достаточная суммируемость абсолютных ожиданий позволяют провести похожее доказательство; произвольная зависимая остановка им не покрывается.

Второй момент помнит вложенность событий

Индикаторы выживания не независимы: при j>k событие N≥j уже включает N≥k. Поэтому E[1{N≥k}1{N≥j}]=qⱼ. Для неотрицательных поправок можно по Тонелли получить EZ²=Σₖ[δₖ²+2δₖΣⱼ₍ⱼ>ₖ₎δⱼ]/qₖ, разрешая и бесконечный результат. Для знакопеременных рядов перестановки второго момента требуют отдельного абсолютного контроля.

Положим δₖ=aᵏ при 0<a<1 и qₖ=rᵏ при 0<r<1. Тогда EZ=1/(1−a), а EZ²=[(1+a)/(1−a)]Σₖ(a²/r)ᵏ. Конечность второго момента эквивалентна r>a². Выживание, убывающее слишком быстро, делает обратные веса дальних уровней опасными, хотя среднее по-прежнему существует.

Цена хвоста и его ошибка проверяются раздельно

При единичной цене слагаемого работа W=N+1 и EW=Σqₖ=1/(1−r), конечная для любого r<1. Если цена уровня растёт, вместо этой суммы нужно использовать соответствующие приращения стоимости. Из конечного среднего N нельзя заключать конечную стоимость произвольного многоуровневого расчёта.

Небольшое r уменьшает обычный короткий запуск, но повышает редкие веса. Большое r заставляет чаще считать хвост и обычно стабилизирует оценку. Отчёт должен называть и закон N, и условия дисперсии: несколько спокойных запусков не проверяют существование второго момента. Усреднение независимых Z получает обычную стандартную ошибку только при нужной конечной дисперсии.

Ряд половин и геометрический обрыв

Условие. Оценивается Σₖ₌₀∞2⁻ᵏ=2. Сначала возьмите P(N≥k)=2⁻ᵏ, затем сравните с выживанием (1/8)ᵏ. Цена одного слагаемого единичная.

  1. В первом плане δₖ/qₖ=1, поэтому Z=N+1, где P(N=n)=2⁻ⁿ⁻¹. Каждый запуск возвращает положительное целое число.
  2. Несмещённость даёт EZ=2. Среднее число вычисленных слагаемых также EW=2, поскольку Z совпадает с W.
  3. При a=r=1/2 отношение a²/r=1/2. Второй момент равен 3/(1−1/2)=6, а дисперсия 6−4=2.
  4. Во втором плане r=1/8 средняя работа равна 1/(1−1/8)=8/7. Но a²/r=2, поэтому второй момент расходится. Ожидание оценки всё ещё равно 2.
  5. Для сравнения более тяжёлый хвост r=3/4 даёт EW=4, EZ²=9/2 и VarZ=1/2. Здесь оплачивается более длинный запуск ради меньшего разброса.

Ответ. При r=1/2 оценка несмещённа, EW=2 и VarZ=2. При r=1/8 EW=8/7, но дисперсия бесконечна; при r=3/4 она равна 1/2.

Проверка. В первом плане напрямую по геометрическому закону E(N+1)=2 и E(N+1)²=6. При r=1/8 уже диагональные вклады второго момента Σδₖ²/qₖ=Σ2ᵏ расходятся, что независимо подтверждает проблему без расчёта перекрёстных членов.

Где легко ошибиться. Конечная средняя длина запуска и точная несмещённость не доказывают конечной дисперсии. Проверьте второй момент до использования стандартной ошибки среднего.

Проверьте понимание

Что происходит при a=1/2 и r=1/8 в разобранном геометрическом примере статьи?

Вопросы к этой главе

Почему нельзя ограничить N большим числом ради безопасности?

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

Гарантирует ли случайный обрыв меньшую ошибку, чем фиксированный?

Нет. Он меняет компромисс смещения, дисперсии и работы. Несмещённость сама по себе не гарантирует меньшую среднеквадратичную ошибку при конкретном бюджете.

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • Rhee, Glynn: Unbiased Estimation with Square Root Convergence for SDE Models, §2

    Развивает несмещённые оценки со случайным последним уровнем и условия их второго момента. Здесь детерминированный геометрический ряд позволяет отдельно вывести все условия и сравнить три закона обрыва без предположений о численной схеме СДУ.

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться