Markov Chains: An Intro

The Markov Property

A stochastic process (“a mathematical object usually defined as a collection of random variables”) is said to have the Markov Property if, conditional on the present value, the future is independent on the past.

Let’s firstly introduce some notation: let S be a countable set called the state space and let = (Xt: t ≥ 0) be a sequence of random variables taking values in S.

Then, the sequence X is called a Markov Chain if it satisfies the Markov Property:

Screen Shot 2017-10-05 at 5.24.15 PM.png

for all t ≥ 0 and all x0, x1, …, xt ϵ S.

Notation is simplified in the case where the Markov chain is homogeneous. This is when for all i, j ϵ S, the conditional probability P(Xt+1 = j | Xt = i) does not depend on the value of t.

Examples

  • Branching Process: The branching process is a simple model of the growth of a population; each member of the nth generation has a number of offspring that is independent of the past; Xn = size of the nth generation.
  • Random Walk: A particle performs a random walk on the line: let Z1, Z2, …, be independent with P(Zi = 1) = p and P(Zi = -1) = 1-p, then Xn =
    Z1 + … + Zn; at each epoch of time, it jumps a random distance that is independent of the previous jumps.
  • Poisson Process: the Poisson process satisfies a Markov property in which time is a continuous variable rather than a discrete variable, and thus the Poisson process is an example of a continuous-time Markov chain; the Markov property still holds as arrivals after time t are independent of arrivals before this time.

Two Quantities

For simplification (and as this is only an intro to  Markov chains) we’ll assume that the Markov chains are homogeneous.

Two quantities that are needed in order to calculate the probabilities in a chain are the:

  1. transition matrix: P = (pi,j: i,j ϵ S) given by pi,j = P(X1 = j | X0 = i);
  2. initial distribution: λ = (λi : i ϵ S) given by λi = P(X0 = i).

As we have assumed homogeneity we have that

pi,j = P(Xn+1 = j | Xn = i) for n ≥ 0.

These quantities are characterised in the following way:

Proposition:

a) The vector λ is a distribution  in that λi ≥ 0 for i ϵ S and the sum of λi over i = 1.

b) The matrix P = (pi,j) is a stochastic matrix in that pi,j ≥ 0 for i, j ϵ S and the sum of pi,j over j = 1 for i ϵ S (i.e. that P row sums to 1)

Proof:

a) As λi is a probability, it is clearly non-negative. Additionally, the sum of λi over i = the sum of P(X0 = i) over i = 1.

b) Since pi,j is a probability, it is non-negative. Finally, the sum of pi,j over j = the sum of P(Xn+1 = j | Xn = i) over j = P(Xn+1 ϵ S | Xn = i) = 1.

Hope you enjoyed this brief introduction to a Markov Chain!

M x

Advertisements

Mind the Gap

Having now been through one full year of university, I thought I’d write a blog post on the differences between secondary school and university mathematics in the British curriculum.

Personally, the main difference that I found was the focus on mathematical proof, something that is not taught in secondary school. For example, one of my lecture courses in first year was Numbers and Sets, which focused on learning how to construct a proof, rather than teaching a lot theory. The technique of writing a proof is something that, as a mathematician, I will carry with me throughout the rest of my academic career so I worked hard to learn this skill well. Becoming used to the language and symbols used in mathematical documents was definitely challenging but vital in order to be able to understand lectures.

The only part of A-Levels that prepared me for this major aspect of university maths was the fact that in order to score all the method marks we had to demonstrate all the steps in our working out. However, I must stress that this is not the same; mathematical proofs, especially in pure maths, often require more explanation in each step and a more logical succession of steps.

The other big difference is not understanding everything! For me, A-Level maths was not a big challenge. Yes, I studied hard, but things came easily for me and I found that I wouldn’t be stuck on a question for a very long time. Fast-forward to now, I find myself stuck on a question for hours! Whilst this can often be very frustrating, I love and thrive off the challenge – this year I have progressed so much as a mathematician!

Finally, mathematics at university is much less computational. There are some more applied courses where computation is essential, however the pure courses require almost no calculations! In secondary school, they label pure maths as what I now call applicable maths. This is maths that still requires are fair bit of computational work, however it is not directly linked to another subject, such as physics. For example, differential equations.

Hope you enjoyed this brief overview of my thoughts on the differences between university and secondary school mathematics. If you would like me to go more in depth please leave me a comment below! M x

MATHS BITE: Heptadecagon

A heptadecagon (or a 17-gon) is a seventeen sided polygon.

File:Regular polygon 17 annotated.svg

Regular Heptadecagon | Wikipedia

Constructing the Heptadecagon

In 1796, Gauss proved, at the age of 19 (let that sink in…) that the heptadecagon is constructible with a compass and a straightedge, such as a ruler. His proof of the constructibility of an n-gon relies on two things:

  • the fact that “constructibility is equivalent to expressibility of the trigonometric functions of the common angle in terms of arithmetic operations and square root extractions“;
  • the odd prime factors of n are distinct Fermat primes.

Constructing the regular heptadecagon involves finding the expression for the cosine of  2\pi /17 in terms of square roots, which Gauss gave in his book Disquistiones Arithmeticae:

{\displaystyle {\begin{aligned}16\,\cos {\frac {2\pi }{17}}=&-1+{\sqrt {17}}+{\sqrt {34-2{\sqrt {17}}}}+\\&2{\sqrt {17+3{\sqrt {17}}-{\sqrt {34-2{\sqrt {17}}}}-2{\sqrt {34+2{\sqrt {17}}}}}}\\=&-1+{\sqrt {17}}+{\sqrt {34-2{\sqrt {17}}}}+\\&2{\sqrt {17+3{\sqrt {17}}-{\sqrt {170+38{\sqrt {17}}}}}}.\end{aligned}}}

Source: Wikipdia

An explicit construction was given by Herbert Willian Richmond in 1893.

Regular Heptadecagon Using Carlyle Circle.gif

Source: Wikipedia

M x

Friedman Numbers

A Friedman number is an integer that can be obtained combining all its digits with the 5 arithmetic operations (+, -, x, /, ^) and concatenation. Note that parentheses can be used in the expressions in order to “override the default operator precedence“. These numbers are named after mathematician Erich Friendman.

For example, 13125 is a Friedman number as it can be written as $21\cdot5^{3+1}$.

nice Friedman number is one where the digits in the expression can be arranged to be in the same order as the number itself. An example of this is 127 = -1 + 2^7.

Friedman numbers can be repdigits, such as

\[999999999= ((9 + 9 + 9)^{9 - 9}+9)^9 - 9/9\]

or pandigital numbers, like

\[9108432576 = 251^3\cdot4\cdot6\cdot(7 + 8 + 9 + 0).\]

This link will take you to a list of Friedman numbers and their decompositions up to 10^6.

Michael Brand showed that the density of Friedman numbers among the naturals is 1. This means that the probability of a number chosen randomly and uniformly between 1 and n to be a Friedman number tends to 1 as n tends to infinity.

Finding 2-digit Friedman Numbers

2-digit Friedman numbers are the easiest to find, although there are less of them than 3-digit Friedman numbers.

Working in base 10 Let’s represent a 2-digit number by 10m + n, where n is an integer from 0 to 9. Now, we only need to check each possible combination of m and n against the equalities:

10m + n = m^n and 10m + n = n^m 

We do not have to worry about n, m x n, m – n and m/n as these will always be smaller than 10m + n when n < 10.

To read more click here.

M x

New Books in Maths: October 2017

The Perfect Bet: How Science and Math are Taking the Luck Out of Gambling

Author: Adam Kucharski

Release Date: September 26th 2017

In The Perfect Bet, mathematician Adam Kicharski tells the story about how experts have succeeded in “pull[ing] the rug out from under Lady Luck”. In the process they have revolutionised mathematics and science; Kucharski demonstrates how the search for theperfect bet has been crucial for “the scientific pursuit of a better world”

“An elegant and amusing account…. Anyone planning to enter a casino or place an online bet would be advised to keep this book handy.”

-Wall Street Journal

Goodreads

The Maths Behind…

Author: Colin Beveridge

Release Date: 5th October 2017

In this book, Colin Beveridge explores the maths behind over 60 everyday phenomena, including why traffic jams often turn out to have no cause when you get to the end of the queue and whether some lotteries might be easier to win than others.

The Maths Behind… takes a scientific view of our everyday world, giving answers to all the “niggling questions” in your life as well as to those that you never even thought of asking.

Foolproof, and Other Mathematical Meditations

Author: Brian Hayes

Release Date: 13th October 2017

In Foolproof, and Other Mathematical Meditations, Brian Hayes convinces the reader that mathematics is too important and too fun to be left only to mathematicians. Topics explores range from Markov chains to Sudoku. As a non-mathematician, he argues that maths is an essential tool to understand the world, whilst also being a world in itself filled “with objects and patterns that transcend earthly reality”.

“Hayes makes math seem fun. Whether he’s tracing the genealogy of a well-worn anecdote about a famous mathematical prodigy, or speculating about what would happen to a lost ball in the nth dimension, or explaining that there are such things as quasirandom numbers, Hayes wants readers to share his enthusiasm.”

-Amazon

M x

 

Surreal Numbers

Surreal numbers were first invented by John Horton Conway in 1969, but was introduced to the public in 1974 by Donald Knuth through his book ‘Surreal Numners: How Two Ex-Students Turned on to Pure Mathematics and Found Total Happiness‘.

What are Surreal Numbers?

Surreal numbers are the ‘most natural’ collection of numbers that include both real numbers and the infinite ordinal numbers of Georg Cantor. The surreals have many of the same properties as the reals, including the usual arithmetic operations. Hence, they form an ordered field.

For a surreal number x we write x = {XL|XR} and call XL and XR the left and right set of x,respectively. These will be explained below.

Conway Construction

“Surreal numbers are constructed inductively as equivalence classes of pairs of sets of surreal numbers, restricted by the condition that each element of the first set is smaller than each element of the second set.”

– Wikipedia

Using the Conway construction, we construct the surreal numbers in stages along with an ordering ≤ such that for any two surreal numbers a and b either a ≤ b or b ≤ a.

Every number corresponds to two sets of previously created numbers, such that no member of the left set is greater than or equal to any member of the right set. Therefore, if x = {XL|XR} then for each xL ∈ XL and xR ∈ XR, xL is not greater than xR.

In the first stage of construction, there are no previously existing numbers so the only representation must use the empty set: { | } = 0.

Subsequent stages yield the following:

  • {0|} = 1, {1|} = 2, {2|} = 3, etc;
  • {|0} = -1, {|1} = -2, {|2} = -3, etc.

For more, click here.

M x

How to Solve It

In 1945, Hungarian mathematician George Pólya wrote an extremely successful book called How to Solve It, which sold over one million copies and has been translated into 17 languages. In this book, Pólya identifies the four basic principles of problem solving.

1. Understand the Problem

Firstly, you must understand the problem you are tackling.  Although this may seem like common sense, it is often overlooked; the amount of times I’ve been staring at a problem for hours because I haven’t fully understood what it is asking! Consider asking the following questions:

  • What is the unknown? What are the data? What is the condition?
  • What are you asked to find or show?
  • Can you restate the problem in your own words?
  • Do you understand all the words used in stating the problem?

For some areas in maths, such as mechanics, drawing a labelled figure can often be extremely helpful to visualise what is going on.

Resultado de imagem para free body diagram

Example of Diagram


2. Devise a Plan

There are many different suitable ways to solve a problem, as mentioned by Pólya. However, it is important to choose an appropriate strategy, which is a skill learnt by solving many problems. Some strategies include:

  • Guess and check
  • Use symmetry
  • Consider special cases
  • Solve an equation or use a formula
  • Look for a pattern
  • Solve a simpler problem
  • Work backwards
  • Eliminate possibilities

When choosing a strategy, it may help to consider whether you have solved a related problem already or whether you can think of a familiar problem that has the same or similar unknown.


3. Carry out the Plan

Once you have devised the plan, this step is simple if you already have the necessary skills, often only required care and patience -try to avoid silly mistakes!

Persist with the plan that you have chosen, only discarding it after multiple failed attempts. Then, return to step 2.

4. Look back

Pólya highlights how a lot can be gained from looking back and reflecting on the work you have done, asking yourself what worked and what didn’t. This way you can implement strategies that were successful for future problems that are similar.


Read more here.

M x