.. _review2:

Complement 2: Combinatorics and Probability Distributions
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++

.. note::

   This content was crafted by Ms. Colleen Pfaff.

Combinations
------------
.. math::
   C^n_r = \frac{n!}{(n-r)!r!}

**Helpful Tip:** If you’re having trouble visualizing a probability problem, draw it as a tree diagram, with each combination forming a different branch.

Example Combinations
~~~~~~~~~~~~~~~~~~~~
Red cards numbered 2–10 and black cards 2–10 are placed in a bag. If 4 cards are selected at random, what is the probability that 2 are red and 2 are black?

Solution
~~~~~~~~
There are :math:`C^9_2` ways to choose 2 red cards.  
There are :math:`C^9_2` ways to choose 2 black cards.

To calculate the probability, we need the total number of ways to choose 4 cards:

Number of ways to choose 4 cards: :math:`C^{18}_4`

Probability = :math:`\frac{C^9_2 C^9_2}{C^{18}_4} = \frac{1296}{3060}`

Discrete Probability
--------------------
.. math::
   \langle x \rangle = \sum_i x_i P_i

.. math::
   \langle x^2 \rangle = \sum_i x_i^2 P_i

Example Discrete Probability
~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Calculate :math:`\langle x \rangle`, :math:`\langle x^2 \rangle`, and :math:`\sigma^2` for a coin flip.

Solution
~~~~~~~~
.. math::
   \langle x \rangle = (1)(0.5) + (-1)(0.5) = 0

.. math::
   \langle x^2 \rangle = (1)^2(0.5) + (-1)^2(0.5) = 1

.. math::
   \sigma^2 = \langle x^2 \rangle - \langle x \rangle^2 = 1 - 0 = 1

Continuous Probability
----------------------
.. math::
   \langle x \rangle = \int x P(x)\,dx

and

.. math::
   \int P(x)\,dx = 1

Independent Variables
---------------------
.. math::
   \langle uv \rangle = \langle u \rangle \langle v \rangle

Example Independent Variables
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Are temperature and the size of a system independent?

Solution
~~~~~~~~
Yes, temperature and system size are independent!

Binomial Distribution
---------------------
A success has probability :math:`p`, and a failure has probability :math:`1 - p`. Success typically has a value of 1 and failure a value of –1.  
This makes sense since :math:`p + (1 - p) = 1`.

Probability of :math:`k` successes and :math:`n-k` failures in :math:`n` trials:

.. math::
   p^k(1-p)^{n-k}

If we have :math:`k` successes in :math:`n` trials, then there must be :math:`n-k` failures because there are only two possible outcomes.  
The average number of successful trials is the probability of success times the number of trials:

.. math::
   \langle k \rangle = np

.. math::
   \sigma^2 = np(1-p)

Drunkard’s Walk
~~~~~~~~~~~~~~~
A man leaves the bar and he is just as likely to step to the left as to the right. What is his average distance after :math:`N` steps, and what is the variance?

Solution
~~~~~~~~
Let’s examine the possible outcomes after 2 steps:  
LL, RR, LR, RL — and the probability of each of these outcomes is:

.. math::
   \frac{1}{4}, \frac{1}{4}, \frac{1}{4}, \frac{1}{4}

This means that after 2 steps, the average distance is 0.  
We can extrapolate this behavior to :math:`N` steps — therefore, after :math:`N` steps the average distance is still 0.

.. math::
   \langle d^2 \rangle = (\langle s_1 \rangle + \langle s_2 \rangle + \ldots + \langle s_N \rangle)^2 = \langle s_1^2 \rangle + \langle s_2^2 \rangle + \ldots + \langle s_N^2 \rangle + \langle s_1s_2 \rangle + \langle s_2s_1 \rangle + \ldots

We know that:

.. math::
   \langle s_1^2 \rangle = 1

Whereas each term like :math:`\langle s_1 s_2 \rangle` is equally likely to be 1 or –1, and thus averages to 0.

Therefore, for every :math:`N` steps:

.. math::
   \langle d^2 \rangle = (1 + 1 + 1 + \ldots + 1) = N

.. math::
   \sigma_d = \sqrt{N}