# Secret Santa Game

It is all in the PDF

Basically I had this problem in my head when I was in ANU, and now I finally have the chance to write down the problem in its most basic form.

I just thought it is a good R practice session.

Fun times! I was also watching a Paul Erdos documentary at the time. What an extraordinary human being he was!

# Still Not Significant

A must for a stats student starting research!

What to do if your p-value is just over the arbitrary threshold for ‘significance’ of p=0.05?

You don’t need to play the significance testing game – there are better methods, like quoting the effect size with a confidence interval – but if you do, the rules are simple: the result is either significant or it isn’t.

So if your p-value remains stubbornly higher than 0.05, you should call it ‘non-significant’ and write it up as such. The problem for many authors is that this just isn’t the answer they were looking for: publishing so-called ‘negative results’ is harder than ‘positive results’.

The solution is to apply the time-honoured tactic of circumlocution to disguise the non-significant result as something more interesting. The following list is culled from peer-reviewed journal articles in which (a) the authors set themselves the threshold of 0.05 for significance, (b) failed to achieve that threshold value for…

View original post 2,779 more words

# Look-And-Say Sequence

According to John Conway, this sequence was constructed and presented to him by one of his students. The construction is rather random, it involves reading the number left to right, and write down the number of consecutive numbers.

#### e.g. for the number “1211”, reading left to right, there are “one ‘1’, one ‘2’ and two ‘1’”, so the next  number is “111221”. Reading this number again, we get “three ‘1’, two ‘2’ and one ‘1’”. Hence the next number is 312211.

Here is a Mathematica code of how to construct and list such sequence:

 f[seed_] := Module[{a = seed}, s = Split[IntegerDigits[a]]; t = Map[Length, s]; u = Map[DeleteDuplicates, s] // Flatten; v = Riffle[t, u]; FromDigits[v] ]

n=50;

For[i = 1, i <= n, i++,
Subscript[a, 1] = 1;
Subscript[a, i + 1] = f[Subscript[a, i]];
]

table = Table[Subscript[a, i], {i, 1, n}]

One of the curious property of this sequence, is that, if we allow $L_n$ to denote the number of digits in the n-th Look-And-Say number, then the ratio $\frac{L_n+1}{L_{n}}$ tends to an number (Conway proved that this is an algebraic number, being a root of a polynomial): http://en.wikipedia.org/wiki/Look-and-say_sequence

 leng = IntegerLength[table] Ratios[leng] // N ListPlot[leng]

We see that the ratios tends towards the constant 1.303577269….

This piece code are so short, thanks for the many easy to use functions in Mathematica, such as IntegerDigits, FormDigits and Riffle.

# Dirichlet’s Approximation Theorem in Mathematica

The Dirichilet’s approximation Theorem is about using rational numbers to approximate any numbers. To state it formally:

If $\alpha \in \mathbb{R}, n \in \mathbb{Z}^+$, then there exist integer $a$ and $b$ with $1 \leq a \leq n$ such that $|a \alpha - b | < 1/n$.

I managed to write up a simple Mathematica code (when I say simple, it still took me about 1 hr to write up and satisfy with, I suck at programming)

 Clear["Global*"]

Declaring all the necessary variables first.
 \[Alpha] = E; n = 1000; seq = (Range[n + 1] - 1)*\[Alpha]; fracseq = FractionalPart[seq]; intervals = Partition[(Range[n + 1] - 1)/n, 2, 1]; found = 0; k = 1;

Just like in the proof of the Dirichlet Therorem, we created a sequence, which are the fractional part of first n integer multiples of alpha. The intervals are created in a similar way.

A loop to find the very first instance that we have “two piegeons in the same piegeonhole”.
 While[k < Length[intervals] && found == 0, If[ Total[Boole[IntervalMemberQ[Interval[intervals[[k]]], fracseq]]] > 1, found = 1, found = 0 ]; k++] 
This is just checking that we have the piegeons in the right place.

k - 1 Total[Boole[IntervalMemberQ[Interval[intervals[[k - 1]]], fracseq]]] intervals[[k - 1]]

13

2

{3/250, 13/1000}

We have a selection criterion here, to select the first two piegeons in the hole.

selectseqcriterion = Boole[IntervalMemberQ[Interval[intervals[[k - 1]]], fracseq]]; Pick[seq, selectseqcriterion, 1];

i = Pick[Range[n + 1] – 1, selectseqcriterion, 1][[1]];
j = Pick[Range[n + 1] – 1, selectseqcriterion, 1][[2]];

‘a’ and ‘b’ are the denominator and numerator of the rational approximation to the real number alpha.
 a = j - i b = Floor[j*\[Alpha]] - Floor[i*\[Alpha]]

536

1457

This is just a check that the function works.
 Abs[a*\[Alpha] - b] < 1/n Abs[\[Alpha] - b/a] <= 1/(a^2) N[Abs[\[Alpha] - b/a]]`

True

True

1.75363*10^-6

So this simple program works. The exercise and theorem came from Kenneth Rosen’s “Elementary Number Theory”, and it certainly a good exercise to do.

# Stability of Marriages

On 2014 May 22, I had the pleasure of doing a presentation for the Sydney University Mathematics Society (SUMS), the topic was on the “stability of relationships and college admission”. Most of the contents were based on a particular algorithm presented in this article in the 60’s (yes, the 60’s)

http://www.econ.ucsb.edu/~tedb/Courses/Ec100C/galeshapley.pdf

The basic motivation is: imagine a set of $n$ students who can bbe ranked (unambiguously) by $n$ universities. We can start pairing the students with their desired unis, even though not everyone can get their first preference.

Based on this set up, we wish to find stable and optimal paring between the students and universities. The precise definitions of “stable” and “optimal” can be found in the above link. And of course, this problem can be easily modified into a “boys propose to girls” romantic marriage problem.

My talk is much light-hearted, since I only had 5 minutes to explain everything, so I left out the crucial proof of the algorithm, and instead, I used an example to illustrate all the important features. (There is even an Alpha-Male pun in there).

In retrospect, everyone had a great laugh, so my efforts to conjure up jokes did pay off!

My Beamer slides can be found here: