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

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

Для описания асимптотических оценок имеется система нотаций:

§ Говорят, что f(n)=O (g(n)), если существует такая константа c>0 и такое число n0, что выполняется условие 0≤f(n)≤c*g(n) для всех n≥n0. Более формально:

(()) { () | 0, } 0 0 O g n = f n $c > $n "n > n £ f n £ cg n

O (g(n)) используется для указания функций, которые не более чем в постоянное число раз превосходят g(n), этот вариант используется для описания оценок сверху (в смысле «не хуже чем»). Когда речь идет о конкретном алгоритме решения конкретной задачи, то целью анализа временной сложности этого алгоритма является получение оценки для времени в худшем или в среднем, обычно асимптотической оценки сверху O (g(n)), при возможности – и асимптотической оценки снизу W(g(n)), а еще лучше - асимптотически точной оценки Q(g(n)).

Но при этом остается вопрос – а могут ли быть для этой задачи алгоритмы решения еще лучше? Этот вопрос ставит задачу о нахождении нижней оценки временной сложности для самой задачи (по всем возможным алгоритмам ее решения, а не для одного из известных алгоритмов ее решения). Вопрос получения нетривиальных нижних оценок очень сложный. На сегодняшний день имеется не так уж много таких результатов, но для некоторых ограниченных моделей вычислителей доказаны нетривиальные нижние оценки, и некоторые из них играют важную роль в практическом программировании. Одной из задач, для которых известна нижняя оценка временной сложности, является задача сортировки:

§ Дана последовательность из n элементов a1,a2,... an, выбранных из множества, на котором задан линейный порядок.

§ Требуется найти перестановку p этих n элементов, которая отобразит данную последовательность в неубывающую последовательность ap(1),ap(2),... ap(n), т.е. ap(i)≤ap(i+1) при 1≤iметод сведения . Пусть у нас есть две задачи A и B, которые связаны так, что задачу A можно решить следующим образом:

1) Исходные данные к задаче A преобразуются в соответствующие исходные

данные для задачи B.

2) Решается задача B.

3) Результат решения задачи B преобразуется в правильное решение задачи A .__ В этом случае мы говорим, что задача A сводима к задаче B. Если шаги (1) и (3) вышеприведенного сведения можно выполнить за время O (t(n)), где, как обычно, n – 25 «объем» задачи A , то скажем, что A t(n)-сводима к B, и запишем это так: A μt(n) B. Вообще говоря, сводимость не симметричное отношение, в частном случае, когда A и B взаимно сводимы, мы назовем их эквивалентными. Следующие два самоочевидных утверждения характеризуют мощь метода сведения в предположении, что это сведение сохраняет порядок «объема» задачи.

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

, «о малое от » обозначает «бесконечно малое относительно » [ , пренебрежимо малую величину при рассмотрении. Смысл термина «О большое» зависит от его области применения, но всегда растёт не быстрее, чем, «O большое от » (точные определения приведены ниже).

В частности:

Продолжение 7

фраза «сложность алгоритма есть » означает, что с увеличением параметра, характеризующего количество входной информации алгоритма, время работы алгоритма не может быть ограничено величиной, которая растет медленнее, чем n !;

фраза «функция является „о“ малым от функции в окрестности точки » означает, что с приближением к уменьшается быстрее, чем (отношение стремится к нулю).

Правило суммы : Пусть конечное множество M разбито на два непересекающихся подмножества M 1 и M 2 (в объединении дающих все множество М). Тогда мощность |M| = |M 1 | + |M 2 |.

Правило произведения : Пусть в некотором множестве объект а может быть выбран n способами, и после этого (то есть после выбора объекта а) объект b может быть выбран m способами. Тогда объект ab может быть выбран n*m способами.

Замечание : Оба правила допускают индуктивное обобщение. Если конечное множество М допускает разбиение на r попарно непересекающихся подмножеств M 1 , M 2 ,…,M r , то мощность |M| = |M 1 |+|M 2 |+…+|M r |. Если объект A 1 может быть выбран k 1 способами, затем (после выбора объекта A 1) объект A 2 может быть выбран k 2 способами, и так далее и наконец, объект AR может быть выбран kr способами, то объект А 1 А 2 …А r может быть выбран k 1 k 2 …k r способами.

Как отмечено в предыдущем разделе, изучение классических алгоритмов во многих случаях может быть проведено с помощью асимптотических методов математической статистики, в частности, с помощью ЦПТ и методов наследования сходимости . Отрыв классической математической статистики от нужд прикладных исследований проявился, в частности, в том, что в распространенных монографиях недостает математического аппарата, необходимого, в частности, для изучения двухвыборочных статистик. Суть в том, что переходить к пределу приходится не по одному параметру, а по двум – объемам двух выборок. Пришлось разработать соответствующую теорию – теорию наследования сходимости, изложенную в нашей монографии .

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

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

При первом подходе получаем гарантированный результат, но "цена" этого результата может быть излишне высокой. В качестве примера укажем на универсальное неравенство Берри-Эссеена для погрешности в ЦПТ . Совершенно справедливо подчеркивает А.А. Боровков , что "скорость сходимости в реальных задачах, как правило, оказывается лучше."

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

Одна из ложных идей - использование при анализе возможных отклонений только какого-либо конкретного параметрического семейства – распределений Вейбулла-Гнеденко, трехпараметрического семейства гамма - распределений и др. Еще в 1927 г. акад. АН СССР С.Н. Бернштейн обсуждал методологическую ошибку, состоящую в сведении всех эмпирических распределений к четырехпараметрическому семейству Пирсона . Однако и до сих пор параметрические методы статистики весьма популярны, особенно среди прикладников, и вина за это заблуждение лежит прежде всего на преподавателях статистических методов (см. ниже, а также статью ).

15. Выбор одного из многих критериев для проверки конкретной гипотезы

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

В качестве примера рассмотрим задачу проверки однородности двух независимых выборок. Как известно , для ее решения можно предложить массу критериев: Стьюдента, Крамера-Уэлча, Лорда, хи - квадрат, Вилкоксона (Манна-Уитни), Ван – дер - Вардена, Сэвиджа, Н.В.Смирнова, типа омега-квадрат (Лемана-Розенблатта), Г.В.Мартынова и др. Какой выбрать?

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

Распространено, особенно среди математиков, ложное и вредное мнение о необходимости поиска оптимальных методов, решений и т.д. Дело в том, что оптимальность обычно исчезает при отклонении от исходных предпосылок. Так, среднее арифметическое в качестве оценки математического ожидания является оптимальной только тогда, когда исходное распределение - нормальное , в то время как состоятельной оценкой - всегда, лишь бы математическое ожидание существовало. С другой стороны, для любого произвольно взятого метода оценивания или проверки гипотез обычно можно так сформулировать понятие оптимальности, чтобы рассматриваемый метод стал оптимальным – с этой специально выбранной точки зрения. Возьмем, например, выборочную медиану как оценку математического ожидания. Она, разумеется, оптимальна, хотя и в другом смысле, чем среднее арифметическое (оптимальное для нормального распределения). А именно, для распределения Лапласа выборочная медиана является оценкой максимального правдоподобия, а потому оптимальной (в смысле, уточненном в монографии ).

Критерии однородности были проанализированы в монографии . Естественных подходов к сравнению критериев несколько - на основе асимптотической относительной эффективности по Бахадуру, Ходжесу-Леману, Питмену. И выяснилось, что каждый критерий является оптимальным при соответствующей альтернативе или подходящем распределении на множестве альтернатив. При этом математические выкладки обычно используют альтернативу сдвига, сравнительно редко встречающуюся в практике анализа реальных статистических данных (в связи с критерием Вилкоксона эта альтернатива обсуждалась и критиковалась нами в ). Итог печален - блестящая математическая техника, продемонстрированная в , не позволяет дать рекомендации для выбора критерия проверки однородности при анализе реальных данных. Другими словами, с точки зрения работы прикладника, т.е. анализа конкретных данных, монография бесполезна. Блестящее владение математикой и огромное трудолюбие, продемонстрированные автором этой монографии, увы, ничего не принесли практике.

Конечно, каждый практически работающий статистик так или иначе решает для себя проблему выбора статистического критерия. На основе ряда методологических соображений мы остановили свой выбор на состоятельном против любой альтернативы критерии типа омега-квадрат (Лемана-Розенблатта). Однако остается чувство неудовлетворенности в связи с недостаточной обоснованностью этого выбора.

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

? Сколько общих точек может быть у линии второго порядка и прямой асимптотического направления относительно этой линии?

В общей теории линий второго порядка доказывается, что если

То ненулевой вектор ( задаёт асимптотическое направление относительно линии

(общий критерий асимптотического направления ).

Для линий второго порядка

если , то нет асимптотических направлений,

если то существует два асимптотических направления,

если то существует только одно асимптотическое направление.

Полезной оказывается следующая лемма (критерий асимптотического направления линии параболического типа ).

Лемма . Пусть - линия параболического типа.

Ненулевой вектор имеет асимптотическое направление

относительно . (5)

(Задача. Доказать лемму.)

Определение . Прямая асимптотического направления называется асимптотой линии второго порядка, если эта прямая либо не пересекается с , либо содержится в ней.

Теорема . Если имеет асимптотическое направление относительно , то асимптота, параллельная вектору , определяется уравнением

Заполняем таблицу.

ЗАДАЧИ .

1. Найти векторы асимптотических направлений для следующих линий второго поря дка:

4 - гиперболического типа два асимптотических направления.

Воспользуемся критерием асимптотического направления:

Имеет асимптотическое направление относительно данной линии 4 .

Если =0, то =0, то есть - нулевой. Тогда Поделим на Получаем квадратное уравнение: , где t = . Решаем это квадратное уравнение и находим два решения: t = 4 и t = 1. Тогда асимптотические направления линии .

(Можно рассмотреть два способа, так как линия – параболического типа.)

2. Выясните, имеют ли оси координат асимптотические направления относительно линий второго порядка:

3. Напишите общее уравнение линии второго порядка, для которой

а) ось абсцисс имеет асимптотическое направление;

б) Обе оси координат имеют асимптотические направления;

в) оси координат имеют асимптотические направления и О – центр линии.

4. Напишите уравнения асимптот для линий:

а) ng w:val="EN-US"/>y=0"> ;

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

Указание: Так как есть две непараллельные асимптоты, то существует два асимптотических направления, тогда , а, значит, линия – центральная.

Запишите уравнения асимптот в общем виде и систему для нахождения центра. Всё очевидно.

6.(№920) Напишите уравнение гиперболы, проходящей через точку А(0, -5) и имеющей асимптоты х – 1 = 0 и 2х – y + 1 = 0.

Указание . Воспользуйтесь утверждением предыдущей задачи.

Домашнее задание . , №915(в,д,е), №916 (в,г,д), №920 (если не успели);

Шпаргалки;

Силаев, Тимошенко. Практические задания по геометрии,

1 семестр. С.67, вопросы 1-8, с.70, вопросы 1-3 (устно).

ДИАМЕТРЫ ЛИНИИ ВТОРОГО ПОРЯДКА.

СОПРЯЖЕННЫЕ ДИАМЕТРЫ.

Дана аффинная система координат .

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

На лекции доказано, что диаметр – это прямая и получено её уравнение

Рекомендации : Показать (на эллипсе), как строится (задаём не асимптотическое направление; проводим [две] прямые этого направления, пересекающие линию; находим середины отсекаемых хорд; проводим через середины прямую – это и есть диаметр).

Обсудить:

1. Почему в определении диаметра берётся вектор не асимптотического направления. Если не могут ответить, то попросите построить диаметр, например, для параболы.

2. Любая ли линия второго порядка имеет хотя бы один диаметр? Почему?

3. На лекции доказано, что диаметр – это прямая. Серединой какой хорды является точка М на рисунке?

4. Посмотрите на скобки в уравнении (7). Что они напоминают?

Вывод: 1) каждый центр принадлежит каждому диаметру;

2) если существует прямая центров, то существует единственный диаметр.

5. Какое направление имеют диаметры линии параболического типа? (Асимптотическое)

Доказательство (наверно, на лекции).

Пусть диаметр d, заданный уравнением (7`) сопряжен вектору не асимптотического направления. Тогда его направляющий вектор

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

6. Сколько диаметров у параболы? Их взаимное расположение? Сколько диаметров у остальных линий параболического типа? Почему?

7. Как построить общий диаметр некоторых пар линий второго порядка (см. вопросы 30, 31 далее).

8. Заполняем таблицу, обязательно делаем рисунки.

1. . Напишите уравнение множества середин всех хорд, параллельных вектору

2. Напишите уравнение диаметра d, проходящего через точку К(1,-2) для линии .

Этапы решения :

1-й способ .

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

В данном случае линия центральная, тогда все диаметры проходят через центр С.

2. Составляем уравнение прямой, проходящей через две точки К и С. Это и есть искомый диаметр.

2-й способ .

1. Записываем уравнение диаметра d в виде (7`).

2. Подставив в это уравнение координаты точки К, находим зависимость между координатами вектора, сопряженного диаметру d.

3. Задаём этот вектор, учитывая найденную зависимость, и составляем уравнение диаметра d.

В данной задаче вычислять проще вторым способом.

3. . Напишите уравнение диаметра, параллельного оси абсцисс.

4. Найдите середину хорды, отсекаемой линией

на прямой x + 3y – 12 =0.

Указание к решению : Конечно, можно найти точки пересечения данных прямой и линии , а затем – середину полученного отрезка. Желание сделать так отпадает, если взять, к примеру, прямую с уравнением х +3у – 2009 =0.

Exact Tests provides two additional methods for calculating significance levels for the statistics available through the Crosstabs and Nonparametric Tests procedures. These methods, the exact and Monte Carlo methods, provide a means for obtaining accurate results when your data fail to meet any of the underlying assumptions necessary for reliable results using the standard asymptotic method. Available only if you have purchased the Exact Tests Options.

Example. Asymptotic results obtained from small datasets or sparse or unbalanced tables can be misleading. Exact tests enable you to obtain an accurate significance level without relying on assumptions that might not be met by your data. For example, results of an entrance exam for 20 fire fighters in a small township show that all five white applicants received a pass result, whereas the results for Black, Asian and Hispanic applicants are mixed. A Pearson chi-square testing the null hypothesis that results are independent of race produces an asymptotic significance level of 0.07. This result leads to the conclusion that exam results are independent of the race of the examinee. However, because the data contain only 20 cases and the cells have expected frequencies of less than 5, this result is not trustworthy. The exact significance of the Pearson chi-square is 0.04, which leads to the opposite conclusion. Based on the exact significance, you would conclude that exam results and race of the examinee are related. This demonstrates the importance of obtaining exact results when the assumptions of the asymptotic method cannot be met. The exact significance is always reliable, regardless of the size, distribution, sparseness, or balance of the data.

Statistics. Asymptotic significance. Monte Carlo approximation with confidence level, or exact significance.

• Asymptotic . The significance level based on the asymptotic distribution of a test statistic. Typically, a value of less than 0.05 is considered significant. The asymptotic significance is based on the assumption that the data set is large. If the data set is small or poorly distributed, this may not be a good indication of significance.
• Monte Carlo Estimate . An unbiased estimate of the exact significance level, calculated by repeatedly sampling from a reference set of tables with the same dimensions and row and column margins as the observed table. The Monte Carlo method allows you to estimate exact significance without relying on the assumptions required for the asymptotic method. This method is most useful when the data set is too large to compute exact significance, but the data do not meet the assumptions of the asymptotic method.
• Exact . The probability of the observed outcome or an outcome more extreme is calculated exactly. Typically, a significance level less than 0.05 is considered significant, indicating that there is some relationship between the row and column variables.