# Chaitanya's Random Pages

## March 26, 2016

### Applying AM-GM in the denominator after flipping the sign

Filed under: mathematics — ckrao @ 8:44 pm

There are times when solving inequalities that one has a sum of fractions in which applying the AM-GM inequality to each denominator results in the wrong sign for the resulting expression.

For example (from [1], p18), if we wish to show that for real numbers $x_1, x_2, \ldots, x_n$ with sum $n$ that

$\displaystyle \sum_{i = 1}^n \frac{1}{x_i^2 + 1}\geq \frac{n}{2},$

we may write $x_i^2 + 1 \geq 2x_i$ (equivalent to $(x_i-1)^2 \geq 0$), but this implies $\frac{1}{x_i^2 + 1} \leq \frac{1}{2x_i}$ and so the sign goes the wrong way.

A way around this is to write

\begin{aligned} \frac{1}{x_i^2 + 1} &= 1 - \frac{x_i^2}{x_i^2 + 1}\\ &\geq 1 - \frac{x_i^2}{2x_i}\\ &= 1 - \frac{x_i}{2}. \end{aligned}

Summing this over $i$ then gives $\sum_{i=1}^n \frac{1}{x_i^2 + 1} \geq n - \sum_{i=1}^n (x_i/2) = n/2$ as desired.

Here are a few more examples demonstrating this technique.

2. (p9 of [2]) If $a,b,c$ are positive real numbers with $a + b + c = 3$, then

$\dfrac{a}{1 +b^2} + \dfrac{b}{1 +c^2} + \dfrac{c}{1 +a^2} \geq \dfrac{3}{2}.$

To prove this we write

\begin{aligned} \frac{a}{1 + b^2} &= a\left(1 - \frac{b^2}{1 + b^2}\right)\\ &\geq a\left(1 - \frac{b}{2}\right) \quad \text{(using the same argument as before)}\\ &=a - \frac{ab}{2}. \end{aligned}

Next we have $3(ab + bc + ca) \leq (a + b + c)^2 = 9$ as this is equivalent to $(a-b)^2 + (b-c)^2 + (c-a)^2 \geq 0$. This means $ab + bc + ca \leq 3$. Putting everything together,

\begin{aligned} \frac{a}{1 + b^2} + \frac{b}{1 + c^2} + \frac{c}{1 + a^2}&\geq \left( a - \frac{ab}{2} \right) + \left( b - \frac{bc}{2} \right) + \left( c - \frac{ca}{2} \right)\\ &= (a + b + c) - (ab + bc + ca)/2\\ &\geq 3 - 3/2\\ &=\frac{3}{2}, \end{aligned}

as required.

3. (based on p8 of [2]) If $x_i > 0$ for $i= 1, 2, \ldots, n$ and $\sum_{i = 1}^n x_i^2 = n$ then

$\displaystyle \sum_{i=1}^n \frac{1}{x_i^3 + 2} \geq \frac{n}{3}.$

By the AM-GM inequality, $x_i^3 + 2 = x_i^3 + 1 + 1 \geq 3x_i$, so

\begin{aligned} \frac{1}{x_i^3 + 2} &= \frac{1}{2}\left( 1 - \frac{x_i^3}{x_i^3 + 2} \right)\\ &\geq \frac{1}{2}\left( 1 - \frac{x_i^3}{3x_i} \right)\\ &= \frac{1}{2}\left( 1 - \frac{x_i^2}{3} \right). \end{aligned}

Summing this over $i$ gives

\begin{aligned} \sum_{i=1}^n \frac{1}{x_i^3 + 2} &\geq \frac{1}{2} \sum_{i=1}^n \left( 1 - \frac{x_i^2}{3} \right)\\ &= \frac{1}{2}\left( n - \frac{n}{3} \right)\\ &= \frac{n}{3}. \end{aligned}

4. (from [3]) If $x, y, z$ are positive, then

$\dfrac {x ^ 3}{x ^ 2 + y ^ 2} + \dfrac {y ^ 3}{y ^ 2 + z ^ 2} + \dfrac {z ^ 3}{z ^ 2 + x ^ 2 } \geq \dfrac {x + y + z}{2}.$

Once again, focusing on the denominator,

\begin{aligned} \dfrac {x ^ 3}{x ^ 2 + y ^ 2} &= x\left(1 - \dfrac {y ^ 2} {x ^ 2 + y ^ 2} \right)\\ &\geq x \left(1 -\dfrac{xy^2}{2xy} \right)\\ &= x-\dfrac{y}{2}. \end{aligned}

Hence,

\begin{aligned} \dfrac {x ^ 3}{x ^ 2 + y ^ 2} + \dfrac {y ^ 3}{y ^ 2 + z ^ 2} + \dfrac {z ^ 3}{z ^ 2 + x ^ 2 } &\geq x-\dfrac{y}{2} + y-\dfrac{z}{2} + z-\dfrac{x}{2}\\ &= \dfrac {x + y + z}{2}, \end{aligned}

as desired.

5. (from the 1991 Asian Pacific Maths Olympiad, see [4] for other solutions) Let $a_1, a_2, \ldots, a_n, b_1, b_2, \ldots, b_n$ be positive numbers with $\sum_{i = 1}^n a_i = \sum_{i = 1}^n b_i$. Then

$\displaystyle\sum_{i=1}^n\frac{a_i^2}{a_i + b_i} \geq \frac{1}{2}\sum_{i=1}^n a_i.$

Here we write

\begin{aligned} \sum_{i=1}^n\frac{a_i^2}{a_i + b_i} &= \sum_{i=1}^n a_i \left(1 - \frac{b_i}{a_i + b_i} \right)\\ &\geq \sum_{i=1}^n a_i \left(1 - \frac{b_i}{2\sqrt{a_i b_i}} \right) \\ &= \frac{1}{2} \sum_{i=1}^n \left( 2a_i - \sqrt{a_i b_i} \right) \\ &= \frac{1}{4} \sum_{i=1}^n \left( 4a_i - 2\sqrt{a_i b_i} \right)\\ &= \frac{1}{4} \sum_{i=1}^n \left( 2a_i +a_i - 2\sqrt{a_i b_i} + b_i \right) \quad \text{(as } \sum_{i=1}^n a_i = \sum_{i=1}^n b_i\text{)}\\ &= \frac{1}{4} \sum_{i=1}^n \left( 2a_i + \left(\sqrt{a_i} - \sqrt{b_i}\right)^2 \right)\\ &\geq \frac{1}{4} \sum_{i=1}^n 2a_i\\ &= \frac{1}{2} \sum_{i=1}^n a_i, \end{aligned}

as required.

#### References

[1] Zdravko Cvetkovski, Inequalities: Theorems, Techniques and Selected Problems, Springer, 2012.

[2] Wang and Kadaveru, Advanced Topics in Inequalities, available from http://www.artofproblemsolving.com/community/q1h1060665p4590952

[3] Cauchy Reverse Technique: https://translate.google.com.au/translate?hl=en&sl=ja&u=http://mathtrain.jp/crt&prev=search

## February 28, 2016

### The race up the charts for two recent movies

Filed under: movies and TV — ckrao @ 7:59 pm

In recent times Jurassic World and Star Wars VII (The Force Awakens) have respectively become the fourth and third biggest movies of all time worldwide (behind Avatar and Titanic). Here is how they ranked in the all-time US/Canada charts day by day (using data from boxofficemojo.com).

 Day Jurassic World Star Wars: The Force Awakens 1 786 464 2 275 183 3 143 96 4 108 68 5 79 40 6 69 29 7 54 22 8 37 11 9 28 6 10 18 5 11 15 5 12 11 5 13 10 4 14 9 3 15 7 2 16-19 5 2 20-21 5 1 22-44 4 1 45+ 3 1

I was amazed by Jurassic World’s summer run and then that of The Force Awakens simply blew my mind. 🙂

## February 27, 2016

### Cutting a triangle in half

Filed under: mathematics — ckrao @ 9:40 pm

Here is a cute triangle result that I’m surprised I had not known previously. If we are given a point on one of the sides of a triangle, how do we find a line through the triangle that cuts its area in half?

Clearly if that point is either a midpoint or one of the vertices, the answer is a median of the triangle. A median cuts a triangle in half since the two pieces have the same length side and equal height.

So what if the point is not a midpoint or a vertex? Referring to the diagram below, if $P$ is our desired point closer to $A$ than $B$, the end point $Q$ of the area-bisecting segment would need to be on side $BC$ so that area(BPQ) = area(ABC)/2.

In other words, we require area(BPQ) = area(BDQ), or, subtracting the areas of triangle BDQ from both sides,

$\displaystyle |DPQ| = |DCQ|.$

Since these two triangles share the common base $DQ$, this tells us that we require them to have the same height. In other words, we require $CP$ to be parallel to $DQ$. This tells us how to construct the point $Q$ given $P$ on $AB$:

1. Construct the midpoint D of $AB$.
2. Draw $DQ$ parallel to $AP$.

See [1] for an animation of this construction.

In turns out that the set of all area-bisecting lines are tangent to three hyperbolas and enclose a deltoid of area $(3/4)\ln(2) - 1/2 \approx 0.01986$ times the original triangle. [2,3,4]

#### References

[1] Jaime Rangel-Mondragon, “Bisecting a Triangle” http://demonstrations.wolfram.com/BisectingATriangle/ from the Wolfram Demonstrations Project Published: July 10, 2013

[4] Henry Bottomley, Area bisectors of a triangle, January 2002

## January 31, 2016

### Most wickets after n test matches from debut

Filed under: cricket,sport — ckrao @ 12:18 am

Here is a list of the leading test cricket wicket takers after playing n matches. A few current-day players feature and I hope to update this list over time (last updated January 31 2016). It was created largely manually using ESPNCricinfo’s Statsguru starting from [1] and [2], and using lists of the fastest to multiples of 50 wickets here.  Corrections are more than welcome (updated: November 27 2017).

#### References

[1] Most wkts in consec Tests from debut – Google Groups

[2] Top 10 bowlers with most wickets in 10 Tests or less (crictracker.com)

## January 30, 2016

### Patterns early in the digits of pi

Filed under: mathematics — ckrao @ 8:59 pm

Recently when taking a look at the early decimal digits of $\pi$ I made the following observations:

3.141592653589793238462643383279502884197169399375105820974944592307816406286…

• The first run of seven distinct digits (8327950, shown underlined) appears in the 26th to 32nd decimal place. Curiously the third such run (5923078, also underlined) in decimal places 61 to 67 contains the same seven digits. (There is also a run of seven distinct digits in places 51 to 57 with 5820974.)
• Decimal digits 60 to 69 (shown in bold) are distinct (i.e. all digits are represented once in this streak). The same is true for digits 61 to 70 as both digits 60 and 70 are ‘4’.

Assume the digits of $\pi$ are generated independently from a uniform distribution. Firstly, how often would we expect to see a run of 7 distinct digits? Places $k$ to $k+6$ are distinct with probability

$\displaystyle \frac{9}{10} \times \frac{8}{10} \times \frac{7}{10} \times \frac{6}{10} \times \frac{5}{10} \times \frac{4}{10} = \frac{9!}{3.10^6} = \frac{189}{3125}.$

Hence we expect runs of 7 distinct digits to appear $3125/189 \approx 16.5$ places apart. This includes the possibility of runs such as 12345678 which contain two runs of 7 distinct digits that are only 1 place apart.

How often would we expect to see the same 7 digits appearing in a run as we did in places 26-32 and 61-67? Furthermore let’s assume the two runs have no overlap, so we discount possibilities such as 12345678 which have a six-digit overlap. We expect a given sequence (e.g. 1234567, in that order) to appear $1/10^7$ of the time. There are $7! = 5040$ permutations of such a sequence, but of these $1$ has overlap 6 (2345671), $2!$ has overlap 5 (3456712 or 3456721), $3!$ has overlap 4, …, $6!$ has overlap 1 with the original sequence. This leaves us with $5040 - (1 + 2 + 6 + 24 + 120 + 720) = 4167$ possible choices of the next run to have the same 7 digits but non-overlapping (or to appear in precisely the same order – overlap 7). Hence we expect the same 7 digits to recur (no overlap with the original run) after approximately $10^7/4167 \approx 2400$ places apart so what we saw in the first 100 places was remarkable.

Now let us turn to runs of all ten distinct digits. Repeating the argument above, such runs occur every $10^{10}/10! \approx 2756$ places. According to [1] the next time we see ten distinct digits is in decimal places 5470 to 5479.

To answer the question of when we would expect to see the first occurrence of ten distinct digits, we adopt an argument from renewal-reward theory based on Sec 7.9.2 of [2] (there also exist approaches based on setting up recurrence relations, or martingale theory (modelling a fair casino), see [3]-[4]). Firstly we let $T$ be the first time we get 10 consecutive distinct values – we wish to find $E[T]$ where $E$ denotes the expected value operator. Note that this will be more than the 2756 answer we obtained above since we make no assumption of starting with a run of ten distinct digits – there is no way $T$ could be 1 for example, but we could have two runs of ten distinct digits that are 1 apart.

From a sequence of digits we first define a renewal process in which after we get 10 consecutive distinct values (at time $T$) we start over and wait for the next run of 10 consecutive distinct values without using any of the values  up to time $T$. Such a process will then have an expected length of cycle of $E[T]$.

Next, suppose we earn a reward of $1 every time the last 10 digits of the sequence are distinct (so we would have obtained$1 at each of decimal places 69 and 70 in the $\pi$ example). By an important result in renewal-reward theory, the long run average reward is equal to the expected reward in a cycle divided by the expected length of a cycle.

In a cycle we will obtain

• $1 at the end •$1 at time 1 in the cycle with probability $1/10$ (if that digit is the same as ten digits before it)
• $1 at time 2 in the cycle with probability $2/100$ (if the last two digits match those ten places before it) •$1 at time 9 in the cycle with probability $9!/10^9$ (if the last nine digits match those ten places before it)

Hence the expected reward in a cycle is given by

$\displaystyle 1 + \sum_{i=1}^9 \frac{i!}{10^i} = \sum_{i=0}^9 \frac{i!}{10^i}.$

We have already seen that the long run average reward is $10!/10^{10}$ at each decimal place. Hence the expected length of a cycle $E[T]$ (i.e. the expected number of digits before we expect the first run of ten consecutive digits) is given by

$\frac{10^{10}}{10!}\sum_{i=0}^9 \frac{i!}{10^i} \approx 3118.$

Hence it is pretty cool that we see it so early in the decimal digits of $\pi$. 🙂

#### References

[2] S. Ross, Introduction to Probability Models, Academic Press, 2014.

[4] A Collection of Dice Problemsmadandmoonly.com

## December 30, 2015

### Novak Djokovic against younger players

Filed under: sport — ckrao @ 9:11 pm

#### Reference

[1] Răzvan Gelca and Titu Andreescu, Putnam and Beyond, Springer, 2007.

## October 31, 2015

### Highest ODI batting averages over 100 consecutive innings

Filed under: cricket,sport — ckrao @ 11:13 am

The 3 centuries by A B de Villiers in the most recent ODI series against India has given him a sizeable lead over the rest in the following list of highest batting averages in 100 consecutive one day international cricket innings. On 92 out of those 100 innings he came in at number 4 or lower (and never opened in that time span), and still he managed to score over 54 runs per innings. All of his ODI hundreds to date have been scored at a strike rate of at least 100. Some very impressive numbers have been posted for other batsmen in the list too.

 Player Innings Not out Runs HS Average Balls faced Strike rate 100s 50s 0s Time period de Villiers* 100 21 5454 162* 69.04 4935 110.52 20 27 1 Nov 09-Oct 15 Bevan 100 40 3726 108* 62.10 4844 76.92 3 26 2 Sep 94-Aug 99 Dhoni* 100 34 4027 139* 61.02 4587 87.79 5 28 2 Feb 09-Jan 14 Amla* 100 7 5388 159 57.94 5991 89.93 20 27 2 Nov 08-Mar 15 Richards 100 19 4611 189* 56.93 5103 90.36 8 34 4 Jun 75-Nov 86 Kohli* 100 16 4668 183 55.57 5016 93.06 17 21 7 Mar 11-Mar 15 Tendulkar 100 11 4789 186* 53.81 5273 90.82 18 16 5 Apr 98-Jun 02 Hussey 100 33 3574 109* 53.34 4114 86.87 2 27 2 Feb 05-Nov 09 Jones 100 19 4317 145 53.30 5667 76.18 7 32 1 Jan 85-Feb 91 Sangakkara 100 10 4736 169 52.62 5417 87.43 14 28 5 Aug 11-Mar 15 Chanderpaul 100 21 4144 149* 52.46 5627 73.64 8 30 2 Sep 04-Jun 10 Lara 100 11 4575 169 51.40 5738 79.73 11 30 3 Mar 92-Dec 97 Kallis 100 21 4044 139 51.19 5474 73.88 7 27 3 Mar 00-Feb 04 Ponting 100 11 4397 164 49.40 5068 86.76 11 29 4 Nov 03-Dec 07 Greenidge 100 11 4382 133* 49.24 6583 66.57 10 27 3 Dec 75-Dec 85

Statistics are from ESPN Cricinfo. I would be interested to know if there are others who averaged 50+ over 100 consecutive ODI innings.

« Previous PageNext Page »

Create a free website or blog at WordPress.com.