Skip to main content

Posts

Why does Kaggle use Log-loss?

Recent posts

The Kelly Criterion and a Sure Thing

The Kelly Criterion is an alternative to standard utility theory, which seeks to maximize expected utility. Instead, the Kelly Criterion seeks to maximize expected growth. That is, if we start out with an initial bankroll \(B_0\), we seek to maximize \(\mathrm{E}[g(t)]\), where \(B_t = B_0\cdot e^{g(t)}\).
As a simple example, consider the following choice. We can have a sure $3000, or we can take the gamble of a \(\frac{4}{5}\) chance of $4000 and a \(\frac{1}{5}\) chance of $0. What does Kelly say?
Assume we have a current bankroll of \(B_0\). After the first choice we have \(B_1 = B_0+3000\), which we can write as \[\mathrm{E}[g(1)] = \log\left(\frac{B_0+3000}{B_0}\right);\]for the second choice we have \[\mathrm{E}[g(1)] = \frac{4}{5} \log\left(\frac{B_0+4000}{B_0}\right).\]And so we want to compare \(\log\left(\frac{B_0+3000}{B_0}\right)\) and \(\frac{4}{5} \log\left(\frac{B_0+4000}{B_0}\right)\).
Exponentiating, we're looking for the positive root of \[{\left({B_0+3000}\righ…

Prime Divisors of \(3^{32}-2^{32}\)

Find four prime divisors < 100 for \(3^{32}-2^{32}\).
Source: British Math Olympiad, 2006.

This factors nicely as \(3^{32}-2^{32} = \left(3^{16}+2^{16}\right)\left(3^{16}-2^{16}\right)\), and we can continue factoring in this way to get \[3^{32}-2^{32} = \left(3^{16}+2^{16}\right)\left(3^8+2^8\right)\left(3^4+2^4\right)\left(3^2+2^2\right)\left(3^2-2^2\right).\]The final three terms are \(5, 13, 97\), so we have three of the four required primes. For another prime divisor, consider \(3^{16}-2^{16}\). By Fermat's Little Theorem \(a^{16}-1\equiv 0 \bmod 17\) for all \(a\) with \((a,17)=1\), and so it follows that \(3^{16}-2^{16}\equiv 0 \bmod 17\), and we therefore have \(17\) as a fourth such prime divisor.
Alternatively, note \( \left(\dfrac{3}{17}\right)=-1, \left(\dfrac{2}{17}\right)=1\), hence by Euler's Criterion \(3^8\equiv -1 \bmod 17\) and \(2^8\equiv 1 \bmod 17\), giving \(3^8+2^8\equiv 0\bmod 17\).

Highest Powers of 3 and \(\left(1+\sqrt{2}\right)^n\)

Let \(\left(1+\sqrt{2}\right)^{2012}=a+b\sqrt{2}\), where \(a\) and \(b\) are integers. What is the greatest common divisor of \(b\) and \(81\)?
Source: 2011-2012 SDML High School 2a, problem 15.

Let \((1+\sqrt{2})^n = a_n + b_n \sqrt{2}\). I've thought about this some more, and there's a nice way to describe the highest power of \(3\) that divides \(b_n\). This is probably outside of the scope of the intended solution, however.

First note that \((1-\sqrt{2})^n = a_n - b_n \sqrt{2}\), and so from \((1+\sqrt{2})(1-\sqrt{2})=-1\) we get \((1+\sqrt{2})^n (1-\sqrt{2})^n = {(-1)}^n\). This gives \[{a_n}^2 - 2 {b_n}^2 = {(-1)}^n.\] Now define the highest power of a prime \(p\) that divides \(n\) to be \(\operatorname{\nu}_p(n)\).
From cubing and using the above result it's straightforward to prove that if \(\operatorname{\nu}_3(b_n) = k > 0\) then \(\operatorname{\nu}_3(b_{3n}) = k+1\).
Note \((1+\sqrt{2})^4 = 17 + 12\sqrt{2} \equiv -1+3\sqrt{2} \pmod{3^2}\). Cubing and using…

Sum of Two Odd Composite Numbers

What is the largest even integer that cannot be written as the sum of two odd composite numbers? Source: AIME 1984, problem 14.

Note \(24 = 3\cdot 3 + 3\cdot 5\), and so if \(2k\) has a representation as the sum of even multiples of 3 and 5, say \(2k = e_3\cdot 3 + e_5\cdot 5\), we get a representation of \(2k+24\) as a sum of odd composites via \(2k+24 = (3+e_3)\cdot 3 + (5+e_5)\cdot 5\). But by the Frobenius coin problem every number \(k > 3\cdot 5 -3-5 = 7\) has such a representation, hence every number \(2k > 14\) has a representation as the sum of even multiples of 3 and 5. Thus every number \(n > 24+14=38\) has a representation as the sum of odd composites. Checking, we see that \(\boxed{38}\) has no representation as a sum of odd composites.

What's the Value of a Win?

In a previous entry I demonstrated one simple way to estimate an exponent for the Pythagorean win expectation. Another nice consequence of a Pythagorean win expectation formula is that it also makes it simple to estimate the run value of a win in baseball, the point value of a win in basketball, the goal value of a win in hockey etc.

Let our Pythagorean win expectation formula be \[ w=\frac{P^e}{P^e+1},\] where \(w\) is the win fraction expectation, \(P\) is runs/allowed (or similar) and \(e\) is the Pythagorean exponent. How do we get an estimate for the run value of a win? The expected number of games won in a season with \(g\) games is \[W = g\cdot w = g\cdot \frac{P^e}{P^e+1},\] so for one estimate we only need to compute the value of the partial derivative \(\frac{\partial W}{\partial P}\) at \(P=1\). Note that \[ W = g\left( 1-\frac{1}{P^e+1}\right), \] and so \[ \frac{\partial W}{\partial P} = g\frac{eP^{e-1}}{(P^e+1)^2}\] and it follows \[ \frac{\partial W}{\partial P}(P=1) = …

A Simple Estimate for Pythagorean Exponents

Given the number of runs scored and runs allowed by a baseball team, what's a good estimate for that team's win fraction? Bill James famously came up with what he called the "Pythagorean expectation" \[w = \frac{R^2}{R^2 + A^2},\] which can also be written as \[w = \frac{{(R/A)}^2}{{(R/A)}^2 + 1}.\] More generally, if team \(i\) scores \(R_i\) and allows \(A_i\) runs, the Pythagorean estimate for the probability of team \(1\) beating team \(2\) is \[w = \frac{{(R_1/A_1)}^2}{{(R_1/A_1)}^2 + (R_2/A_2)^2}.\] We can see that the estimate of the team's win fraction is a consequence of this, as an average team would by definition have \(R_2 = A_2\). Now, there's nothing magical about the exponent being 2; it's a coincidence, and in fact is not even the "best" exponent. But what's a good way to estimate the exponent? Note the structural similarity of this win probability estimator and the Bradley-Terry estimator \[ w = \frac{P_1}{P_1+P_2}.\] Here t…