Техники подсчета и вероятности

Комбинации, вариации и перестановки являются наиболее часто используемыми техниками подсчета в изучении вероятностей благодаря их простоте в изучении экспериментов с равновероятными результатами. Один из самых знаковых примеров таких экспериментов происходит из азартных игр. Обычно они представляют собой недетерминированные процессы на выборочном пространстве \Omega = \{\omega_1, \omega_2, \cdots, \omega_N\}. Эти эксперименты имеют общую характеристику, что все события вида \{\omega_i\}\in\mathcal{A}_\Omega, с i\in\{1,2,\cdots, n\}, имеют одинаковую вероятность возникновения.

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

P(E) = \displaystyle \lim_{N\to\infty}g_N(E) = \lim_{N\to\infty}\frac{f_N(E)}{N}= \frac{\# E}{\# \Omega}

Здесь символ «#» относится к мощности множества. Это то, что известно как формула благоприятных случаев к возможным случаям.

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

Получение техник подсчета

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

Предположим, у нас есть «идеальная случайная машина», которая состоит из черного ящика, памяти, кнопки действия и кнопки сброса. У машины есть следующие свойства:

1. У машины есть только одна настраиваемая конфигурация: мощность ее выборочного пространства \Omega_N = \{\omega_1,\cdots,\omega_N\}
2. При нажатии на кнопку действия на экране будет отображаться один из элементов \Omega_N
3. Когда результат отображается, он сохраняется в памяти, и пока он там, при нажатии на кнопку действия он не будет отображаться снова.
4. Если машина уже показала все возможные результаты, она замерзнет и ничего не покажет.
5. Кнопка сброса очищает память и отображаемое на экране.

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

Эксперимент 1 (AORm): Действие — Запись по порядку — Сброс, повторить m раз

Машина настраивается \#\Omega = N и следующие шаги повторяются m\leq N раз:

1. Нажмите на кнопку действия
2. Запишите результат в упорядоченный список
3. Сброс

Когда мы закончим, у нас будет упорядоченный список с m элементами из \Omega_N = \{\omega_1,\cdots,\omega_N\}. Этот список можно интерпретировать как m-упорядоченность \Omega_N. Другими словами, выборочное пространство этого эксперимента \Omega_{AORm} будет следующим:

\Omega_{AORm}=\Omega_N \times \cdots \times \Omega_N = \Omega_N^m

Таким образом, будет \#\Omega_{AORm}=\#\Omega_N^m = N^m.

Эксперимент 2 (AOk): Действие — Запись по порядку, повторить k раз

Мы снова настраиваем машину \#\Omega = N и повторяем следующие шаги k раз (k\leq N):

1. Нажмите на кнопку действия.
2. Запишите результат в упорядоченный список.

Когда мы закончим, у нас будет упорядоченный список из k элементов из \Omega_N = \{\omega_1,\cdots,\omega_N\}, но ни один элемент не будет повторяться с предыдущими.

Поскольку машина, в принципе, не отдает предпочтения ни одному из возможных результатов (потому что она совершенно случайная), можно без ущерба для общности предположить, что при первом нажатии произошло событие \{\omega_1\}, так что выборочное пространство следующего действия должно быть \Omega_N\setminus\{\omega_1\}. Аналогично, можно без ущерба для общности предположить, что при втором нажатии произошло событие \{\omega_2\}; поэтому выборочное пространство следующего действия будет (\Omega_N\setminus\{\omega_1\})\setminus\{\omega_2\}. Если мы продолжим таким образом, то при k-м нажатии выборочное пространство будет следующим:

(\cdots(\Omega_N\setminus\{\omega_1\})\setminus\{\ω_2\}\cdots)\setminus\{\ω_{k-1}\}

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

\Omega_{AOk}= \Omega \times (\Omega_N\setminus\{\ω_1\}) \times ((\Omega_N\setminus\{\ω_1\})\setminus\{\ω_2\}) \times \cdots \times ((\cdots(\Omega_N\setminus\{\ω_1\})\setminus\{\ω_2\}\cdots)\setminus\{\ω_{k-1}\})

Если мы рассчитаем мощность этого множества, то получим

\#\Omega_{AOk}= N \cdot (N-1) \cdot (N-2) \cdots [N-(k-1)]=\displaystyle \frac{N!}{(N-k)!}

Из этого результата создается следующее определение:

Эксперимент 3 (ADk): Действие — Запись без порядка, повторить k раз

Этот эксперимент точно такой же, как предыдущий, только теперь порядок появления элементов \Omega_N не записывается. То есть, два k-упорядоченности с одними и теми же элементами, но в разном порядке теперь считаются одной и той же вещью. Таким образом, поскольку каждую k-упорядоченность, полученную в эксперименте AOk, можно записать (k)_k=k! различными способами, мощность выборочного пространства этого эксперимента будет следующей:

\#\Omega_{ADk} = \displaystyle \frac{\#\Omega_{AOk}}{(k)_k} = \frac{(N)_k}{k!} = \frac{N!}{k!(N-k)!}

Из этого можно установить следующее определение:

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