Анализ проблем комбинаторики и теории вероятности

1. Событие — то, что имеет место, происходит, наступает в произвольной точке пространства-времени; значительное происшествие, явление или иная деятельность как факт общественной или личной жизни; подмножество исходов эксперимента.

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

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

Вероятность события — это численное мера объективной возможности этого события (интуитивное определение вероятности) Вероятность события, А сказывается Р (А) Если осуществлять различные испытания, то можно констатировать, что различные случайные события могут иметь разную вероятность появления.

2. Комбинаторика — это раздел математики, изучающий задачи о расположении или выборе элементов из множеств.

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

Различают три основных типа соединений: размещения, перестановки и сочетания.

В комбинаторике перестановка — это упорядоченный набор чисел обычно трактуемый как биекция на множестве, которая числу i ставит в соответствие i-й элемент из набора. Число n при этом называется порядком перестановки. Как синоним слову «перестановка» в этом смысле некоторые авторы используют слово расстановка.

В теории групп под перестановкой произвольного множества подразумевается биекция этого множества на себя. Как синоним слову «перестановка» в этом смысле некоторые авторы используют слово подстановка. (Другие авторы подстановкой называют наглядный способ записи перестановки.

Число всех сочетаний без повторений по m из n элементов обозначается .

Буква C от французского «combinaison» («сочетание»).

Теорема.

.

Доказательство. Каждое размещение без повторений (x₁,…,x_m) по m из n можно построить в 2 шага: вначале строится сочетание без повторений {x₁,…,x_m} по mиз n, а затем — перестановка (x₁,…,x_m) из m элементов множества {x₁,…,x_m}. По правилу произведения.

Из теоремы и формул для числа размещений без повторений следуют еще 2 формулы для числа сочетаний без повторений:

.

.

3. Теорема умножения вероятностей.

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

P (AB) = P (A)ЧP (B/A) = P (B)ЧP (A/B).

Произведению событий и благоприятствуют только те исходы, которые благоприятствуют и событию и событию одновременно, т. е. исходов. Поэтому вероятность произведения событий и равна.

.

Умножим числитель и знаменатель этой дроби на. Получим.

.

Аналогично доказывается и формула.

.

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

Пример. Поступление в магазин одного вида товара — событие. Поступление второго вида товара — событие. Поступить эти товары могут и одновременно. Поэтому и — совместные события.

Теорема. Вероятность появления хотя бы одного из двух совместных событий равна сумме вероятностей этих событий без вероятности их совместного появления.

P (A+B) = P (A) + P (B) — P (AB). (2.5).

Доказательство. Событие наступит, если наступит одно из трех несовместных событий,. По теореме сложения вероятностей несовместных событий имеем.

(2.6).

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

(2.7).

Аналогично для события Откуда.

.(2.8).

Подставив (2.7) и (2.8) в (2.6), находим.

P (A+B) = P (A) + P (B) — P (AB).

Формула полной вероятности. Формула Байеса.

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

.

где — вероятность -ой гипотезы, а — условная вероятность события при осуществлении данной гипотезы.

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

.

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

5. Формула Бернулли — формула в теории вероятностей, позволяющая находить вероятность появления события при независимых испытаниях. Формула Бернулли позволяет избавиться от большого числа вычислений — сложения и умножения вероятностей — при достаточно большом количестве испытаний. Названа в честь выдающегося швейцарского математика Якоба Бернулли, который вывел эту формулу.

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

Оказывается можно точно подсчитать число «удачных» комбинаций исходов испытаний, для которых событие наступает раз в независимых испытаниях, — в точности это количество сочетаний из по :

.

В то же время, так как все испытания независимы и их исходы несовместимы (событие либо наступает, либо нет), то вероятность получения «удачной» комбинации в точности равна: .

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

.

Последнее выражение есть не что иное, как Формула Бернулли. Полезно также заметить, что в силу полноты группы событий, будет справедливо:

.

Теорема Пуассона. При неограниченном увеличении числа n независимых испытаний в каждом из которых может наступить некоторое событие с одной и той же вероятностью стремящейся к нулю при этом вероятность того, что событие наступит m, приближенно равна:

(3.22).

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

находят в таблице, приведенной в приложении 3, на пересечении соответствующих значений и .

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

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

Функция распределения в теории вероятностей — функция, характеризующая распределение случайной величины или случайного вектора; Вероятность того, что случайная величина X примет значение, меньшее или равное х, где х — произвольное действительное число. При соблюдении известных условий полностью определяет случайную величину.

7. Математическое ожидание дискретной случайной величины есть сумма произведений всех её возможных значений на их вероятности:

M (X) = x₁p₁ + x₂p₂ +… + x_np_n

Свойства математического ожидания.

1) Математическое ожидание постоянной величины равно самой величине:

М© = С.

2) Постоянный множитель можно выносить за знак математического ожидания:

М (СХ) = С· М (Х).

3) Математическое ожидание суммы случайных величин равно сумме математических ожиданий слагаемых:

М (Х₁ + Х₂ + …+ Х_n) = М (Х₁) + М (Х₂) +… + М (Х_n).

4) Математическое ожидание произведения взаимно независимых случайных величин равно произведению математических ожиданий сомножителей:

М (Х₁ · Х₂ · … · Х_n) = М (Х₁) · М (Х₂) · … · М (Х_n).

Дисперсия дискретной случайной величины есть математическое ожидание квадрата отклонения случайной величины от её математического ожидания:

D (X) = (x₁ — M (X))²p₁ + (x₂ — M (X))²p₂ +… + (x_n— M (X))²p_n = x²₁p₁ + x²₂p₂ +… + x²_np_n — [M (X)]²

Свойства дисперсии.

• 1) Дисперсия постоянной величины равна нулю: D© = 0
• 2) Постоянный множитель можно выносить за знак дисперсии, предварительно возведя его в квадрат:

D (СХ) = С² · D (Х).

3) Дисперсия суммы (разности) независимых случайных величин равна сумме дисперсий слагаемых.

D (Х₁ ± Х₂ ±… ± Х_n) = D (Х₁) + D (Х₂) +… + D (Х_n).

8. Часто результат опыта описывается не одной случайной величиной X, а несколькими случайными величинами: Х1, Х2, …, Хп. В этом случае принято говорить, что указанные случайные величины образуют систему (Х1, Х2, …, Хп).

Систему двух случайных величин (Х, Y) можно изобразить случайной точкой на плоскости.

Событие, состоящее в попадании случайной точки (X; Y) в область D, принято обозначать в виде (X; Y) М D.

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

М(ХY) = М(Х) Ч М(Y); С_ху = 0.

Для характеристики связи между величинами Х и Y рассматривается так называемый коэффициент корреляции

являющийся безразмерной величиной.

Если случайные величины Х и Y независимы, то r_xy = 0. Если же случайные величины Х и Y связаны точной линейной зависимостью то т. е. r_xy = 1 при а > 0 и r_xy = -1 при, а < 0.

Вообще же коэффициент корреляции удовлетворяет условию ;

9. Неравенство Чебышёва, известное также как неравенство Биенэме — Чебышёва, это распространённое неравенство из теории меры и теории вероятностей. Оно было первый раз получено Бьенеме в 1853 году, и позже также Чебышёвым. Неравенство, использующееся в теории меры, является более общим, в теории вероятностей используется его следствие.

Так как события и взаимно противоположны, то и лемма Чебышёва может быть также представлена в виде.

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

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

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

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

10. Выборка или выборочная совокупность — часть генеральной совокупности элементов, которая охватывается экспериментом (наблюдением, опросом).

Характеристики выборки:

Качественная характеристика выборки — что именно мы выбираем и какие способы построения выборки мы для этого используем;

Количественная характеристика выборки — сколько случаев выбираем, другими словами объём выборки.

Необходимость выборки:

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

Существует необходимость в сборе первичной информации.

Частота — физическая величина, характеристика периодического процесса, равна количеству повторений или возникновения событий (процессов) в единицу времени. Рассчитывается, как отношение количества повторений или возникновения событий (процессов) к промежутку времени, за которое они совершены^[1]. Стандартные обозначения в формулах — н, f или F.

Единицей измерения частоты в Международной системе единиц (СИ) является герц (русское обозначение: Гц; международное: Hz), названный в честь немецкого физика Генриха Герца.

Частота обратно пропорциональна периоду колебаний: н = 1/T.

Вариационные ряды и их характеристика Обычно полученные наблюдаемые данные представляют собой множество расположенных в беспорядке чисел.

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

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

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

Порядковый номер варианта (значения признака) называется рангом: x₁-1-й вариант (1-е значение признака), x₂ — 2-й вариант (2-е значение признака), x_i — i-й вариант (iе значение признака).

Определение. Численность отдельной группы сгруппированного ряда наблюдаемых данных называется частотой или весом соответствующего варианта и обозначается n_i, где i — индекс варианта.

Частота (n_i) показывает, сколько раз встречается тот или иной вариант (значение признака) в статистической совокупности.

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

где k — число вариантов.

Частость или относительная частота (w_i) показывает, какая часть единиц совокупности имеет тот или иной вариант. Нетрудно заметить, что частость w_i является статистической вероятностью появления варианта.

Сумма всех частостей равна 1:

Вариационные ряды бывают дискретными и интервальными.

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

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

Таблица 1.

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

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

Интервальные вариационные ряды строят обычно в том случае, если значения изучаемого признака могут отличаться друг от друга на сколь угодно малую величину. Значения признака в них задаются в виде интервалов. Общий вид интервального вариационного ряда показан в табл. 2, где i = 1,2,…, k.

Таблица 2.

В интервальных вариационных рядах в каждом интервале выделяют верхнюю и нижнюю границы. Разность между верхней и нижней границами интервала называется интервальной разностью или размахом вариации R.

.

Чтобы ряд не был громоздким, обычно число интервалов берут от 7 до 11. Для более точного определения величины частичного интервала можно воспользоваться формулой Стерджеса:

.

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

Определение. Если интервалы в вариационном ряде имеют одинаковую длину (интервальную разность), их называют равновеликими, в противном случае — неравновеликими.

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

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

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

,

где — число, меньших ; — объем выборки.

Из теоремы Бернулли следует, что при достаточно большом объеме выборки функции и мало отличаются друг от друга. Отличие эмпирической функции распределения от теоретической состоит в том, что теоретическая функция распределения определяет вероятность события, а эмпирическая функция определяет относительную частоту этого же события.

Эмпирическая функция распределения обладает всеми свойствами интегральной функции распределения:

• 1) значения эмпирической функции распределения принадлежат отрезку; комбинаторика вероятность вариационный распределение
• 2) — неубывающая функция;
• 3) если — наименьшая варианта, то при; если — наибольшая варианта, то при .

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

В качестве примера можно привести гистограмму для ошибки наводки, построенную по данным статистического ряда, рассмотренного в примере 1 (рис. 7.3.1).

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

Эмпирической функцией распределения (функцией распределения выборки) называют функцию, определяющую для каждого значения x относительную частоту события X.

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

При росте n относительная частота события X.

.

Свойства эмпирической функции распределения

Значения эмпирической функции принадлежат отрезку [0,1].

— неубывающая функция.

Если — наименьшая варианта, то =0 при ,.

если — наибольшая варианта, то =1 при .

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

Гистограмма (от др. греч? уфьт— столб + гсЬммб — черта, буква, написание) — способ графического представления табличных данных.

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

12. Точечная оценка в математической статистике — это число, оцениваемое на основе наблюдений, предположительно близкое к оцениваемому параметру.

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

.

где обозначает математическое ожидание в предположении, что — истинное значение параметра (распределения выборки).

• · Оценка называется эффективной, если она обладает минимальной дисперсией среди всех возможных несмещенных точечных оценок.
• · Оценка называется состоятельной, если она по вероятности с увеличением объема выборки n стремится к параметру генеральной совокупности: ,

по вероятности при .

· Оценка называется сильно состоятельной, если ,.

почти наверное при .

Надо отметить, что проверить на опыте сходимость «почти наверное» не представляется возможным, поэтому с точки зрения прикладной статистики имеет смысл говорить только о сходимости по вероятности.

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

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

· Выборочное среднее — несмещённая оценка теоретического среднего:

.

· Выборочное среднее — сильно состоятельная оценка теоретического среднего:

почти наверное при .

· Выборочное среднее — асимптотически нормальная оценка. Пусть дисперсия случайных величин конечна и ненулевая, то есть. Тогда.

по распределению при ,.

где — нормальное распределение со средним и дисперсией .

· Выборочное среднее из нормальной выборки — эффективная оценка её среднего.

Выборочная дисперсия в математической статистике — это оценка теоретической дисперсии распределения, рассчитанная на основе данных выборки. Виды выборочных дисперсий:

• · смещённая;
• · несмещённая или исправленная.

Свойства выборочных дисперсий Выборочная дисперсия является теоретической дисперсией выборочного распределения. Более точно, пусть — выборочная функция распределения данной выборки. Тогда для любого фиксированного функция является (неслучайной) функцией дискретного распределения. Дисперсия этого распределения равна .

· Обе выборочные дисперсии являются состоятельными оценками теоретической дисперсии. Если, то И.

.

где символ «» обозначает сходимость по вероятности.

· Выборочная дисперсия является смещённой оценкой теоретической дисперсии, а исправленная выборочная дисперсия — несмещённой:

.

И.

.

· Выборочная дисперсия нормального распределения имеет распределение хи-квадрат. Пусть. Тогда.

.

Определения Пусть — выборка из распределения вероятности. Тогда.

· выборочная дисперсия — это случайная величина.

.

где символ обозначает выборочное среднее;

· несмещённая (исправленная) дисперсия — это случайная величина.

.