# Course Review: MATH 418

#### Probability

“I heard you had a lot of difficulty with the last homework. So you will be relieved to note that next homework you will have another opportunity to practice similar problems.”

Text:  A First Look at Rigorous Probability Theory, 2nd ed by J.S. Rosenthal

Prof: Dr Gordon Slade

Prof Slade is very clear and keeps things simple. He also has no problem slowing down to answer questions from students if they are not following along. He has a dry sense of humor, that keeps the class interesting, and he can even by funny when he is talking in earnest.

Difficulty

After taking measure theory, several sections of the course can feel like review. This was a good thing for me, as I found MATH 420 a tad fast. There are a handful of new techniques that you learn in the homework and class, but there are not that many new concepts if you have some background in measure theory and probability. MATH 421 material also comes up in terms of weak convergence.

Key Concepts

Probability Triples

Random Variables

Distributions

Expectation

Borel-Cantelli

Modes of Convergence

Law of Large Numbers

Central Limit Theorem

Characteristic Functions

Hard Concepts

Tail Events: Kind of funny to think about. Also, include definitions of limit supremum and limit infimum for sequences of event which can be difficult to convert to statements about limits of random variables.

Weak Convergence: There are a lot of equivalent statements, and if you pick the wrong one it can be a mission to prove that convergence occurs.

Conclusion

Good review of measure theory, and gives you a mathematical foundation to elementary probability.

# Mathematical Aside: Golden Mean Shift and Pascal’s Triangle (Part 3)

As was derived in Part 2, $|c_{m,n}|=$ ${n-(m-1)}\choose{m}$ where $c_{m,n}$ denotes the set of binary strings of length $n$ with exactly $m$ non-adjacent ones.

Today we will analyze $c_{n}$ the set of binary strings of length $n$ with any number of non-adjacent ones. We will need some additional notation.

• $c_{n,0}$ denote the the subset of $c_{n}$ ending with 0
• $c_{n,1}$ denote the the subset of $c_{n}$ ending with 1

After some thought, we realize that $c_{n,0} =c_{n-1}$ and $c_{n-2}$. We can then derive the recurrence $|c_{n}| = |c_{n,0}|+|c_{n,1}|=|c_{n-1}|+|c_{n-2}|$. After verifying the base case, we can conclude $|c_{n}| = F_{n+2}$, the Fibonacci Numbers!

Another way to compute $|c_{n}|$ is $|c_{n}| = \sum_{m=0}^{\infty}$ ${n-(m-1)}\choose{m}$.

Therefore $F_{n+2} =$ $\sum_{m=0}^{\infty}$ ${n-(m-1)}\choose{m}$.

With some shifting, we can solve for the $n^{th}$ Fibonnaci number :

$F_{n} =$ $\sum_{m=0}^{\infty}$ ${n-m-1}\choose{m}$

While this formula can be quite easily verified inductively, its nice to construct it explicitly.

# Mathematical Aside: Golden Mean Shift and Pascal’s Triangle (Part 2)

As we discussed in Part 1, we noticed a common pattern in the the $m^{th}$ element in the $n^{th}$ diagonal, $d_{m,n}$,  of Pascal’s Triangle and the function $c_{m,n}$, denoting the set of binary strings of length $n$ with exactly $m$ non-adjacent ones. Today we derive an explicit formula for $c_{m,n}$ in two ways.

Firstly, some more notation. The element in $r^{th}$ row and $k^{th}$ column in Pascal’s Triangle is denoted by ${r}\choose{k}$. Then we can see $d_{m,n} = {n+m-1,m}$. Unfortunately, $c_{m,n}$ is at a slight shift. To see this, we think about how long the string needs to be just so can fit in $m$ ones. The answer is $2(m-1)$. While the $d_{m,n}$ is non-zero straight away, it takes $c_{m,n}$ $2(m-1)$ increments to the length before it is non-zero. Therefore, $|c_{m,n}|=d_{m,n-2(m-1)}=$ ${n-(m-1)}\choose{m}$.

Another way to see this requires knowledge of combinations.  If we consider the unconstrained system, the clearly we have $u_{m,n} {n}\choose{m}$ options. We can construct a bijection from $u_{m,n-(m-1)}$ to $c_{m,n}$ as follows:

• For every element in $u_{m,n-(m-1)}$, we can add append a 0 to all but the rightmost 1 and construct a unique element in $c_{m,n}$
• For every element in $c_{m,n}$, we can add delete a 0 from the right side of all but the rightmost 1 and construct a unique element in $u_{m,n-(m-1)}$

Thus $|c_{m,n}| = |u_{m,n-(m-1)}|=$ ${n-(m-1)}\choose{m}$ as required.

We will use this to find an intriguing connection to the Fibonacci numbers in Part 3!

# Mathematical Aside: Golden Mean Shift and Pascal’s Triangle

I noticed something curious when I was working on my summer project last year. Basically, you consider the set $c_n$ of binary strings (strings of length $n$ where each symbol is either a $1$ or a $0$ and $1$‘s are non-adjacent).  So we construct a table like

 Length 1 2 3 4 5 6 Strings 0;1 00;01;10 000;001;010;100;101 0000;0001;0010;0100;0101;1000;1001;1010 … …

And then count the number of elements of length $n$ with $m$ ones.

 Number of ones [m] (below) Number of strings (below) Length of string [n] (right) 1 2 3 4 5 6 0 1 1 1 1 1 1 1 1 2 3 4 5 6 2 0 0 1 3 6 10 3 0 0 1 4 4 0 0

Do you see Pascal’s Triangle hiding inside? Starting from the top left and diagonally down to the left. First one is 1,2,1, then is 1,3,3,1 etcThe explanation is simple enough. We are using the fact that the subset of  $c_n$ composed of strings with $m$ ones (lets call this $c_{n,m}$) can be made by taking an element in $c_{n-1,m}$ and appending a zero to it or an element in $c_{n-2,m-1}$ and appending a zero-one to it. We end up with the recurrence $c_{n,m}= c_{n-1,m}+ c_{n-2,m-1}$. If we consider $d_{n,m}$ as the $n^{th}$ element in the $m^{th}$ diagonal, then we realize that $d_{n.m}$ follows the same recurrence. This reccurence is well documented in the literature for calculating $|c_n|$, here we are just using this idea for subsets of $c_n$ with exactly $m$ ones to connect it with Pascal’s Triangle.

The adventure continues in Part 2!

# The Island

When the People first arrived on the island, the great Captain divided the People into four groups.

Unto the first group he spake

You, the People of the darkness , I give for you the place in the light. Yours is the bright place of the Sun. May you revel in the Sun’s energy.”

A dark man came forward and bowed

Thank you, oh Captain, whose generosity surpasses all. We will take the Sun’s energy, only to give.”

unto the second group he spake

You, the People of the Earth, I give for you a place of the Earth. Yours is the central place of the Earth. May you nourish yourself with the Earth’s soil.”

A brown woman came up and curtsied

Thank you, oh Captain, whose wisdom is timeless. We will be nourished by the soil, only to sow and nurture.”

And unto the third group he spake

You, the People of of the sand, I give for you a place of the water. Yours is the aqueous place of the unmeasurable coastline. May you forever cleanse yourself with the water’s purity.”

An ochre man came forward and bowed

Thank you, oh Captain, whose justice is fairest. We will clean ourselves, only to cleanse our domain.

But to the remaining, fourth group he looked on and was silent.

A fair woman came forward

The island that you have brought us to is wondrous, are we the People of the sky, to have our share of this island?”

The mighty Captain was silent.

A fair man came forward

We have travelled with you for many Suns, is it not only just that we are to have a quarter of this paradise?”

The Captain remained silent.

A silence engulfed the gathering. Though the People were one in this silence, they were divided, now. For the first time, they felt apart from the People. They also felt apart from their groups. For the first time, each person interpreted individually an event that had been experienced collectively. They looked at one another, confused, insecure and suspicious.

A commotion had started amongst the fairer People. However, with a flash of the Captain’s eyes, the silence resumed. People made way as a toddler slowly crawled its way towards the Captain. Without hesitating, the toddler clutched at one of the Captain’s trunk-like legs, and pressed its head against it in a tight embrace.

The Captain’s face broke into a smile.

Oh the People of the Sky! Child is no doubt the father of man. Here you, fair lady, fair man, you would take, giving nothing. Here is your child, he gives his heart, taking nothing. That is how the People have lived best, taking little, giving all. To you the People of the Sky, I give you, yourself. Little though it may seem, now, when you use it to take, you shall take all. It is not for you that you will take, it is for the child at my feet. For it is from your child that you will learn to give, and it is to your child that you will give.”

The great Captain paused.

Henceforth, the People, you are the People of the Island. This Island is yours to take, yours to give. Ultimately, though, it will be the island that takes you. Explore this paradise, People of the Island. People of Darkness, the Sun is easiest found, for the art of discovery itself, is the Sun’s own. People of the Earth, the Earth is not hard to find either, for one must not look neither forward, nor backward, but under, to find it. People of the Sand, on this Island water is all around, however water is inside too. Though this inside water may be uncovered timeously, it is this water that is purest. People of the Sky, when you look upwards, see not the distant shore, hidden peak, the far flung star or galaxy. See nothing but yourself, and you shall find yourself.”

End of Part One