Центральная предельная теорема простым языком. Расширения модулей Python и параллельное программирование с Си. Обучение на основе моделирования: почему модели

Python для обучения научной информатике: Моделирование систем массового обслуживания

• Перевод
• Tutorial

Аннотация

1. Ввведение и предистория

1.1. Научная информатика

1.2. Конструктивизм в обучении

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

1.3. Обучение на основе моделирования: почему модели?

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

Лерер и Шаубле заостряют внимание на экспериментах с различными представлениями модели: “Обучение студента усиливается, когда у студента есть возможность создания и пересмотра нескольких вариантов моделей, а затем сравнения адекватности описания этих различных моделей”.

1.4. Научная информатика в основе образования: эксперименты с моделями

1.5. Стохастическое моделирование систем массового обслуживания

1.6. Python в образовании, основанном на научной информатике

2. Основы

2.1. Случайные величины и распределения

Задача этих вводных экспериментов является довольно сложной. Мы не только рассмотрим вероятностные распределения, но также затронем моделирование и параллельные вычисления. Мы также сделаем один шаг вперёд в научном исследовании: экспериментально докажем Центральную Предельную Теорему.

Мы начнём с генерации случайных чисел (не затрагивая распределения). Затем объясним равномерно распределённые случайные величины. Обсуждения об истинной случайности и квази случайности представлены авторами . Для продвинутых учеников будет представлен ряд экспериментов с генератором псевдослучайных величин Python. На начальном этапе, для наглядности изучения, будем повышать количество испытаний, наблюдая результат моделирования. На последующем этапе мы перейдём к более сложным экспериментам и параллельным вычислениям. Будем использовать для моделирования модуль случайных величин Python, а для параллельных вычислений - библиотеку mpi4py. Модуль случайных величин Python основан на псевдослучайном генераторе чисел для различных распределений. Для примера: random.randint(a,b) возвращает случайное целое число N, где a ≤ N ≤ b и random.expovariate(lambd) возвращает экспоненциально распределенные случайные величины с параметром ‘lambd’. Для получения более подробной информации обратитесь к документации Python. Программирование модели подбрасывания кубика представлено на рис.2.

Import pylab import random number_of_trials =100 ## Here we simulate the repeated throwing of a single six-sided die list_of_values = for i in range(number_of_trials): list_of_values.append(random.randint(1,6)) print "Trials =", number_of_trials, "times." print "Mean =", pylab.mean(list_of_values) print "Standard deviation =", pylab.std(list_of_values) pylab.hist(list_of_values, bins=) pylab.xlabel("Value") pylab.ylabel("Number of times") pylab.show()
Рис. 2. Программирование модели подбрасывания одного кубика на Python

Результаты моделирования подбрасывания одного кубика представлены на рисунке 3.

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

List_of_values.append(random.randint(1, 6) + random.randint(1, 6)) ... pylab.hist(list_of_values, pylab.arange(1.5, 13.5, 1.0)) ...
Результат вычислений в случае двух кубиков представлен на рисунке 5.

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

List_of_values.append(random.normalvariate(7, 2.4)) ...
Результаты моделирования для нормального распределения представлены на рисунке 6.

Финальным шагом является демонстрация экспоненциального распределения. Экспоненциальное распределение используется для моделирования распределения (длительности) интервалов между моментами поступления требований в системах разного типа. Результаты их моделирования представлены на рис 7 и 8.

Import pylab import random number_of_trials = 1000 number_of_customer_per_hour = 10 ## Here we simulate the interarrival time of the customers list_of_values = for i in range(number of trials): list_of_values.append(random.expovariate(number_of_customer_per_hour)) mean=pylab.mean(list_of_values) std=pylab.std(list_of_values) print "Trials =", number_of_trials, "times" print "Mean =", mean print "Standard deviation =", std pylab.hist(list_of_values,20) pylab.xlabel("Value") pylab.ylabel("Number of times") pylab.show()
Рис. 7. Модель Python для экспоненциального распределения

2.2. Стохастическое моделирование

Здесь учащийся должен провести определённое количество экспериментов используя эту простую модель путём увеличения количества испытаний. За счёт увеличения числа кубиков и числа испытаний, учащийся столкнётся с относительно долгим временем вычисления. Это прекрасный повод для использования параллельных вычислений. Модель Python для нескольких игральных кубиков представлена на рисунке 9. И результаты моделирования представлены на рисунке 10. Следующим шагом будет рассмотрение более общих вопросов, связанных с различными системами массового обслуживания. Краткое введение в классификацию СМО представлено в следующей части этой статьи. Начнём изучение с системы М/М/1 системы и более сложных систем массового обслуживания. Основные понятия стохастических процессов будут подробно освещены в этой части статьи. В качестве возможного примера можно предложить задачу исследования выходного потока. Докажем, что вывод М/М/1 системы является Пуассоновским потоком. Таким образом собранные данные будут представлены в виде построенной выходной эмпирической гистограммы.

Import pylab import random number_of_trials = 150000 number_of_dice = 200 ## Here we simulate the repeated throwing ## of a number of single six-sided dice list_of_values = for i in range(number_of_trials): sum=0 for j in range(number_of_dice): sum+=random.randint(1,6) list_of_values.append(sum) mean=pylab.mean(list_of_values) std=pylab.std(list_of_values) print "Trials =", number_of_trials, "times" print "Mean =", mean print "Standard deviation =", std pylab.hist(list_of_values,20) pylab.xlabel("Value") pylab.ylabel("Number of times") pylab.show()
Рис. 9. Модель моделирования Python для расширенного нормального распределения

3. Многофазные системы массового обслуживания и стохастическое моделирование

3.1. Системы Массового Обслуживания

Процесс поступления заявок описывает как заявки приходят в систему. Определим
как временной интервал между прибытием заявок между и -ой заявкой, ожидаемое (среднее) время между поступлениями заявок как и частоту поступления заявок как

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

Определим как время обслуживание -ой заявки, как среднее время обслуживания заявки и как скорость обслуживания заявки.

Правило, которое использует обслуживающее устройство для выбора следующей заявки из очереди называется дисциплиной очереди СМО. Наиболее частые дисциплины очереди: Приоритетная – клиенты обслуживаются в порядке их важности. FIFO – первый пришёл первый обслужен; LIFO – стек, последний пришёл первым обслужен. Расширенная классификация систем по Кендаллу использует 6 символов: A/B/s/q/c/p, где А – распределение интервалов между приходящими заявками, В – распределение интервалов обслуживания, s – количество серверов, q – дисциплин обслуживания (опущена для FIFO), с – вместимость системы (опущено для бесконечных очередей), p – количество возможных заявок (опущено для открытых систем) . Для примера М/М/1 описывает Пуассоновский поток на входе, одно экспоненциальное обслуживающее устройство, одну бесконечную FIFO очередь, и бесконечное число заявок.

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

3.2. Почему многофазные?

3.3. Теоретическая основа

Мы будем исследовать время пребывания заявки в многофазной СМО. Обозначим как время пребывания заявки в системе, как время обслуживания n -ой заявки j -ой фазы. Рассмотрим как для k -ой фазы.

Существует такая константа такая, что

Теорема. Если условия (1) и (2) выполнены, тогда

3.4. Статистическое моделирование

3.5. Рекуррентное уравнение

Предположение. Рекуррентное уравнение для расчёта времени пребывания заявки в многофазной СМО.

Доказательство. Это правда, что если время , тогда время ожидания в -ой фазе -ой заявки является 0. В этом случае , время ожидания в -ой фазе -ой заявки и . Принимая во внимание два вышеупомянутых случая, мы в итоге имеем предполагаемый результат.

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

4. Python для многопроцессорной обработки

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

Мы начнём с использования модуля mpi4py. Это важно для представления главной идеи о том, как работает MPI. Он просто копирует предоставленную программу одному из процессорных ядер, определяемых пользователем, и интегрирует результаты после использования метода gather(). Пример Python кода (рис. 13) и результаты моделирования (рис. 14) представлены ниже.

#!/usr/bin/python import pylab import random import numpy as np from mpi4py import MPI dice=200 trials= 150000 rank = MPI.COMM_WORLD.Get_rank() size = MPI.COMM WORLD.Get_size() name = MPI.Get_processor_name() random.seed(rank) ## Each process - one throwing of a number of six-sided dice values= np.zeros(trials) for i in range(trials): sum=0 for j in range(dice): sum+=random.randint(l,6) values[i]=sum data=np.array(MPI.COMM_WORLD.gather(values, root=0)) if rank == 0: data=data.flatten() mean=pylab.mean(data) std=pylab.std(data) print "Number of trials =", size*trials, "times." print "Mean =", mean print "Standard deviation =", std pylab.hist(data,20) pylab.xlabel("Value") pylab.ylabel("Number of times") pylab.savefig("multi_dice_mpi.png")
Рис. 13. Python модель для расширенного нормального распределения с применением MPI.

5. Образовательный подход, основанный на моделировании

Все эти теоретические и программные структуры дают учащемуся проводить эксперимент с различными моделями многофазных СМО. Цель таких экспериментов двояка. Во-первых, это даёт учащимися понять следующую последовательность, которая важна в любых научных исследованиях: необходимые для изучения теоретические факты, математические модели, программные конструкции, компьютерные модели, стохастические модели и наблюдение результатов моделирования. Это даст учащемуся полную картину общих научных исследований (рис 16).

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

5.1. Эксперименты с моделями

Первая модель, представленная нами, основана на записи в реальном времени и мы называем это имитационной моделью. Она использует мультипроцессорный модуль Python. Точность этой модели зависит от точности и разрешающей способности метода времени time(). Она может быть довольно низкой, в случае различных операционных систем общего назначения, и довольно высокой, в случае систем реального времени. Учащийся может изменять эту модель используя ранее предложенное рекуррентное уравнение (для вычисления времени пребывания заявки в системе) и сравнивать результаты в обоих случаях.

Следующая модель вычисляет время пребывания заявки в системе и основана на стохастическоом моделировании. Модель не использует много-процессорность напрямую. Мультипроцессорная обработка эмулируется при помощи использования yield выражениями Python.

Последняя модель представлена здесь с использованием Python MPI mpi4py модулем. Здесь используется настоящий MPI (мультипроцессорный) подход для статистического моделирования и можем, за счёт этого, увеличивается количество испытаний в методе Монте Карло.

В общем, задача учащегося заключается в создании серии экспериментов с предоставленными моделями и получение экспериментального доказательства закона повторного логарифма (law of the iterated logarithm) для времени пребывания заявки в многофазной СМО.

5.2. Имитационная модель, использующая мультипроцессорный сервис

Программный код код состоит из двух главных частей. Первый предназначен непосредственно для расчётов, а следующий – для построения результатов. Модуль для вычисления содержит три главные функции: producer() – для получения заявок и помещения их в первую очередь; server() – для обслуживания заявок; consumer() – для получения результатов. Эта программная модель основана на реальной симуляции и не использует математические выражения для вычислений. Её точность зависит от точности временного модуля Python и, как правило, зависит от операционной системы. Вычисление работы обслуживающих устройств распределяются между различными процессами внутри мультипроцессорной системы. Компьютерный код для реализации, указанной выше модели, представлен на рисунке 18.

Import multiprocessing import time import random import numpy as np def server(input_q,next_q,i): while True: item = input_q.get() if i==0:item.st=time.time() ## start recording time ## (first phase) timc.sleep(random.expovariate(glambda|i])) ##stop recording time (last phase) if i==M-1:item.st=time.time()-item.st next_q.put(item) input_q.task_done() print("Server%d stop" % i) ##will be never printed why? def producer(sequence,output_q): for item in sequence: time.sleep(random.expovariate(glambda)) output_q.put(ilem) def consumer(input_q): "Finalizing procedures" ## start recording processing time ptime=time.time() in_seq= while True: item = input_q.get() in_scq+= input_q.task_done() if item.cid == N-1: break print_results(in_seq) print("END") print("Processing time sec. %d" %(time.time()-ptime)) ## stop recording processing time printf("CPU used %d" %(multiprocessing.cpu_count())) def print_resulls(in_seq): "Output rezults" f=open("out.txt","w") f.write("%d\n" % N) for l in range(M): f.write("%d%s" % (glambda[t],",")) f.write("%d\n" % glambda[M]) for t in range(N-1): f.write("%f%s" % (in_seq[t].st,",")) f.write("%f\n" % (in_seq.st)) f.close() class Client(object): "Class client" def __init__(self,cid,st): self.cid=cid ## customer id self.st=st ## sojourn time of the customer ###GLOBALS N=100 ## total number of customers arrived M=5 ## number of servers ### glambda - arrival + servicing frequency ### = customers/per time unit glambda=np.array(+) ###START if __name__ == "__main__": all_clients= q= for i in range(M): serv = multiprocessing.Process(target=server,args=(q[i],q,i)) serv.daemon=True serv.start() cons = multiprocessing.Process(target=consumer,args=(q[M],)) cons.start() ### start "produsing" customers producer(all_clients,q) for i in q: i.join()
Рис. 18. Python код для имитационной модели, использующей мультипроцессорный сервис.

Вопросы для изучения:

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

5.3. Единичный процесс статистической модели

Программный код для реализации указанной выше модели представлен на рисунке 21. Результаты симуляции представлены на рисунке 22.

#!/usr/bin/python import random import time import numpy as np from numpy import linspace def coroutine(func): del start(*args,**kwargs): g = func(*args,**kwargs) g.next() return g return start def print_header(): "Output rezults - header" f=open("out.txt","w") f.write("%d\n" % N) ##number of points in printing template f.write("%d\n" % TMPN) for t in range(M): f.write("%d%s" % (glambda[t],",")) f.write("%d\n" % glambda[M]) f.close() def print_results(in_seq): "Output rezults" f=open("out.txt","a") k=() for i in range(N-2): if in_seq[i].cid==template[k]: f.write("%f%s" % (in_seq[i].st,",")) k+=1 f.write("%f\n" % (in_seq.st)) f.close() coroutine def server(i): ST=0 ##sojourn time for the previous client item=None while True: item = (yield item) ##get item if item == None: ##new Monte Carlo iteration ST=0 continue waiting_time=max(0.0,ST-item.st-item.tau) item.st+=random.expovariate(glambda)+waiting_time ST=item.st def producer(): results= i=0 while True: if i == N: break c=Client(i,0.,0.) if i!=0: c.tau=random.expovariate(glambda) i+= 1 for s in p: c=s.send(c) results+=[c] for s in p: c=s.send(None) ##final signal return results class Client(object): def __init__(self,cid,st,tau): self.cid=cid self.st=st self.tau=tau def params(self): return (self.cid,self.st,self.tau) stt=time.time() N=1000000 ## Clients M=5 ## Servers ## Input/sevice frequency glambda= + MKS=20 ## Monte Carlo simulation results ## Number of points in the printing template TMPN=N/10000 ##printing template template= map(int,linspace(0,N-1,TMPN)) print_header() p= for i in range(M):p += for i in range! MKS): print_results(producer()) print("Step=%d" % i) sys.stdout.write("Processing time:%d\n" % int(time.time()-stt))
Рис. 21. Python код для единичного процесса статистической модели

5.4. Статистическая модель на MPI

В дополнении к предыдущей модели, должны быть импортированы несколько дополнительных модулей. Функция print_results() также должна быть переписана, так как на данном этапе у нас больше испытаний. Мы должны также переписать главную часть программы. На рисунке 24 мы предоставили только ту часть программного кода, которая отличается от кода предыдущей модели. Результаты моделирования представлены на рисунке 25.

Import sys from mpi4py import MPI .................... def print_results(in_seq): "Output rezults" f=open("out.txt","a") for m in range(int(size)): for j in range(MKS): for i in range(TMPN-l): f.write("%f%s" % (in_seq[m].st,",")) f.write("%f\n" % (in_seq[m][(TMPN-l)+j*TMPN].st)) f.close() .................... stt=time.time() #start time for the process rank = MPI.COMM_WORLD.Get_rank() size = MPI.COMM_WORLD.Get_size() name = MPI.Get_processor_name() N= 10**3 ## Clients M=5 ## Servers ## Input/sevice frequency glambda=+ ## Number of Monte-Carlo simulations for this particuar process MKS=20 TMPN=200 ## Number of points in printing templat template= map(int,linspace(0,N-1,TMPN)) ## points for printing p= results= ## this process results total_results= ## overall results for i in range(M):p += for i in range(MKS):results+=producer() total_results=MPI.COMM_WORLD.gather(results,0) random.seed(rank) if rank == 0: print_header() print_results(total_results) sys.stdout.write("Processing time: %d\n" % int(time.time()-stt))
Рис. 24. Python код для статистической модели на основе MPI

6. Выводы

6.1. Линейность модели и статистические параметры СМО

6.2. Расширения модулей Python и параллельное программирование с Си

6.3. Эффективность программных решений и дальнейшие разработки

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

Литература

Полный список использованной литературы

A. Arazi, E. Ben-Jacob and U. Yechiali, Bridging genetic net- works and queueing theory, Physica A: Statistical Mechanics and Its Applications 332 (2004), 585–616.
D.M. Beazley, Python Essential Reference, Addison-Wesley Professional, 2009.
J. Bernard, Use Python for scientific computing, Linux Journal 175 (2008), 7.
U.N. Bhat, An Introduction to Queueing Theory Modeling and Analysis in Applications, Birkhäuser, Boston, MA, 2008.
K.J. Bogacev, Basics of Parallel Programming, Binom, Moscow, 2003.
R.N. Caine and G. Caine, Making Connections: Teaching andthe Human Brain, Association for Supervision and Curriculum Development, Alexandria, 1991.
J. Clement and M.A. Rea, Model Based Learning and Instruction in Science, Springer, The Netherlands, 2008.
N.A. Cookson, W.H. Mather, T. Danino, O. Mondragón- Palomino, R.J. Williams, L.S. Tsimring and J. Hasty, Queue- ing up for enzymatic processing: correlated signaling through coupled degradation, Molecular Systems Biology 7 (2011), 1. A.S. Gibbons, Model-centered instruction, Journal of Structural Learning and Intelligent Systems 4 (2001), 511–540. M.T. Heath, Scientific Computing an Introductory Survey, McGraw-Hill, New York, 1997.
A. Hellander, Stochastic Simulation and Monte Carlo Meth- ods, 2009.
G.I. Ivcenko, V.A. Kastanov and I.N. Kovalenko, Queuing System Theory, Visshaja Shkola, Moscow, 1982.
Z.L. Joel, N.W. Wei, J. Louis and T.S. Chuan, Discrete–event
simulation of queuing systems, in: Sixth Youth Science Con- ference, Singapore Ministry of Education, Singapore, 2000, pp. 1–5.
E. Jones, Introduction to scientific computing with Python, in: SciPy, California Institute of Technology, Pasadena, CA, 2007, p. 333.
M. Joubert and P. Andrews, Research and developments in probability education internationally, in: British Congress for Mathematics Education, 2010, p. 41.
G.E. Karniadakis and R.M. Kyrby, Parallel Scientific Comput- ing in C++ and MPI. A Seamless Approach to Parallel Al- gorithms and Their Implementation, Cambridge Univ. Press, 2003.
D.G. Kendall, Stochastic processes occurring in the theory of queues and their analysis by the method of the imbedded Markov chain, The Annals of Mathematical Statistics 1 (1953), 338–354.
M.S. Khine and I.M. Saleh, Models and modeling, cognitive tools for scientific enquiry, in: Models and Modeling in Science Education, Springer, 2011, p. 290.
T. Kiesling and T. Krieger, Efficient parallel queuing system simulation, in: The 38th Conference on Winter Simulation, Winter Simulation Conference, 2006, pp. 1020–1027.
J. Kiusalaas, Numerical Methods in Engineering with Python, Cambridge Univ. Press, 2010.
A. Kumar, Python for Education. Learning Maths & Science Using Python and Writing Them in LATEX, Inter University Accelerator Centre, New Delhi, 2010.
H.P. Langtangen, Python Scripting for Computational Science, Springer-Verlag, Berlin, 2009.
H.P. Langtangen, A Primer on Scientific Programming with Python, Springer-Verlag, Berlin, 2011.
H.P. Langtangen, Experience with using Python as a primary language for teaching scientific computing at the University of Oslo, University of Oslo, 2012.
R. Lehrer and L. Schauble, Cultivating model-based reason- ing in science education, in: The Cambridge Handbook of the Learning Sciences, Cambridge Univ. Press, 2005, pp. 371–388.
G. Levy, An introduction to quasi-random numbers, in: Nu- merical Algorithms, Group, 2012.
J.S. Liu, Monte Carlo Strategies in Scientific Computing, Har- vard Univ., 2001.
V.E. Malishkin and V.D. Korneev, Parallel Programming of Multicomputers, Novosibirsk Technical Univ., Novosibirsk, 2006.
N. Matloff, Programming on Parallel Machines: GPU, Multi- core, Clusters and More, University of California, 2012.
M. Milrad, J.M. Spector and P.I. Davidsen, Model facilitated 
learning, in: Instructional Design, Development and Evalua- 
tion, Syracuse Univ. Press, 2003.
S. Minkevicˇius, On the law of the iterated logarithm in multi- phase queueing systems, Informatica II (1997), 367–376.
S. Minkevicˇius and V. Dolgopolovas, Analysis of the law of the iterated logarithm for the idle time of a customer in multiphase 
queues, Int. J. Pure Appl. Math. 66 (2011), 183–190.
Model-Centered Learning, Pathways to mathematical under- standing using GeoGebra, in: Modeling and Simulations for Learning and Instruction, Sense Publishers, The Netherlands, 
2011.
C.R. Myers and J.P. Sethna, Python for education: Computa- tional methods for nonlinear systems, Computing in Science & Engineering 9 (2007), 75–79.
H. Niederreiter, Random Number Generation and Quasi- Monte Carlo Methods, SIAM, 1992.
F.B. Nilsen, Queuing systems: Modeling, analysis and simu- lation, Department of Informatics, University of Oslo, Oslo, 1998.
R.P. Sen, Operations Research: Algorithms and Applications, PHI Learning, 2010. Добавить метки

Продемонстрируем основные выводы Центральной предельной теоремы с помощью MS EXCEL : построим выборочное распределение среднего, рассчитаем стандартную ошибку и сравним значения, полученные на основе выборки, с выводами ЦПТ.

стремится к нормальному распределению со средним значением μ и стандартным отклонением равным σ/√n

Примечание : Про статистики и их выборочные распределения можно прочитать в статье .

Покажем почему равно σ/√n.

Каждое отдельное наблюдение X i в выборке имеет дисперсию σ 2 . Из , следует, что сумма независимых случайных величин в выборке , т.е. х 1 +х 2 …+х n , имеет дисперсию n*σ 2 , а стандартное отклонение этой суммы равно КОРЕНЬ(n) *σ. Чтобы найти стандартное отклонение среднего выборки нужно разделить стандартное отклонение суммы на n. В результате получим, что стандартное отклонение выборочного среднего равно σ/√n.

Т.к. обычно стандартное отклонение исходного распределения, из которого взята выборка, неизвестно, то в расчетах вместо σ используют ее оценку s - стандартное отклонение выборки .

Соответствующая величина s/√n, где n – размер выборки , имеет специальное название: Стандартная ошибка (Standard Error of the Mean , SE M ).

Примечание : Термин SEM иногда также может использоваться для стандартного отклонения выборочного распределения среднего.

Примечание : Хотя Стандартная ошибка является, по сути, стандартным отклонением , ее специальное название обусловлено стремлением подчеркнуть, что она показывает величину неопределенности выборочного среднего . Стандартная ошибка оценивает насколько выборочное среднее Х ср отличается от среднего значения μ исходного распределения. А термин стандартное отклонение обычно используют для обозначения величины изменчивости отдельных элементов выборки от среднего .

Для применения ЦПТ необходимо, чтобы были выполнены следующие условия:

• отдельные наблюдения в выборке должны быть независимыми;
• наблюдения берутся из одной и той же генеральной совокупности , т.е. имеют одинаковое распределение с параметрами μ и σ;
• размер выборки n должен быть «достаточно большим» (см. пояснения ниже).

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

Примечание : Несмотря, что отдельные значения x i подчиняются какому-то неизвестному нам закону распределения, процедура объединения многих значений для вычисления суммы или среднего , приводит к нормальному распределению (для которого мы умеем вычислять вероятности). Зачастую, имеет смысл говорить, является распределение нормальным или нет, только в отношении суммы или среднего .

Примеры расчета вероятности в MS EXCEL с использованием ЦПТ

Задача1 . Предприятие производит плавленые сырки. Номинальный вес сырка должен составлять 100 грамм. По естественным причинам, вес каждого сырка отличается от номинала. Из опыта известно, что средний вес сырка составляет 105г, а стандартное отклонение равно 15г. Чтобы избежать потери репутации фирмы вес сырка не должен быть слишком мал, но он не должен быть слишком велик, т.к. при этом увеличиваются расходы. Известно, что любую упаковку из 30 штук сырков отбраковывают, если средний вес сырка в ней меньше 95г и больше чем 110г. Какая часть упаковок будет отбракована при 100% контроле?

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

Примечание : Хотя в ЦПТ сказано, что по нормальному закону распределено выборочное среднее , но очевидно, что выборочное распределение суммы также будет распределено по нормальному закону , но с другими параметрами.

Из условий задачи мы знаем, что среднее значение веса упаковки сырков равно 30шт *105г . Мы также можем вычислить стандартное отклонение этого выборочного распределения .

Стандартное отклонение известно только для сырка (15г ), но из (считаем, что веса сырков получаются случайным образом) можно вычислить Стандартное отклонение для упаковки:
Var(x 1 +…+x 30)= Var(x 1)+…+ Var(x 30)=30* Var(x)

Т.к. считаем, что все веса х i имеют одинаковое распределение, то случайную величину (вес сырка) обозначим просто х.

Следовательно, стандартное отклонение упаковки сырков =15*КОРЕНЬ(30)

Сначала определим вероятность, того что упаковка сырков будет весить менее 95*30г. В MS EXCEL это можно сделать с помощью формулы:
=НОРМ.РАСП(95*30; 105*30; 15*КОРЕНЬ(30); ИСТИНА)=0,013%

Теперь определим вероятность того, что упаковка сырков будет весить больше 110*30г.
=1-НОРМ.РАСП(110*30; 105*30; 15*КОРЕНЬ(30); ИСТИНА)=3,395%

Таким образом, отбраковано будет 3,395%+0,013%=3,407% продукции.

Тот же результат можно получить при расчете через среднее значение одного сырка:
=НОРМ.РАСП(95; 105; 15/КОРЕНЬ(30); ИСТИНА)+ 1-НОРМ.РАСП(110; 105; 15/КОРЕНЬ(30); ИСТИНА)

Задача2 . Из свойств нормального распределения можно ожидать, что примерно в 95% случаях выборочное среднее будет находиться в пределах 2-х стандартных ошибок от среднего генеральной совокупности (исходного распределения, из которого взята выборка ), т.е. в пределах:

2*s/КОРЕНЬ(n)<μ<2*s/КОРЕНЬ(n)

Например, пусть размер выборки n=30, среднее генеральной совокупности μ =0, а вычисленное на основе выборки стандартное отклонение s=5.

В этом случае стандартная ошибка = 5/КОРЕНЬ(30)

Покажем с помощью формулы MS EXCEL, что искомая вероятность действительно близка к 95%:
=1-((1-НОРМ.РАСП(2*5/КОРЕНЬ(30);0;5/КОРЕНЬ(30);ИСТИНА))+ НОРМ.РАСП(-2*5/КОРЕНЬ(30);0;5/КОРЕНЬ(30);ИСТИНА))=95,45%

Как работает ЦПТ при n=3 и n=10

Для демонстрации выводов ЦПТ проведем «оценку нормальности» распределения выборочного среднего при n=3 и n=10.

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

Как известно, среднее значение этого распределения =(1+6)/2=3,5 ; а стандартное распределение =КОРЕНЬ(((6-1+1)^2-1)/12)=1,708

С помощью MS EXCEL произведем 100 серий по 3 броска кубика (n=3) и 100 серий по 10 бросков (n=10).

Для каждой серии бросков (т.е. для каждой выборки ) будем вычислять выборочное среднее. Затем вычислим среднее Выборочных средних и стандартную ошибку . Убедимся, что в соответствии с ЦПТ , эти значения равны 3,5 и 1,708/КОРЕНЬ(n) , соответственно.

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

файле примера на листе ЦПТ Классик .

При n=3 График проверки распределения на нормальность будет соответствовать прямой очень условно (сохраняется дискретность данных, унаследованная от исходного распределения), но для n=10 – соответствие нормальному распределению будет хорошим.

Примечание : В качестве иллюстрации сравним графики проверки распределения на нормальность при n=3 и исходного , т.е. для n=1 (красные точки на рисунке ниже). Как видно на рисунке, значения, взятые из равномерного распределения, располагаются четко выраженными группами.

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

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

Вывод : С помощью MS EXCEL мы продемонстрировали как работает ЦПТ : не смотря на то, что исходное распределение по форме не имеет ничего общего с нормальным , уже при небольшом n=10 выборочное среднее распределено по закону близкому к нормальному с тем же средним значением и со стандартным отклонением равным стандартной ошибке .

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

Алгоритм решения задач с применением классической ЦПТ

Вы проводите аудит крупного банка. Банковский служащий сообщил Вам, что средний депозит в банке составляет 200 долл., а стандартное отклонение равно 45 долл. Вам нужно убедиться в истинности информации, сообщенной менеджером, поэтому Вы решаете взять данные по случайным 50 депозитам.
Дайте описание выборочного распределения среднего при n =50. Предполагая, что сообщенные менеджером характеристики распределения верны, вычислить вероятность, что рассчитанное Вами среднее значение выборки будет меньше 190 долл.

СОВЕТ : Отличное изложение материала по данной теме приведено на сайте http://brownmath.com/swt/chap08.htm (англ.)

Сначала дадим описание выборочного распределения среднего . Зачем нам это нужно? Дело в том, чтобы вычислить вероятность необходимо знать распределение вероятности. Т.е. нужно показать, что выборочное среднее распределено по нормальному закону.

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

Форма распределения . Для того, чтобы решить задачу необходимо убедиться, что выборочное распределение среднего является нормальным (выполняются условия применимости ЦПТ). Как правило, для этого необходимо проверить 2 условия:

• размер выборки не должен превышать 10% от генеральной совокупности ;
• размер выборки достаточен, чтобы, несмотря на форму исходного распределения, распределение выборочного среднего было нормальным . Обычно достаточно, чтобы n было больше 30.

Будем считать, что первое условие выполнено (пусть известно, что в банке более 1000 депозитов), соответственно, 50 депозитов составляет менее 10% от общего количества депозитов банка. Исходное распределение, скорее всего, будет смещенным влево, т.к. обычно большинство депозитов небольшого и среднего размера, а крупных депозитов гораздо меньше. Размер выборки является достаточно большим (50>30), чтобы гарантировать, что форма распределения выборочного среднего является близкой к нормальному распределению .

Среднее . Среднее выборочного распределения , согласно ЦПТ , равно среднему исходного распределения, т.е. в нашем случае 200 долл.

Разброс . Стандартное отклонение выборочного среднего (стандартная ошибка ), согласно ЦПТ, равна =45/КОРЕНЬ(50)=6,36 .

Теперь переходим непосредственно к решению задачи. Сначала построим выборочного среднего N(200; 45/КОРЕНЬ(50)).

Зеленая вертикальная линия соответствует х=190 долл.

По условиям задачи мы взяли выборку из 50 депозитов и вычислили среднее этой выборки (Хср). Теперь рассчитаем вероятность того, что Хср будет меньше 190 долл. Это можно сделать с помощью формулы
=НОРМ.РАСП(190; 200; 45/КОРЕНЬ(50); ИСТИНА)=0,058

Таким образом, если Х ср, вычисленное по 50 депозитам, окажется меньше 190 долл., то, это может стать серьезным основанием для сомнений в истинности слов банковского служащего (утверждавшего, что средний банковский депозит равен 200 долл.), т.к. это является маловероятным событием (<6%).

Расчеты приведены в файле примера на листе Задача .

Примечание : Частой ошибкой при решении подобных задач является неправильное использование стандартного отклонения , т.е. когда вместо стандартной ошибки используют известное стандартное отклонение исходного распределения (45 долл.), которое не обязательно является нормальным . Но, даже если исходное распределение нормальное , то вычисленное значение вероятности (в нашем случае оно будет около 40%) всегда существенно выше правильного значения (примерно 6%). Это соответствует схеме расчета, если бы мы выбрали лишь 1 депозит (вместо 50) и попытались бы на основании его значения принять решение об истинности слов служащего банка.

Резюме : Чаще всего на практике распределение, из которого делается выборка не известно (можно лишь предположить, что распределение банковских депозитов, скорее всего, скошено влево, т.к. обычно небольшие вклады составляют наибольшее количество). Но, не зная математического выражения для распределения, мы не можем оценить вероятность извлечь определенное значение из него. Именно в таких случаях нам помогает ЦПТ .

Альтернативная формулировка ЦПТ

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

Если x 1 , x 2 , x 3 , … x n – случайные величины с известными значениями среднего μ i и стандартного отклонения σ i , и y= x 1 +x 2 +x 3 + … +x n , то распределение

приближается к N (0;1) при n стремящемуся к бесконечности.

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

Как и в случае классической ЦПТ , для демонстрации выводов ЦПТ используем MS EXCEL. В качестве исходных распределений возьмем 4 B(0,1; 20), 3 U и 3 ). В этой книге мы, о производящих функциях будем давать краткую информацию и некоторые применения к подсчёту числовых характеристик случайных величин.

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

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

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

Рассмотрим следующий пример.

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

Решение. Условия ЦПТ соблюдается, поэтому с.в.имеет приближенно плотность распределения

По известным формулам для м.о. и дисперсии в случае равномерного распределения находим: Тогда

На основании формулы (26), находим (с учётом табличных значений функции Лапласа)

План:

1. Понятие центральной предельной теоремы (теорема Ляпунова)

2. Закон больших чисел, вероятность и частота (теоремы Чебышева и Бернулли)

1. Понятие центральной предельной теоремы.

Нормальное распределение вероятностей имеет в теории вероят­ностей большое значение. Нормальному закону подчиняется вероят­ность при стрельбе по цели, в измерениях и т. п. В частности, оказывается, что закон распределения суммы достаточно большого чис­ла независимых случайных величин с произвольными законами распределения близок к нормальному распределению. Этот факт, называемый центральной предельной теоремой или теоремой Ляпунова.

Известно, что нормально распределенные случай­ные величины широко распространены на практике. Чем это объясняется? Ответ на этот вопрос был дан

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

Пример. Пусть производится измерение некоторой физической величины. Любое измерение дает лишь приближенное значение изме­ряемой величины, так как на результат измерения влияют очень многие независимые случайные факторы (температура, колебания прибора, влажность и др.). Каждый из этих факторов порождает ничтожную "частную ошибку". Однако, поскольку число этих факторов очень велико, их совокупное действие порождает уже заметную «суммар­ную ошибку».

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

Рассмотрим условия, при которых выполняется "централь­ная предельная теорема"

Х1, Х2, ...,Х n – последовательность независимых случайных величин,

M (Х1), M (Х2), ..., M (Х n ) - конечные математические ожидания этих величин, соответственно равные М(Xk )= ak

D(Х1), D (Х2), ..., D (Х n ) - конечные дисперсии их, соответственно равные D (X k )= bk 2

Введем обозначения: S= Х1+Х2 + ...+Хn;

A k= Х1+Х2 + ...+Хn=; B2= D(Х1)+ D (Х2)+ ...+ D (Х n ) =

Запишем функцию распределения нормированной суммы:

Говорят, что к последовательности Х1, Х2, ...,Х n применима централь­ная предельная теорема, если при любом x функция распределения нормированной суммы при n ® ¥ стремится к нормальной функции распределения:

Right " style="border-collapse:collapse;border:none;margin-left:6.75pt;margin-right: 6.75pt">

Рассмотрим дискретную случайную величину X , задан­ную таблицей распределения:

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

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

Лемма Чебышева. Дана случайная величина X, принимающая только неотрицательные значения с математическим ожиданием M(X). Для любого числа α>0 имеет место выражение:

Неравенство Чебышева. Вероятность того, что отклонение случайной величины X от ее математического ожидания по абсолютной величине меньше положитель­ного числа ε , не меньше, чем 1 – D(X) / ε 2:

Р (| X-M (X) | < ε ) ³ 1 - D (Х) / ε 2.

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

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

2.2. Теорема Чебышева

Если Х1, Х2, ...,Хn..- попарно независимые случайные величины, причем диспер­сии их равномерно ограничены (не превышают постоян­ного числа С), то, как бы мало ни было положительное число ε , вероятность неравенства

÷ (Х1+Х2 + ...+Хn) / n - (M(Х1)+M(Х2)+ ...+M(Хn))/n | < ε

будет как угодно близка к единице, если число случайных величин достаточно велико.

P (÷ (Х1+Х2 + ...+Хn) / n - (M(Х1)+M(Х2)+ ...+M(Хn))/n | < ε )=1.

Теорема Чебышева утверждает:

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

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

Обозначим математическое ожидание каждой из слу­чайных величин через а;

В рассматриваемом случае среднее арифметическое математических ожиданий, как легко видеть, также равно а.

Можно сформулировать тео­рему Чебышева для рассматриваемого частного случая.

"Если Х1, Х2, ...,Хn..- попарно независимые случай­ные величины, имеющие одно и то же математическое ожидание а, и если дисперсии этих величин равномерно ограничены, то, как бы мало ни было число ε > О, ве­роятность неравенства

÷ (Х1+Х2 + ...+Хn) / n - a | < ε

будет как угодно близка к единице, если число случай­ных величин достаточно велико".

Другими словами, в условиях теоремы

P (÷ (Х1+Х2 + ...+Хn) / n - a | < ε ) = 1.

2.3. Сущность теоремы Чебышева

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

(М (Xj ) + М (Х2) +... + М (Х„))/п или к числу а в частном случае.

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

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

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

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

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

2.4. Значение теоремы Чебышева для практики

Приведем примеры применения теоремы Чебышева к решению практических задач.

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

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

Х1, Х2, ...,Хn

К. этим величинам можно применить теорему Чебышева, если:

1) Они попарно независимы.

2) имеют одно и то же ма­тематическое ожидание,

3) дисперсии их равномерно огра­ничены.

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

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

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

Если все указанные требования выполнены, мы вправе применить к результатам измерений теорему Чебышева: при достаточно большом п вероятность неравенства

| (Х1 + Хя+...+Х„)/п - а |< ε как угодно близка к единице.

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

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

На теореме Чебышева основан широко применяемый в статистике выборочный метод, суть которого состоит в том, что по сравнительно небольшой случайной выборке судят о всей совокупности (генеральной совокупности) исследуемых объектов.

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

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

Уже из приведенных примеров можно заключить, что для практики теорема Чебышева имеет неоценимое значение.

2.5. Теорема Бернулли

Производится п независимых испытаний (не событий, а испытаний). В каждом из них вероятность появления события A равна р.

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

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

Другими словами, если ε >0 сколь угодно малое число, то при соблюдении условий теоремы имеет место равенство

Р(| m / п - р| < ε)= 1

Замечание. Было бы неправильным на основании теоремы Бернулли сделать вывод, что с ростом числа испытаний относитель­ная частота неуклонно стремится к вероятности р; другими словами, из теоремы Бернулли не вытекает равенство (т/п) = р,

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

Задание 7-1.

1. Оценить вероятность того, что при 3600 бросаниях кости число появления 6 очков будет не меньше 900.

Решение. Пусть x – число появления 6 очков при 3600 бросаниях монеты. Вероятность появления 6 очков при одном бросании равна p=1/6, тогда M(x)=3600·1/6=600. Воспользуемся неравенством (леммой) Чебышева при заданном α = 900

= P (x ³ 900) £ 600 / 900 =2 / 3

Ответ 2 / 3.

2. Проведено 1000 независимых испытаний, p=0,8. Найти вероятность числа наступлений события A в этих испытаниях отклонится от своего математического ожидания по модулю меньше, чем 50.

Решение. x –число наступлений события A в n – 1000 испытаниях.

М(Х)= 1000·0,8=800. D(x)=100·0,8·0,2=160

Воспользуемся неравенством Чебышева при заданном ε = 50

Р (| х-M (X) | < ε) ³ 1 - D (х) / ε 2

Р (| х-800 | < 50) ³ / 50 2 = 1-160 / 2500 = 0,936.

Ответ. 0,936

3. Используя неравенство Чебышева, оценить вероятность того, что |Х - М(Х)| < 0,1, если D (X) = 0,001. Ответ Р³0,9.

4. Дано: Р(|Х-М(Х)\ < ε) ³ 0,9; D (X )= 0,004. Используя неравенство Чебышева, найти ε. Ответ. 0,2.

Контрольные вопросы и задания

1. Назначение центральной предельной теоремы

2. Условия применимости теоремы Ляпунова.

3. Отличие леммы и теоремы Чебышева.

4. Условия применимости теоремы Чебышева.

5. Условия применимости теоремы Бернулли (закона больших чисел)

Требования к знаниям умениям и навыкам

Студент должен знать обще смысловую формулировку центральной предельной теоремы. Уметь формулировать частные теоремы для не зависимых одинаково распределенных случайных величин. Понимать неравенство Чебышева и закон больших чисел в форме Чебышева. Иметь представление о частоте события, взаимоотношениях между понятиями "вероятность" и "частота". Иметь представление о законе больших чисел в форме Бернулли.

(1857-1918), вы­дающийся русский математик

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

Энциклопедичный YouTube

• 1 / 5

  Пусть есть бесконечная последовательность независимых одинаково распределённых случайных величин, имеющих конечное математическое ожидание и дисперсию . Обозначим последние μ {\displaystyle \mu } и σ 2 {\displaystyle \sigma ^{2}} , соответственно. Пусть также

  . S n − μ n σ n → N (0 , 1) {\displaystyle {\frac {S_{n}-\mu n}{\sigma {\sqrt {n}}}}\to N(0,1)} по распределению при ,

  где N (0 , 1) {\displaystyle N(0,1)} - нормальное распределение с нулевым математическим ожиданием и стандартным отклонением , равным единице. Обозначив символом выборочное среднее первых n {\displaystyle n} величин, то есть X ¯ n = 1 n ∑ i = 1 n X i {\displaystyle {\bar {X}}_{n}={\frac {1}{n}}\sum \limits _{i=1}^{n}X_{i}} , мы можем переписать результат центральной предельной теоремы в следующем виде:

  n X ¯ n − μ σ → N (0 , 1) {\displaystyle {\sqrt {n}}{\frac {{\bar {X}}_{n}-\mu }{\sigma }}\to N(0,1)} по распределению при n → ∞ {\displaystyle n\to \infty } .

  Скорость сходимости можно оценить с помощью неравенства Берри - Эссеена .

  Замечания

  • Неформально говоря, классическая центральная предельная теорема утверждает, что сумма n {\displaystyle n} независимых одинаково распределённых случайных величин имеет распределение, близкое к N (n μ , n σ 2) {\displaystyle N(n\mu ,n\sigma ^{2})} . Эквивалентно, X ¯ n {\displaystyle {\bar {X}}_{n}} имеет распределение близкое к N (μ , σ 2 / n) {\displaystyle N(\mu ,\sigma ^{2}/n)} .
  • Так как функция распределения стандартного нормального распределения непрерывна , сходимость к этому распределению эквивалентна поточечной сходимости функций распределения к функции распределения стандартного нормального распределения. Положив Z n = S n − μ n σ n {\displaystyle Z_{n}={\frac {S_{n}-\mu n}{\sigma {\sqrt {n}}}}} , получаем F Z n (x) → Φ (x) , ∀ x ∈ R {\displaystyle F_{Z_{n}}(x)\to \Phi (x),\;\forall x\in \mathbb {R} } , где Φ (x) {\displaystyle \Phi (x)} - функция распределения стандартного нормального распределения.
  • Центральная предельная теорема в классической формулировке доказывается методом характеристических функций (теорема Леви о непрерывности).
  • Вообще говоря, из сходимости функций распределения не вытекает сходимость плотностей . Тем не менее в данном классическом случае это имеет место.

  Локальная Ц. П. Т.

  В предположениях классической формулировки, допустим в дополнение, что распределение случайных величин { X i } i = 1 ∞ {\displaystyle \{X_{i}\}_{i=1}^{\infty }} абсолютно непрерывно, то есть оно имеет плотность. Тогда распределение также абсолютно непрерывно, и более того,

  f Z n (x) → 1 2 π e − x 2 2 {\displaystyle f_{Z_{n}}(x)\to {\frac {1}{\sqrt {2\pi }}}\,e^{-{\frac {x^{2}}{2}}}} при n → ∞ {\displaystyle n\to \infty } ,

  где f Z n (x) {\displaystyle f_{Z_{n}}(x)} - плотность случайной величины Z n {\displaystyle Z_{n}} , а в правой части стоит плотность стандартного нормального распределения.

  Обобщения

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

  Ц. П. Т. Линдеберга

  Пусть независимые случайные величины X 1 , … , X n , … {\displaystyle X_{1},\ldots ,X_{n},\ldots } определены на одном и том же вероятностном пространстве и имеют конечные математические ожидания и дисперсии : E [ X i ] = μ i , D [ X i ] = σ i 2 {\displaystyle \mathbb {E} =\mu _{i},\;\mathrm {D} =\sigma _{i}^{2}} .

  Пусть S n = ∑ i = 1 n X i {\displaystyle S_{n}=\sum \limits _{i=1}^{n}X_{i}} .

  Тогда E [ S n ] = m n = ∑ i = 1 n μ i , D [ S n ] = s n 2 = ∑ i = 1 n σ i 2 {\displaystyle \mathbb {E} =m_{n}=\sum \limits _{i=1}^{n}\mu _{i},\;\mathrm {D} =s_{n}^{2}=\sum \limits _{i=1}^{n}\sigma _{i}^{2}} .

  И пусть выполняется условие Линдеберга :

  ∀ ε > 0 , lim n → ∞ ∑ i = 1 n E [ (X i − μ i) 2 s n 2 1 { | X i − μ i | > ε s n } ] = 0 , {\displaystyle \forall \varepsilon >0,\;\lim \limits _{n\to \infty }\sum \limits _{i=1}^{n}\mathbb {E} \left[{\frac {(X_{i}-\mu _{i})^{2}}{s_{n}^{2}}}\,\mathbf {1} _{\{|X_{i}-\mu _{i}|>\varepsilon s_{n}\}}\right]=0,}

  где 1 { | X i − μ i | > ε s n } {\displaystyle \mathbf {1} _{\{|X_{i}-\mu _{i}|>\varepsilon s_{n}\}}} функция - индикатор.

  по распределению при n → ∞ {\displaystyle n\to \infty } .

  Ц. П. Т. Ляпунова

  Пусть выполнены базовые предположения Ц. П. Т. Линдеберга. Пусть случайные величины { X i } {\displaystyle \{X_{i}\}} имеют конечный третий момент . Тогда определена последовательность

  r n 3 = ∑ i = 1 n E [ | X i − μ i | 3 ] {\displaystyle r_{n}^{3}=\sum _{i=1}^{n}\mathbb {E} \left[|X_{i}-\mu _{i}|^{3}\right]} .

  Если предел

  lim n → ∞ r n s n = 0 {\displaystyle \lim \limits _{n\to \infty }{\frac {r_{n}}{s_{n}}}=0} (условие Ляпунова ), S n − m n s n → N (0 , 1) {\displaystyle {\frac {S_{n}-m_{n}}{s_{n}}}\to N(0,1)} по распределению при n → ∞ {\displaystyle n\to \infty } .

  Ц. П. Т. для мартингалов

  Пусть процесс (X n) n ∈ N {\displaystyle (X_{n})_{n\in \mathbb {N} }} является мартингалом с ограниченными приращениями. В частности, допустим, что

  E [ X n + 1 − X n ∣ X 1 , … , X n ] = 0 , n ∈ N , X 0 ≡ 0 , {\displaystyle \mathbb {E} \left=0,\;n\in \mathbb {N} ,\;X_{0}\equiv 0,}

  и приращения равномерно ограничены, то есть

  ∃ C > 0 ∀ n ∈ N | X n + 1 − X n | ≤ C {\displaystyle \exists C>0\,\forall n\in \mathbb {N} \;|X_{n+1}-X_{n}|\leq C} τ n = min { k | ∑ i = 1 k σ i 2 ≥ n } {\displaystyle \tau _{n}=\min \left\{k\left\vert \;\sum _{i=1}^{k}\sigma _{i}^{2}\geq n\right.\right\}} . X τ n n → N (0 , 1) {\displaystyle {\frac {X_{\tau _{n}}}{\sqrt {n}}}\to N(0,1)} по распределению при n → ∞ {\displaystyle n\to \infty } .