Category Archive

You are currently browsing the category archive for the ‘MATH6028’ category.

MATH6028: Poker Hack and Spin the Wheel

November 27, 2017 in MATH6028 | Leave a comment

A Poker Hack

I told this story in class on Friday. I wasn’t sure if it was true but it appears that it is.

Texas Hold’Em Poker

‘Texas‘ is a poker game where a number of players sit around a table. Two cards are dealt to each player. There after follows a round of betting, the reveal of three more cards (the flop), more betting, another card (the turn), another round of betting, another card (the river), and another round of betting:

poker1

What we are interested in is what happens after all this, before another hand is dealt?

The deck is shuffled.

A shuffle is required to mix up the deck. Here we used three terms: deck, shuffle, mixed up. These can all be given a precise mathematical realisation (see the introduction here for more). Mixed up means ‘close to random’. Here let me introduce a mathematical realisation of random:

If one is handed a deck of cards, face down, and if each possible order of
the cards is equally possible then the deck is considered random.

Note there are 52!\approx 10^{68} possible orders that a deck can be in so when a deck is random the probability that a deck is in a specific order is

\displaystyle \frac{1}{52!}.

One popular method of shuffling cards is the riffle shuffle. In a remarkable 1992 paper by Bayer & Diaconis, with a really cool name: Trailing the Dovetail Shuffle to Its Lair, it is shown that seven riffle shuffles are necessary and sufficient to get a deck close to random:

graph20

Here we see d, distance to random, plotted against k, number of shuffles. After five shuffles the deck is still far from random, but then there is a fairly abrupt convergence to random. After seven shuffles the distance to random is less than 1/e.

So the idea is after, say, ten shuffles (or, equivalently, about ten rounds of hands), the deck is mixed up or close to random: each of the 52! orders are approximately likely.

Read the rest of this entry »

Advertisement

MATH6028: Fibonacci Sequence Exercises

November 22, 2017 in MATH6028 | Leave a comment

The Fibonacci Sequence is given by the recursive definition:

\displaystyle F(n)=\begin{cases}1 & \text{ if }n=1\text{ or }n=2\\ F(n-1)+F(n-2) & \text{ otherwise } \end{cases}

Exercises

  • Prove that if F(n)=x^n satisfies the recurrence relation

F(n+2)=F(n+1)+F(n),

that x=\frac{1\pm \sqrt{5}}{2}.

  • If the Fibonacci Sequence is given by:

\displaystyle F(n)=\frac{\phi^n-\psi^n}{\sqrt{5}},

where \phi=\frac{1+\sqrt{5}}{2} and \psi=\frac{1-\sqrt{5}}{2}, prove that for large n:

F(n+1)\approx \phi\cdot F(n)

  • Use ten terms of the Fibonacci Sequence to write down a sequence of rational approximations to \phi.

 

  • Using \displaystyle F(n)=\frac{\phi^n-\psi^n}{\sqrt{5}}, where \phi=\frac{1+\sqrt{5}}{2} and \psi=\frac{1-\sqrt{5}}{2}, or otherwise, find F(22).

MATH6028: Chaos Theory II

November 21, 2017 in General, MATH6028, MS 3011 | Leave a comment

This follows on from this post.

Recall the Doubling Mapping D:[0,1)\rightarrow [0,1) given by:

\displaystyle D(x)=\begin{cases} 2x & \text{ if }x<1/2 \\ 2x-1 & \text{ if }x\geq 1/2 \end{cases}

At the end of the last post we showed that this dynamical system displays sensitivity to initial conditions. Now we show that it displays topological mixing (a chaotic orbit) and density of periodic points.

First we must talk about periodic points.

Periodic Points

Consider, for example, the initial state \displaystyle x_0=\frac{1}{9}. The orbit of x_0 is given by:

\displaystyle \text{orb}(x_0)=\left\{\frac{1}{9},\frac29,\frac49,\frac89,\frac79,\frac59,\frac19,\frac29,\dots\right\}

Here we see \frac19 repeats itself and so gets ‘stuck’ in a repeating pattern:

graph1

The orbit of x_0=1/9.

The orbit of any fraction, e.g. \displaystyle x_0=\frac{4}{243}, must be periodic, because \displaystyle D\left(\frac{i}{243}\right) is either equal to \displaystyle \frac{2i}{243} of \displaystyle \frac{2i-243}{243} and so the orbit consists only of states of the form:

\displaystyle \frac{i}{243},

and there are only 243 of these and so after 244 iterations, some state must be repeated and so we get locked into a periodic cycle.

If we accept the following:

Proposition

A fraction \frac{p}{q} has a recurring binary expansion:

\displaystyle \frac{p}{q}=0.b_1\dots b_m\overline{a_1a_2\dots a_n}_2,

then this is another way to see that fractions are (eventually) periodic. Take for example,

\displaystyle x_0=0.101,101,101,101,\dots_2=0.\overline{101}_2=\frac{5}{7}.

Read the rest of this entry »

MATH6028: Chaos Theory Exercises

November 16, 2017 in MATH6028 | Leave a comment

Geometric Series

Let a,r\in\mathbb{R} be constants. Let \{a_n\} be a sequence of real numbers with the following recursive definition:

a_n=\begin{cases}a & \text{ if }n=1\\ r\cdot a_{n-1}&\text{ if }n>1\end{cases}.

Therefore the sequence is given by:

a,ar,ar^2,ar^3,ar^4,\dots

Such a sequence is called a geometric sequence with common ratio r.

When we add up the terms a sequence we have a geometric sum:

S_n=a+ar+ar^2+ar^3+\cdots ar^{n-1}.

Here S_n is the sum of the first n terms.

We can find a formula for S_n using the following ‘trick’:

r\cdot S_n=ar+ar^2+ar^3+\cdots ar^n

\Rightarrow a+r\cdot S_n-ar^n=S_n

\Rightarrow S_n(r-1)=a(r^n-1)

\displaystyle \Rightarrow S_n=\frac{a(r^n-1)}{r-1}.

Exercises

Assuming that |r|<1, find a formula for the geometric series

\displaystyle S_{\infty}=\lim_{n\rightarrow \infty}S_n.

Binary Numbers

Exercises

  • Write the following as fractions:

0.1_2,\,0.11_2,\,0.101_2.

  • Use infinite geometric series to show that:
    • 0.111\dots_2=1
    • 0.0111\dots_2=\frac12
    • 0.101010\dots_2=\frac23

Doubling Mapping

The doubling mapping D:[0,1)\rightarrow [0,1) is given by:

\displaystyle D(x)=\begin{cases}2x & \text{ if }x<1/2 \\ 2x-1 & \text{ of }x\geq 1/2\end{cases}.

Exercises

  • Find the first six iterates of the point x_0=\frac17 under D.
  • Find the first four iterates of the point

x_0=\frac{1}{2}+\frac{1}{2^2}+\frac{0}{2^3}+\frac{1}{2^4}=0.1101_2.

  • Where x has the binary representation

x = 0.a_1a_2a_3a_4a_5a_6a_7a_8\dots ,

write down expressions for D(x) and D^5(x).

  • Hence find points y, z \in [0, 1] such that y and z agree to 5 binary digits but D^N(y) and D^N(z) differ in the first binary digit for some N \in \mathbb{N}.
  • Describe the period-5 points of D.
  • Let w \in [0, 1] have a binary representation beginning w = 0.01001\dots  . Find a period-5 point \gamma of D such that w and \gamma agree to five binary digits.
  • Find a \delta \in [0, 1] such that there are iterates of \delta, D^{n_1}(\delta),D^{n_2}(\delta),D^{n_3}(\delta), with n_1, n_2, n_3 \in \mathbb{N}, that agree with 0.111 , 0.101, and 0.010, to three binary
    digits.

Sensitivity to Initial Conditions

Exercise

Let f(x)=4x\cdot (1-x). Where [0,1] is the set of states, and f:[0,1]\rightarrow [0,1] the iterator function, by looking at the first seven iterates of x_0=0.8 and y_0=0.81, show that this dynamical system displays sensitivity to initial conditions [HINT:4*ANS*(1-ANS)]

 

 

MATH6028: Chaos Theory (Part I)

November 14, 2017 in General, MATH6028, MS 3011 | 1 comment

Dynamical Systems

A dynamical system is a set of states S together with an iterator function f:S\rightarrow S which is used to determine the next state of a system in terms of the previous state. For example, if x_0\in S is the initial state, the subsequent states are given by:

x_1=f(x_0),

x_2=f(x_1)=f(f(x_0))=(f\circ f)(x_0)=:f^2(x_0)

x_3=f(x_2)=f(f^2(x_0))=f^3(x_0),

and in general, the next state is got by applying the iterator function:

x_{i}=f(x_{i-1})=f^i(x_0).

The sequence of states

\{x_0,x_1,x_2,\dots\}

is known as the orbit of x_0 and the x_i are known as the iterates.

Such dynamical systems are completely deterministic: if you know the state at any time you know it at all subsequent times. Also, if a state is repeated, for example:

\text{orb}(x_0)=\{x_0,x_1,x_2,x_3,x_4=x_2,x_5\dots,\}

then the orbit is destined to repeated forever because

x_5=f(x_4)=f(x_2)=x_3,

x_6=f(x_5)=f(x_3)=x_4=x_2, etc:

\Rightarrow \text{orb}(x_0)=\{x_0,x_1,x_2,x_3,x_2,x_3,x_2,\dots\}

Example: Savings

Suppose you save in a bank, where monthly you receive 0.1\%=0.001 interest and you throw in 50 per month, starting on the day you open the account.

This can be modeled as a dynamical system.

Let S=\mathbb{R} be the set of euro amounts. The initial amount of savings is x_0=50. After one month you get interest on this: 0.001\times50, you still have your original 50 and you are depositing a further €50, so the state of your savings, after one month, is given by:

x_1=50+0.001\times 50+50=(1+0.001)50+50.

Now, in the second month, there is interest on all this:

interest in second month 0.001\times((1+0.001)50+50)=0.001x_1,

we also have the x_1=(1+0.001)50+50 from the previous month and we are throwing in an extra €50 so now the state of your savings, after two months, is:

x_2=x_1+0.001x_1+50=(1+0.001)x_1+50,

and it shouldn’t be too difficult to see that how you get from x_i\longrightarrow x_{i+1} is by applying the function:

f(x)=(1+0.001)x+50.

Exercise

Use geometric series to find a formula for x_n.

Weather

If quantum effects are neglected, then weather is a deterministic system. This means that if we know the exact state of the weather at a certain instant (we can even think of the state of the universe – variations in the sun affecting the weather, etc), then we can calculate the state of the weather at all subsequent times.

This means that if we know everything about the state of the weather today at 12 noon, then we know what the weather will be at 12 noon tomorrow…

Read the rest of this entry »

%d bloggers like this: