Chaitanya's Random Pages

October 30, 2014

Mountain ranges of the world

Filed under: geography — ckrao @ 1:06 pm

As a geography lesson for myself, here is a list of major mountain ranges of the world, where those that are either long or have a significantly high peak are shown (hence several near Tibet are given). Maps are shown below the table.

 

Continent Name of Range Countries spanned Length (km) Name of Highest Peak Elevation of highest peak (m)
Antarctica Transantarctic 3500 Kirkpatrick 4528
Oceania Southern Alps New Zealand 350 Aoraki (Cook) 3724
Great Dividing Range Australia 3000 Kosciuszko 2228
New Guinea Highlands Indonesia, Papua New Guinea 1600 Puncak Jaya 4884
Africa Drakensberg South Africa, Lesotho 1000 Thabana Ntlenyana 3482
Ethiopian Highlands Ethiopia, Eritrea 1500 Ras Dashan 4533
Atlas Morocco, Algeria, Tunisia 2400 Jbel Toubkal 4167
Asia Himalayas Bhutan, China, India, Nepal, Pakistan 2400 Everest 8849
Karakoram Pakistan, India, China 500 K2 8611
Hindu Kush Afghanistan, Pakistan 1200 Tirich Mir 7690
Pamir Tajikistan, Krygyzstan, Afghanistan, Pakistan, China ~500 Ismoil Somoni Peak 7495
Tian Shan China, Pakistan, India, Kazakhstan, Kyrgyzstan, Uzbekistan 1500 Jengish Chokusu 7439
Kunlun China, India 3000 Kongur Tagh 7649
Altun China 800 Sulamutag Feng 6245
Altai Russia, China, Mongolia, Kazakhstan 2000 Belhuka 4506
Sayan Mongolia, Russia 1500 Mounkou 3492
Verkhoyansk Russia 1200 Mus-Khaya 2959
Sredinny Russia 900 Ichinsky 3607
Hengduan China, Myanmar 800 Gongga 7556
Qin China 500 Taibai 3767
Taihang China 400 Wutai 3061
Arakan Myanmar 1000 Victoria 3094
Annamite Laos, Vietnam, Cambodia 1100 Ngoc Pan 2598
Barisan Indonesia 1700 Kerinci 3800
Western Ghats India 1600 Anamudi 2695
Eastern Ghats India 1300 Arma Konda 1680
Zagros Iran, Iraq, Turkey 1500 Zard Kuh 4548
Alborz Iran 600 Damavand 5671
Caucasus Russia, Georgia, Azerbaijan, Armenia, Turkey 1100 Elbrus 5642
Yemen Highlands Yemen, Saudi Arabia 1500 Jabal an Nabi Shu’ayb 3666
Pontic Turkey 1000 Kackar Dagi 3492
Taurus Turkey 600 Demirkazik 3756
Asia/Europe Ural Russia, Kazakhstan 2500 Narodnaya 1895
Europe Kjølen Norway, Sweden, Finland 1700 Galdhøpiggen 2469
Alps Germany, Austria, France, Italy, Liechtenstein, Monaco, Slovenia, Switzerland 1200 Blanc 4811
Pyrenees France, Spain, Andorra 430 Aneto 3404
Apennines Italy, San Marino 1200 Corno Grande 2912
Carpathians Austria, Slovakia, Poland, Czech Republic, Hungary, Romania, Ukraine, Serbia 1500 Gerlachovsky stit 2655
North America Arctic Canada 1000 Barbeau Peak 2616
Brooks USA, Canada 1100 Mount Chamberlin 2749
Aleutian USA 1000 Redoubt 2788
Alaskan USA 650 McKinley 6194
Rocky USA, Canada 4800 Elbert 4401
Coast USA, Canada 1600 Waddington 4019
Cascade USA, Canada 1100 Rainier 4392
Sierra Nevada USA 650 Whitney 4421
Appalachian USA, Canada 2400 Mitchell 2037
Sierra Madre Occidental Mexico 1250 Cerro Mohinora 3250
Sierra Madre Oriental Mexico 1250 Cerro San Rafael 3700
Sierra Madre del Sur Mexico 1000 Teotepec 3703
Sierra Madre Chiapas Mexico, Guatemala, El Salvador, Honduras 600 Tajumulco 4220
 South America Andes Venezuela, Colombia, Ecuador, Peru, Bolivia, Chile, Argentina 7000 Aconcagua 6962
Serra do Mar Brazil 1500 Pico Maior de Friburgo 2316

Maps

References

October 25, 2014

An integral related to Bessel polynomials

Filed under: mathematics — ckrao @ 12:46 am

In this post I want to share this cute result that I learned recently:

\displaystyle \int_{-\infty}^{\infty} \frac{\cos x}{x^2+1}\ dx = \int_{-\infty}^{\infty} \frac{\cos x}{(x^2+1)^2}\ dx = \frac{\pi}{e} \quad\quad (1)

Let us see how the first integral is derived and then generalised. The integrand has poles at \pm i in the complex plane and we may apply contour integration to proceed. Note that as \sin x /(x^2+1) is an odd function, \int_{-\infty}^{\infty} \sin x /(x^2+1)\ dx = 0 and so

\int_{-\infty}^{\infty}\frac{\cos x}{x^2+1}\ dx = \int_{-\infty}^{\infty} \frac{e^{ix}}{x^2+1}.\quad\quad(2)

It therefore suffices to consider the integrand f(z) = e^{iz}/(z^2+1). We consider the semicircular contour of radius R (to be traversed anticlockwise) in the upper half plane centred at 0. It encloses the pole at i.

semicircular contour

Along this closed contour we use the residue theorem to compute

\begin{aligned}  \oint f(z)\ dz &= 2\pi i \text{Res}[f(z)]_{z=i}\\  &= 2\pi i \lim_{z \rightarrow i} (z-i)\frac{e^{iz}}{z^2 +1}\\  &= 2\pi i \lim_{z \rightarrow i} \frac{e^{iz}}{z +i}\\  &= 2\pi i \frac{e^{-1}}{2i}\\  &= \frac{\pi}{e}.\quad\quad (3)  \end{aligned}

On the semicircular arc z = R(\cos \theta + i\sin \theta) = Re^{i\theta} for 0 \leq \theta \leq \pi and so

\begin{aligned}  |f(z)| &= \left| \frac{e^{iz}}{z^2+1} \right|\\  &= \frac{|e^{iR(\cos \theta + i\sin \theta)}|}{|R^2 e^{i2\theta} + 1|}\\  &= \frac{|e^{-R \sin \theta}|}{|R^2 e^{i2\theta} + 1|}\\  &\leq \frac{e^{-R\sin \theta}}{R^2-1}\\  &\leq \frac{1}{R^2-1} \quad \text{for } 0 \leq \theta \leq \pi,\quad\quad (4)  \end{aligned}

where in the second last step we use the fact that distance to the origin of a circle of radius R^2 centred at -1 is at least R^2-1. Then

\begin{aligned}  \lim_{R \rightarrow \infty} \int_C f(z)\ dz &\leq \lim_{R \rightarrow \infty} \int_C |f(z)| \ |dz| \\  &\leq \lim_{R \rightarrow \infty} \pi R \sup_{z \in C} |f(z)|\\  &\leq \lim_{R \rightarrow \infty} \pi R \frac{1}{R^2-1} \quad \text{(by (4))}\\  &= 0.\quad\quad(5)  \end{aligned}

It follows that \lim_{R \rightarrow \infty} \int_C f(z)\ dz = 0 and we are left with

\begin{aligned}  \int_{-\infty}^{\infty} \frac{e^{ix}}{x^2+1}\ dx &= \lim_{R \rightarrow \infty} \int_{-R}^R f(z)\ dz \\  &= \lim_{R \rightarrow \infty} \oint f(z)\ dz - \int_C f(z) \ dz\\  &= \lim_{R \rightarrow \infty} \oint f(z)\ dz\\  &= \frac{\pi}{e} \quad\text{(by (3)).}\quad \quad(6)  \end{aligned}

To generalize this result to integrals of the form \int_{-\infty}^{\infty} \frac{\cos x}{(x^2+1)^{n+1}}\ dx = \int_{-\infty}^{\infty} \frac{e^{ix}}{(x^2+1)^{n+1}}\ dx for non-negative integers n, we choose the same contour as above and use the residue limit formula for poles of order (n+1):

\displaystyle \text{Res} [f(z)]_{z=z_0} = \frac{1}{n!} \lim_{z \rightarrow z_0} \left[\frac{d^n}{dz^n} (z-z_0)^{n+1} f(z) \right]. \quad\quad (7)

To apply (7) we make use of the General Leibniz rule for the n‘th derivative of a product:

\displaystyle (fg)^{(n)} = \sum_{k=0}^n \binom{n}{k} f^{(k)} g^{(n-k)}.\quad \quad (8)

Hence

\begin{aligned}  \oint \frac{e^{iz}}{(z^2+1)^{n+1}}\ dz &= 2\pi i \text{Res} \left[ \frac{e^{iz}}{(z^2+1)^{n+1}} \right]_{z=i}\\  &= \frac{2\pi i}{n!} \left[\frac{d^n}{dz^n}\frac{e^{iz}}{(z+i)^{n+1}} \right]_{z=i}\\  &= \frac{2\pi i}{n!} \sum_{k=0}^n \left[\binom{n}{k}\left(e^{iz}\right)^{(n-k)} \left(\frac{1}{(z+i)^{n+1}}\right)^{(k)}\right]_{z=i} \quad\text{(applying (8))}\\  &= \frac{2\pi i}{n!} \sum_{k=0}^n \binom{n}{k} (i)^{n-k} e^{-1} (-n-1)(-n-2)\ldots (-n-k) \frac{1}{(2i)^{n+k+1}}\\  &= \frac{2\pi i}{n!e} \sum_{k=0}^n \binom{n}{k}\frac{1}{i^{2k+1}}\frac{(n+k)!}{n!}(-1)^k\\  &= \frac{\pi}{n!e} \sum_{k=0}^n \frac{n!}{k!(n-k)!}\frac{(n+k)!}{n!}\frac{1}{2^{n+k}}\\  &= \frac{\pi}{e} \frac{1}{2^n n!}\sum_{k=0}^n \frac{(n+k)!}{k!(n-k)!}\frac{1}{2^k}\\  &= \frac{\pi}{e} \frac{1}{2^n n!} y_n(1), \quad\quad(8)\end{aligned}

where y_n(x) is the n‘th order Bessel polynomial defined by

\displaystyle y_n(x) = \sum_{k=0}^n \frac{(n+k)!}{k!(n-k)!} \left(\frac{x}{2}\right)^k.\quad\quad(9)

For example, for n = 1, the integral is given by

\begin{aligned} 2\pi i \left[ \frac{d}{dz} \frac{e^{iz}}{(z+i)^2}\right]_{z=i} &= \left[ \frac{-2e^{iz}}{(z+i)^3} + \frac{ie^{iz}}{(z+i)^2}\right]_{z=i}\\ &= 2\pi i\left(\frac{-2e^{-1}}{8i^3} + \frac{ie^{-1}}{-4}\right)\\ &= \frac{\pi}{e}. \quad\quad (10)\end{aligned}

The general sum in (8) can be also be written as

\displaystyle \sum_{k=0}^n \frac{(k+n)!}{2^k k!(n-k)!} = e \sqrt{\frac{2}{\pi}}K_{n+1/2}(1),\quad \quad (11)

where K_{\alpha}(x) is the modified Bessel function of the second kind.

Proceeding similarly to (4), \left| e^{iz}/(1+z^2)^{n+1} \right| \leq 1/(R^2-1)^{n+1} and so similar to (5)  the integral on the arc converges to 0 as R \rightarrow \infty. Hence following the same argument as in (6) the desired line integral along the real axis is equal to the contour integral in (8).

Evaluating (8) for n = 0, 1, 2,3,4,5,\ldots the first terms of  (e/\pi)\int_{-\infty}^{\infty} \frac{\cos x}{(x^2+1)^2}\ dx are given by

\displaystyle \frac{1}{1}, \frac{2}{2}, \frac{7}{8}, \frac{37}{48}, \frac{266}{384}, \frac{2431}{3840}, \cdots\quad\quad(12)

In this sequence a_n/b_n, the denominators b_n are related to the previous ones by multiplication by 2n, while curiously the numerators are related by the second order recurrence

a_{n} = (2n-1)a_{n-1} + a_{n-2}.\quad\quad(13)

This follows from the following recurrence relation for the Bessel polynomials:

y_n(x) = (2n-1)xy_{n-1}(x) + y_{n-2}(x).\quad\quad (14)

This can be proved using (9). We have

\begin{aligned}  (2n-1)xy_{n-1}(x) + y_{n-2}(x) &= (2n-1)x\sum_{k=0}^{n-1} \frac{(n+k)!}{k!(n-k)!} \left(\frac{x}{2}\right)^k + \sum_{k=0}^{n-2} \frac{(n+k)!}{k!(n-k)!} \left(\frac{x}{2}\right)^k\\  &=(2n-1)\sum_{k=1}^n \frac{(n+k-2)!}{(k-1)!(n-k)!}2\frac{x^k}{2^k}  + \sum_{k=0}^{n-2} \frac{(n+k-2)!}{k!(n-2-k)!}\left(\frac{x}{2}\right)^k\\  &= \frac{(n-2)!}{0!(n-2)!} + \sum_{k=1}^{n-2} (n+k-2)! \left[  \frac{2(2n-1)}{(k-1)!(n-k)!} + \frac{1}{k!(n-k-2)!}\right] \left(\frac{x}{2}\right)^k \\  & \quad \quad + (2n-1) \left[\frac{n + n -1-2)!}{(n-2)!1!}2 \left(\frac{x}{2}\right)^{n-1} + \frac{(2n-2)!}{(n-1)!0!}2\left(\frac{x}{2}\right)^n\right]\\  &= 1 + \sum_{k=1}^{n-2} (n+k-2)! \left[\frac{2(2n-1)k + (n-k-1)(n-k)}{k!(n-k)!}\right]\left(\frac{x}{2}\right)^k\\  & \quad \quad + (2n-1) \left[ \frac{(2n-3)!}{(n-2)!}2\left(\frac{x}{2}\right)^{n-1} + \frac{(2n-2)!}{(n-1)!}2\left(\frac{x}{2}\right)^n\right].\quad\quad(15)  \end{aligned}

Now

\begin{aligned}  2(2n-1)k + (n-k-1)(n-k) &= 2k(2n-1) + (n + k - 1 - 2k)(n-k)\\  &= 2k(2n-1-n+k) + (n+k-1)(n-k)\\  &= (n+k-1)(2k + n-k)\\  &= (n+k-1)(n+k).\quad\quad(16)  \end{aligned}

Substituting this into (15),

\begin{aligned}  (2n-1)xy_{n-1}(x) + y_{n-2}(x) &= 1 + \sum_{k=1}^{n-2}\frac{(n+k)!}{k!(n-k)!}\left(\frac{x}{2}\right)^k + \frac{(2n-1)!(n-1)2}{(n-1)!(2n-2)}\left(\frac{x}{2}\right)^{n-1} + \frac{(2n)!n2}{n! 2n}\left(\frac{x}{2}\right)^{n}\\  &= \sum_{k=0}^n \frac{(n+k)!}{k!(n-k)!}\left(\frac{x}{2}\right)^k\\  &= y_n(x),  \end{aligned}

thus verifying (14).

September 25, 2014

Players with low test cricket + one day international cricket bowling averages

Filed under: cricket,sport — ckrao @ 8:40 pm

Recently I pointed out players with high sum of test cricket and one day cricket batting averages. This time I shall look at those with a low sum of bowling averages.

Amongst former players Joel Garner heads the list while many big names are here. It’s a shame Shane Bond wasn’t able to play more. This first list shows those with a bowling average sum below 50.

Former players

Test cricket One day international cricket
Player Matches Wickets Average Matches Wickets Average Economy Rate Test Average + ODI Average
J Garner 58 259 20.97 98 146 18.84 3.09 39.81
SE Bond 18 87 22.09 82 147 20.88 4.28 42.97
GD McGrath 124 563 21.64 250 381 22.02 3.88 43.66
Sir RJ Hadlee 86 431 22.29 115 158 21.56 3.3 43.85
CEH Croft 27 125 23.30 19 30 20.66 3.47 43.96
AA Donald 72 330 22.25 164 272 21.78 4.29 44.03
DK Lillee 70 355 23.92 63 103 20.82 3.58 44.74
MA Holding 60 249 23.68 102 142 21.36 3.32 45.04
CEL Ambrose 98 405 20.99 176 225 24.12 3.48 45.11
M Muralitharan 133 800 22.72 350 534 23.08 3.93 45.80
Sir AME Roberts 47 202 25.61 56 87 20.35 3.4 45.96
Wasim Akram 104 414 23.62 356 502 23.52 3.89 47.14
Waqar Younis 87 373 23.56 262 416 23.84 4.68 47.40
SM Pollock 108 421 23.11 303 393 24.50 3.67 47.61
MD Marshall 81 376 20.94 136 157 26.96 3.53 47.90
DL Underwood 86 297 25.83 26 32 22.93 3.44 48.76
Imran Khan 88 362 22.81 175 182 26.61 3.89 49.42
RGD Willis 90 325 25.20 64 80 24.60 3.28 49.80
DE Bollinger 12 50 25.92 39 62 23.90 4.57 49.82

 

Among current players with over 50 wickets in both forms of the game only Dale Steyn would qualify for the above list. The list below contains those current players with bowling averages below 30 in both test and ODI cricket.

Current players

 

Test cricket One day international cricket
Player Matches Wickets Average Matches Wickets Average Economy Rate Test Average + ODI Average
RJ Harris 24 103 22.56 21 44 18.90 4.84 41.46
VD Philander 26 115 21.57 15 17 26.05 4.37 47.62
DW Steyn 75 383 22.56 87 135 25.62 4.82 48.18
Saeed Ajmal 35 178 28.10 111 183 22.18 4.13 50.28
KAJ Roach 28 111 25.98 64 98 26.85 4.90 52.83
MG Johnson 59 264 27.42 140 212 26.11 4.84 53.53
M Morkel 59 204 29.90 80 135 24.28 4.88 54.18
ST Finn 23 90 29.40 42 62 28.41 4.74 57.81
SCJ Broad 74 264 29.90 108 168 28.37 5.22 58.27
JM Anderson 99 380 29.72 184 257 29.10 4.94 58.82

Statistics are current to 25 Sep 2014 and are from ESPN Cricinfo here and here. I located current players using Statsguru via this query.

September 15, 2014

A good simple approximation of the complementary error function

Filed under: mathematics — ckrao @ 12:12 pm

I learnt from [1] that the complementary error function \displaystyle \text{erfc}(x) = \sqrt{\frac{2}{\pi}}\int_x^{\infty}e^{-t^2}\ dt can be well approximated as follows for positive x:

\displaystyle \text{erfc}(x) \approx \exp(-c_1x-c_2x^2), x > 0

where

\displaystyle c_1=1.09500814703333, \quad c_2=0.75651138383854.

As mentioned in [2], this approximation is found by applying the non-linear least squares method to estimate the parameters c_1, c_2 based on 500 points equally spaced in the interval [0,5].

The graphs below show how well this approximation holds across positive x. By symmetry one could use 2-\exp(c_1x-c_2x^2) as an approximation of \text{erfc}(x) for negative x.

erfc_approx

approx-erfcOnly two parameters are needed, but each were specified to 14 decimal places in to obtain the accuracy (maximum error just over 0.002) seen here. Such an approximation would be useful for working with functions (e.g. products) of error functions  (see [1] for an example).

References

[1] Product of two complementary error functions (erfc) – Mathematics Stack Exchange.

[2] W.-J. Tsay, C.J. Huang, T.-T. Fu, I-L. Ho, Maximum Likelihood Estimation of Censored Stochastic Frontier Models: An Application to the Three-Stage DEA Method, No 09-A003, IEAS Working Paper : academic research from Institute of Economics, Academia Sinica, Taipei, Taiwan. Available at http://econ.ccu.edu.tw/academic/master_paper/090323seminar.pdf.

 

August 31, 2014

Players with high test cricket + one day international cricket batting averages

Filed under: cricket,sport — ckrao @ 8:10 am

Jacques Kallis recently retired from international cricket with a phenomenal record of close to 25,000 runs, almost 600 wickets and 300+ catches on the international stage. He ended up with batting averages of 55.37 in test cricket and 44.36 in one day internationals (ODIs), leading to a sum just shy of 100. In turns out this is the highest sum of averages for any retired player who has played both of these forms of the game, just ahead of Michael Hussey (not counting players with a small number of innings).

The following tables show current and former players with a sum of test and ODI batting average above 90. Sangakkara has improved his numbers in both formats dramatically in recent years while Amla and de Villiers are the only players with sum exceeding 100. Statistics are current to August 30 2014.

 

Current players

Test cricket One day international cricket
Player Innings Runs Average Innings Runs Average Strike Rate Test Average + ODI Average
HM Amla 137 6415 51.32 89 4539 55.35 89.84 106.67
AB de Villiers 159 7296 51.02 159 6701 50.38 95.04 101.40
KC Sangakkara 221 11988 58.76 357 12844 40.14 77.55 98.90
IJL Trott 87 3763 46.45 65 2819 51.25 77.06 97.71
MJ Clarke 180 8240 51.50 215 7683 44.67 78.76 96.17
S Chanderpaul 266 11414 51.88 251 8778 41.60 70.74 93.48
MS Dhoni 140 4808 38.46 215 8098 53.28 89.31 91.74
V Kohli 51 1855 39.47 128 5674 51.58 89.75 91.05
AD Mathews 74 3054 52.66 111 3013 38.14 84.06 90.79
Misbah-ul-Haq 84 3285 46.93 136 4594 43.75 73.82 90.68

(NB: Fawad Alam would qualify but only played 3 test matches.)

 

Former players

Test cricket One day international cricket
Player Innings Runs Average Innings Runs Average Strike Rate Test Average + ODI Average
DG Bradman 80 6996 99.94 Bradman predated ODI cricket 99.94
JH Kallis 280 13289 55.37 314 11579 44.36 72.89 99.73
MEK Hussey 137 6235 51.53 157 5442 48.16 87.16 99.69
SR Tendulkar 329 15921 53.79 452 18426 44.83 86.23 98.62
IVA Richards 182 8540 50.24 167 6721 47.00 90.20 97.24
ML Hayden 184 8625 50.74 155 6133 43.81 78.96 94.54
Javed Miandad 189 8832 52.57 218 7381 41.70 67.01 94.27
GS Chappell 151 7110 53.86 72 2331 40.19 75.70 94.05
Mohammad Yousuf 156 7530 52.29 273 9720 41.72 75.10 94.01
RT Ponting 287 13378 51.85 365 13704 42.04 80.39 93.89
BC Lara 232 11953 52.89 289 10405 40.49 79.51 93.38
Zaheer Abbas 124 5062 44.80 60 2572 47.63 84.80 92.43
GM Turner 73 2991 44.64 40 1598 47.00 68.05 91.64
R Dravid 286 13288 52.31 318 10889 39.17 71.24 91.48
DM Jones 89 3631 46.55 161 6068 44.62 72.56 91.17

The above statistics are from ESPN Cricinfo here and here.

August 30, 2014

Waiting times and the size biased distribution

Filed under: mathematics — ckrao @ 12:48 pm

Suppose buses arrive at a stop after independent random intervals of T minutes, where T is uniformly distributed between 10 and 20. It is natural to wonder how long one is expected to wait from some random point in time t until the first bus arrives. For example on the one hand the bus could arrive immediately, or one could be unlucky with time t just after the previous bus left and we could wait as many as 20 minutes for the next bus. Interestingly this waiting time W is no longer uniformly distributed.

In general if interarrival times T have (cumulative) distributive function F_T and mean \mathbb{E}[T], the following is true.

The probability density of waiting time is f_W(x) = \text{Pr}(T \geq x)/\mathbb{E}[T] = (1-F_T(x))/\mathbb{E}[T].\quad\quad(1)

Applying this formula to the above bus example, we have \mathbb{E}[T] = 15 and

\displaystyle F_T(x) = \begin{cases}0, & x < 10\\  (x-10)/10, & 10 \leq x \leq 20\\  1, & x > 20\end{cases}

Using (1), the probability density function of waiting time f_W(x) is plotted below.

waitingtimeforbus

We see that the density function is a rectangle (centred at x = 5 and having 2/3 of the total probability mass) appended to a triangle (having centroid at x=40/3 and 1/3 of the total probability mass). From this we can say the expected waiting time is \mathbb{E}[W] = 5 \times (2/3) + 40/3 \times (1/3) = 70/9 \approx 7.78 minutes. This is more than half the mean interarrival time of 15/2 = 7.5 minutes that one might initially expect.

To prove (1), we shall first look at the length of a particular inter-arrival period that contains a given point t, and the waiting time can then be the part of this after time t. We make use of the following result from alternating renewal process theory [1]:

Proposition: Consider a system that alternates between on and off states where:

  • the on durations X_1, X_2, \ldots are independent and identically distributed according to random variable X, and
  • the off durations Y_1, Y_2, \ldots are independent and identically distributed according to random variable Y.

(However it may be that X_n and Y_n are dependent in general.)

Let p(t) be the probability that the system is in the on state at time t. Then if X+ Y has finite mean and is non-lattice (i.e. takes on more values than just an integral multiple of some positive number), then

\displaystyle \lim_{t \rightarrow \infty} p(t) = \frac{\mathbb{E}[X]}{\mathbb{E}[X+Y]}.\quad\quad(2)

This result is easily understood: the probability the system is on at a given time is the mean on time divided by the mean total cycle time. However it is based on the key renewal theorem, a limit theorem which is not so straightforward to prove.

Now consider a random process with independent and identically distributed interarrival times T_1, T_2, \ldots with common distribution T with probability distribution function F_T. Consider the length of the particular interarrival period T^* that contains some point t. We shall determine the distribution of T^*. We define an on-off system as follows.

  • If T^* is greater than some given x > 0, let our system be on for the entire interarrival period (i.e. X_{n} = T_n, Y_{n} = 0).
  • If the length of the interarrival period is less than or equal to x let our system be off for the interarrival period (i.e. X_{n} = 0, Y_{n} = T_n).

renewalperiodcontainingtThen by this definition the conditions of the above proposition are met and so

\begin{aligned} \text{Pr}(T^* > x) &= \text{Pr(system is on at time t)}\\  &= \frac{\mathbb{E}[X_n]}{\mathbb{E}[X_n+Y_n]}\quad\text{(by (2))}\\ &= \frac{\mathbb{E}[T_n \mid T_n > x]\text{Pr}(T_n > x)}{\mathbb{E}[T_n]}\\  &= \frac{\int_x^{\infty} t\ \ dF_T(t)}{\mathbb{E}[T]}.\quad\quad(3)\end{aligned}

Equivalently, \text{Pr}(T^* \leq x) = \frac{\int_0^{x} t\ \ dF_T(t)}{\mathbb{E}[T]}, and if T has probability density f_T, differentiating both sides of this equation gives the probability density function of the length of interarrival period containing a point t:

\displaystyle f_{T^*}(x) = xf_T(x)/\mathbb{E}[T].\quad\quad (4)

Intuitively, longer periods are more likely to contain the point t, with probability in direct proportion to the length of the interval. Hence the original density f_T(x) is scaled by the length x and then normalized by \int_0^{\infty} x f_T(x)\ dx = \mathbb{E}[T] to make xf_T(x)/\mathbb{E}[T] a valid probability density. T^* defined by (3) is known as the size-biased transform of T.

Note that the length of the particular interarrival interval T^* is stochastically larger than any of the identically distributed interarrival times T. In other words,

\displaystyle \text{Pr}(T^* > x) \geq \text{Pr}(T > x).\quad\quad(5)

This is the so-called inspection paradox, which can be proved by the Chebyshev correlation inequality (a form of rearrangement inequality) which states than when f and g are functions of the random variable X having the same monotonicity (i.e. both non-increasing or both non-decreasing), then f(X) and g(X) are non-negatively correlated:

\displaystyle \mathbb{E} [f(X)g(X)] \geq \mathbb{E}[f(X)] \mathbb{E}[g(X)].\quad\quad(6)

Applying this result with the non-decreasing functions f(T) = T and g(T) = {\bold 1}_{(T > x)} (which is 1 when T > x and 0 otherwise):

\begin{aligned} \text{Pr}(T^* > x) &= \frac{\int_x^{\infty} t\ \ dF_T(t)}{E[T]}\\ &= \frac{\mathbb{E}[T {\bold 1}_{(T>x)}]}{\mathbb{E}[T]}\\ &\geq \frac{\mathbb{E}[T] \mathbb{E}[{\bold 1}_{(T>x)}]}{\mathbb{E}[T]}\\ &= \mathbb{E}[{\bold 1}_{(T>x)}]\\ &= \text{Pr}(T > x).\quad\quad(7)\end{aligned}

The inspection paradox is a form of sampling bias, where results are modified as a result of a non-intended sampling of a given space. Another example is the friendship paradox, where in a graph of acquaintances with vertices having some differing degrees (number of friends), the average degree of a friend is greater than the average degree of a randomly chosen node. For one thing a friend will never have degree zero while a randomly chosen person might! The degree of a friend is an example of sampling from a size-biased distribution.

How about the distribution of the waiting time W for the next arrival? For fixed x > 0 we consider another on-off system where this time the system is in an off state during the last x units of time of an interarrival interval, and in the on state otherwise. That is,

  • Y_n = \min(x,T_n),
  • X_n = T_n - Y_n.

waitingperiodThen we have

\begin{aligned} \text{Pr}(W \leq x) &= \text{Pr(system is off at time t)}\\  &= \frac{\mathbb{E}[Y_n]}{\mathbb{E}[X_n+Y_n]} \quad\quad \text{(by (2))}\\  &= \frac{\mathbb{E}[\min(x,T_n)]}{\mathbb{E}[T_n]}\\  &= \frac{\int_0^{x} t\ \ dF_T(t) + \int_x^{\infty} x\ \ dF_T(t) }{\mathbb{E}[T_n]}\\  &= \frac{ \left[tF_T(t) \right]_{0}^x - \int_0^xF_T(t)\ dt + x(1-F_T(x))}{\mathbb{E}[T_n]}\quad \quad \text{(integrating the first term by parts)}  \\&= \frac{xF_T(x) - \int_0^x (1-F_T(t))\ dt - xF_T(x)}{\mathbb{E}[T_n]}\\  &= \frac{\int_0^x (1-F_T(t))\ dt }{\mathbb{E}[T_n]}.\quad\quad(8)\end{aligned}

Alternatively this form can be found by imagining our time t to be uniformly distributed within the current interarrival interval, thus partitioning our inspection interarrival interval T^* into (1-X)T^* and XT^*, where X is the uniform random variable X \sim U(0,1). Hence the distribution of W = XT^* is found by integrating over the distribution of T^* and using the fact that dF_T^*(t) = \frac{t}{\mathbb{E}[T]}\ dF_T(t) from (3):

\begin{aligned} \text{Pr}(W \leq x) &= \text{Pr}(XT^* \leq x)\\&= \int_0^{\infty} \text{Pr}(Xt \leq x \mid T^* = t)\ dF_{T^*}(t)\\&= \int_0^{\infty} \text{Pr}(U \leq x/t)\ dF_{T^*}(t)\\&=\int_0^x 1\ dF_{T^*}(t) + \int_x^{\infty} (x/t)\ dF_{T^*}(t)\\&=\int_0^x \frac{t}{\mathbb{E}[T]}\ dF_T(t) + x\int_x^{\infty} \frac{1}{t}\frac{t}{\mathbb{E}[T]}\ dF_T(t)\\&= \frac{\left[tF_T(t)\right]_0^x - \int_0^x F_T(t)\ dt + x(1-F_T(x))}{\mathbb{E}[T]} \quad\quad \text{(integrating the first term by parts)}\\&= \frac{- \int_0^xF_T(t)\ dt + x}{\mathbb{E}[T]}\\&= \frac{\int_0^x (1-F_T(t))\ dt }{\mathbb{E}[T]}.\quad\quad(9)\end{aligned}

Differentiating both sides of (8) or (9) with respect to x leads to (1), the probability density function of waiting time f_W(x) = (1-F_T(x))/\mathbb{E}[T].

Finally, if we wish to find any moments E[W^k] we write W = XT^* where X \sim U(0,1) and X is independent of the size-biased variable T^*:

\begin{aligned}\mathbb{E}[W^k] &= \mathbb{E}[(XT^*)^k]\\ &= \mathbb{E}[X^k] \mathbb{E}[(T^*)^k]\\&= \mathbb{E}[X^k]\int_0^{\infty}\frac{x}{\mathbb{E}[T]} (x^k)\ dF_T(x)\quad\quad \text{(}dF_T^*(x)\text{ related to }dF_T(x)\text{ via (3))}\\ &= \frac{\mathbb{E}[X^k]\mathbb{E}[T^{k+1}]}{\mathbb{E}[T]}\\ &= \frac{\int_0^1 x^k\ dx \mathbb{E}[T^{k+1}]}{\mathbb{E}[T]}\\ &= \frac{\mathbb{E}[T^{k+1}]}{(k+1)\mathbb{E}[T]}.\quad\quad(10)\end{aligned}

In particular

\begin{aligned} \mathbb{E}[W] &= \mathbb{E}[T^2]/(2\mathbb{E}[T])\\ &\geq (\mathbb{E}[T])^2/(2\mathbb{E}[T])\\ &= \mathbb{E}[T]/2\quad\quad(11)\end{aligned}.

Hence we can say that the mean waiting time for the next arrival from any given point in time is more than half the mean interarrival time, unless \mathbb{E}[T^2] = (\mathbb{E}[T])^2 (i.e. zero variance in T, meaning T is deterministic).

For example, in the initial bus example where T \sim U(10,20):

  • E[T] = 15,
  • E[T^2] = \int_{10}^{20} (t^2/10)\ dt = (20^3-10^3)/30 = 700/3 and
  • E[T^3] = \int_{10}^{20} (t^3/10)\ dt = (20^4-10^4)/40 = 3750,

so E[W] = E[T^2]/(2E[T]) = 700/90 = 70/9 \approx 7.78 > E[T]/2 = 7.5 and E[W^2] = E[T^3]/(3E[T]) = 250/3 \approx 83.33. Hence the waiting time has mean 7.78 and standard deviation of \sqrt{250/3-(70/9)^2} \approx 4.78.

References

[1] S. Ross, Stochastic Processes, John Wiley & Sons, 1996.

[2] R. Arratia and L. Goldstein, Size bias, sampling, the waiting time paradox, and infinite divisibility: when is the increment independent? Available at arxiv.org/pdf/1007.3910.

[3] This answer by Did on math.stackexchange.

July 30, 2014

A minimal list of countries whose borders span all nations

Filed under: geography — ckrao @ 11:39 am

 

There is an interesting Sporcle quiz here that asks one to list the countries of the world, where by listing each country all its neighbouring countries also appear. In that way there is no need to list all 197 countries. For example typing Russia or China alone leads to 14 more countries appearing since that is how many countries each of those countries borders. It led me to think of what is a minimal list of countries I could type in order to have all the countries listed. Mathematically speaking, if each country were represented as a node and I connect two nodes with an edge if they share a land border, then I am looking for a minimum vertex cover for the resulting graph.

After some trial and error I came up with the list below that may or not be minimal. Listed first are the continental countries and secondly the island nations.

The only island nations to share borders with other nations are:

  • UK with Ireland and Cyprus (at Akrotiri and Dhekelia)
  • Indonesia with East Timor
  • Indonesia with Papua New Guinea
  • Haiti with the Dominican Republic

Not counted are artificial bridge or tunnel borders such as between:

  • Singapore and Malaysia
  • Bahrain and Saudi Arabia (via the artificial Passport Island)
  • Denmark and Sweden
  • UK and France (via the Channel Tunnel).

Other curious borders are:

  • France with the Netherlands (at the Caribbean island of Saint Martin)
  • France with Brazil and Suriname (via French Guiana)
  • Spain with the United Kingdom (at Gibraltar)
  • Spain with Morocco (at three places on the African mainland)

 

As the following list shows, 149 continental countries can be covered by 9 + 10 + 8 + 3 + 2 = 32 countries which border the other 117.

continental Africa (9):

  • South Africa
  • Democratic Republic of Congo
  • Ethiopia
  • Senegal
  • Burkina Faso
  • Libya
  • Cameroon
  • any country that borders or is Malawi
  • one of Guinea, Liberia, Sierra Leone

continental Europe (including Russia) (10):

  • Germany
  • Spain
  • Italy
  • France or Monaco
  • one of Liechtenstein, Austria, Switzerland
  • Montenegro (borders all former Yugoslavia countries except Slovenia and Macedonia)
  • Norway or Sweden
  • Ukraine
  • Bulgaria
  • Russia

continental Asia (excluding Russia) (8):

  • Israel
  • Saudi Arabia
  • Iran
  • Uzbekistan
  • India
  • Vietnam
  • Malaysia
  • one of North/South Korea

continental North America (3):

  • Costa Rica
  • Guatemala
  • Canada or USA

continental South America (2):

  • Brazil (borders all except Chile and Ecuador)
  • Peru

For completeness we give a minimal list (42 entries) of the island sovereign states too.

Island sovereign states

Africa (6): Cape Verde, Comoros, Madagascar, Mauritius, São Tomé and Príncipe, Seychelles

Europe (3): Iceland, Malta, United Kingdom
(Ireland borders the United Kingdom)

Asia (8): Bahrain, Indonesia, Japan, Maldives, Philippines, Singapore, Sri Lanka, Taiwan
(East Timor borders Indonesia, Cyprus borders the United Kingdom, Brunei borders Malaysia)

North America (12): Antigua and Barbuda, Bahamas, Barbados, Cuba, Dominica, Dominican Republic or Haiti, Grenada, Jamaica, St Kitts and Nevis, St Lucia, St Vincent and the Grenadines, Trinidad and Tobago

Oceania (13): Australia, Fiji, Kiribati, Marshall Islands, Federated States of Micronesia, Nauru, New Zealand, Samoa, Solomon Islands, Palau, Tonga, Tuvalu, Vanuatu
(all except Papua New Guinea which borders Indonesia)

 

Below is a map of the world showing in black the countries listed above. It should be possible to reach a non-black labelled sovereign country from a black-labelled country via one land border crossing. Recall that Morocco is accessed via its small land border with Spain.

 

borders_covering_all_countries

References

http://en.wikipedia.org/wiki/Land_borders

http://en.wikipedia.org/wiki/List_of_island_nations

http://en.wikipedia.org/wiki/List_of_divided_islands

July 26, 2014

Harmonic numbers in terms of binomial coefficients

Filed under: mathematics — ckrao @ 11:48 am

Harmonic numbers H_n are the sums of reciprocals of the first n natural numbers.

\displaystyle H_n := \sum_{k=1}^n \frac{1}{k}\quad\quad(1)

The first few terms are 1, 3/2, 11/6, 25/12, 137/60, 49/20, 363/140, …

An interesting sum relating the harmonic numbers to the binomial coefficients is

\displaystyle H_n = \sum_{k=1}^n \binom{n}{k} \frac{(-1)^{k-1}}{k}.\quad\quad(2)

For example, for n=7:

\begin{aligned} & \quad \frac{7}{1} - \frac{21}{2} + \frac{35}{3} - \frac{35}{4} + \frac{21}{5} - \frac{7}{6} + \frac{1}{7}\\ &= \frac{363}{140}\\ &= \frac{1}{1} + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \frac{1}{5} + \frac{1}{6} + \frac{1}{7}. \end{aligned}

One way of proving this is by mathematical induction on n, where we also use the following result that looks similar but is easier to prove.

\displaystyle \sum_{k=0}^n \binom{n}{k} \frac{(-1)^{k}}{k+1} = \frac{1}{n+1}\quad\quad(3)

For example, for n = 7:

\displaystyle \frac{1}{1} - \frac{7}{2} + \frac{21}{3} - \frac{35}{4} + \frac{35}{5} - \frac{21}{6} + \frac{7}{7} - \frac{1}{8} = \frac{1}{8}.

Equation (3) can be proved by using the identity \frac{1}{k+1}\binom{n}{k} = \frac{1}{n+1} \binom{n+1}{k+1}. From this,

\begin{aligned} & \sum_{k=0}^n \binom{n}{k} \frac{(-1)^{k}}{k+1}\\  &= \frac{1}{n+1}\sum_{k=0}^n \binom{n+1}{k+1} (-1)^{k}\\  &= \frac{1}{n+1}\sum_{k'=1}^{n+1} \binom{n+1}{k'} (-1)^{k'-1}\\  &= \frac{1}{n+1}\left(\sum_{k'=0}^{n+1} \binom{n+1}{k'} (-1)^{k'} (-1) - \binom{n+1}{0} (-1)^{-1}\right)\\  &= \frac{1}{n+1}\left[ \left( (1-1)^{n+1} . (-1)\right) - (-1)\right]\\  &= \frac{1}{n+1},  \end{aligned}

as required.

Then to prove (2) firstly note that for n=1, \sum_{k=1}^1 \binom{1}{k} \frac{(-1)^{k-1}}{k} = 1 = H_1, so the result is true when n = 1. Assume it is true for n = m for some positive integer m. That is, assume

\displaystyle H_m = \sum_{k=1}^m \binom{m}{k} \frac{(-1)^{k-1}}{k}.\quad\quad(4)

Then

\begin{aligned}  \sum_{k=1}^{m+1} \binom{m+1}{k} \frac{(-1)^{k-1}}{k}  &= \sum_{k=1}^{m} \binom{m+1}{k} \frac{(-1)^{k-1}}{k} + \binom{m+1}{m+1} \frac{(-1)^{m}}{m+1}\\  &= \sum_{k=1}^{m} \left( \binom{m}{k} + \binom{m}{k-1} \right) \frac{(-1)^{k-1}}{k} + \frac{(-1)^{m}}{m+1}\\  &= \sum_{k=1}^{m} \binom{m}{k} \frac{(-1)^{k-1}}{k} + \sum_{k=1}^{m} \binom{m}{k-1} \frac{(-1)^{k-1}}{k} + \frac{(-1)^{m}}{m+1}\\  &= \sum_{k=1}^{m} \binom{m}{k} \frac{(-1)^{k-1}}{k} + \sum_{k'=0}^{m-1} \binom{m}{k'} \frac{(-1)^{k'}}{k'+1} + \frac{(-1)^{m}}{m+1}\\  &= \sum_{k=1}^{m} \binom{m}{k} \frac{(-1)^{k-1}}{k} + \sum_{k'=0}^{m} \binom{m}{k'} \frac{(-1)^{k'}}{k'+1} - \binom{m}{m} \frac{(-1)^{m}}{m+1}+ \frac{(-1)^{m}}{m+1}\\  &= \sum_{k=1}^{m} \binom{m}{k} \frac{(-1)^{k-1}}{k} + \frac{1}{m+1} \quad \text{(using (3))}\\  &= H_m + \frac{1}{m+1} \quad \text{(using (4))}\\  &= H_{m+1}.  \end{aligned}

Hence we have shown that if (2) is true for n=m, it is also true for n=m+1. Then by the principle of mathematical induction (2) is true for all natural numbers n.

A more beautiful proof of (2), taken from here, is to write 1/(k+1) = \int_0^1 x^k\ \text{d}x and so

\begin{aligned}  H_n &= \sum_{k=0}^{n-1} \frac{1}{k+1}\\  &= \sum_{k=0}^{n-1} \int_0^1 x^k\ \text{d}x\\  &= \int_0^1 \left( \sum_{k=0}^{n-1} x^k \right) \ \text{d}x\\  &= \int_0^1 \frac{1-(1-u)^n}{u} \text{d}u\\  &= \int_0^1 \frac{-\sum_{k=1}^n \binom{n}{k} (-1)^k u^k}{u} \text{d}u\\  &= \sum_{k=1}^n \binom{n}{k} (-1)^{k+1} \int_0^1 u^{k-1} \text{d}u\\  &= \sum_{k=1}^n\binom{n}{k} \frac{(-1)^{k-1}}{k},\\  \end{aligned}

as required.

June 29, 2014

Melbourne’s late start to cooler temperatures in 2014

Filed under: climate and weather — ckrao @ 11:21 am

It occurred to me that Melbourne has had an unusual number of cooler days in 2014 up to the middle of June. After some checking here, I found that from January 1 to June 17 this year, the Melbourne Regional Office has only twice recorded days with a maximum temperature less than 15°C (May 2 [14.3°C] and May 4 [14.2°C]). This beats 2003 when the previous fewest number of 5 such instances took place prior to June 18. The graph and table below show that in the past this number has been as high as 40, but in recent years there is a clear downward trend.

lackofcooldays_regionaloffice

Melbourne Regional Office Average number of sub-15°C days before June 18
Average 1856-2013 21.6
Average 1971-2013 15.0
Average 2004-2013 11.7
2014 2

 

If we do the same calculation for a station further away from the city centre, say the international airport just over 20km away, there is not as much historical data and the effect is not as pronounced, but this year still equals the previous record of 2003 (11 times). In recent times the sub-15°C days prior to June 18 have been about twice as frequent here as the Regional Office.

lackofcooldays_airport

Melbourne Airport Average number of sub-15°C days before June 18
Average 1971-2013 24.7
Average 2004-2013 23.1
2014 11

The data is from Australia’s Bureau of Meteorology website.

June 28, 2014

A few sums involving inverses of binomial coefficients

Filed under: mathematics — ckrao @ 11:11 am

One of the problems from the 1990 Australian Mathematical Olympiad ([1]) asks one to prove the following result.

\displaystyle \sum_{k=1}^{2n-1}\frac{(-1)^{k-1}}{\binom{2n}{k}} = \frac{1}{n+1}.\quad\quad (1)

One solution in [1] makes use of the following identity:

\begin{aligned}  \frac{1}{\binom{m}{k}} &= \frac{k!(m-k)!}{m!}\\  &= \frac{k!(m-k)!(m+1)(m+2)}{m!(m+1)(m+2)}\\  &= \left(\frac{m+1}{m+2}\right)\frac{k!(m-k)!(m+2)}{(m+1)!}\\  &= \left(\frac{m+1}{m+2}\right)\frac{k!(m-k)!((m-k+1) + (k+1))}{(m+1)!}\\  &=\left(\frac{m+1}{m+2}\right)\frac{k!(m-k+1)! + (k+1)!(m-k)!}{(m+1)!}\\  &= \frac{m+1}{m+2}\left(\frac{1}{\binom{m+1}{k}}+ \frac{1}{\binom{m+1}{k+1}}\right).\quad\quad(2)  \end{aligned}

Then setting m=2n, (1) becomes a telescoping sum:

\begin{aligned}  \sum_{k=1}^{2n-1}\frac{(-1)^{k-1}}{\binom{2n}{k}}  &= \sum_{k=1}^{2n-1} \frac{2n+1}{2n+2}\left(\frac{(-1)^{k-1}}{\binom{2n+1}{k}}+ \frac{(-1)^{k-1}}{\binom{2n+1}{k+1}}\right)\\  &= \frac{2n+1}{2n+2}\left( \sum_{k=1}^{2n-1} \frac{(-1)^{k-1}}{\binom{2n+1}{k}} + \sum_{k=1}^{2n-1} \frac{(-1)^{k-1}}{\binom{2n+1}{k+1}}\right)\\  &= \frac{2n+1}{2n+2}\left( \frac{(-1)^0}{\binom{2n+1}{1}} + \sum_{k=2}^{2n-1} \frac{(-1)^{k-1}}{\binom{2n+1}{k}} + \frac{(-1)^{2n-1-1}}{\binom{2n+1}{2n-1+1}} + \sum_{k=1}^{2n-2} \frac{(-1)^{k-1}}{\binom{2n+1}{k+1}} \right)\\  &= \frac{2n+1}{2n+2}\left( \frac{1}{2n+1} + \frac{1}{2n+1} + \sum_{k=1}^{2n-2} \frac{(-1)^{k}}{\binom{2n+1}{k+1}} + \sum_{k=1}^{2n-2} \frac{(-1)^{k-1}}{\binom{2n+1}{k+1}} \right)\\  &= \frac{2n+1}{2n+2} \left(\frac{2}{2n+1} + 0\right)\\  &= \frac{1}{n+1}.  \end{aligned}

Using a similar argument one can prove the more general identity

\displaystyle \sum_{k=0}^n\frac{(-1)^k}{\binom{n}{k}} = \frac{n+1}{n+2}\left(1 + (-1)^n\right).\quad\quad (3)

How about the sum \displaystyle S(n) := \sum_{k=0}^{n}\frac{1}{\binom{n}{k}}? Using (1) we find the recursion

\begin{aligned}  S(n) &= \frac{n+1}{n+2}\left(\sum_{k=0}^n \frac{1}{\binom{n+1}{k}} + \frac{1}{\binom{n+1}{k+1}}\right)\\  &= \frac{n+1}{n+2}\left(S(n+1)-1 + S(n+1)-1\right)\\  &= \frac{2(n+1)}{n+2}\left(S(n+1)-1 \right). \quad\quad (4)\\  \end{aligned}

Hence we have the recurrence relation

\displaystyle S(n+1) = \frac{n+2}{2(n+1)}S(n) + 1.\quad\quad(5)

From this S(n) does not have a closed form solution but using induction on n we can prove the following relations found in [2].

\displaystyle S(n) := \sum_{k=0}^{n}\frac{1}{\binom{n}{k}} = \frac{n+1}{2^{n+1}}\sum_{k=1}^{n+1}\frac{2^k}{k} = (n+1)\sum_{k=0}^n \frac{1}{(n+1-k)2^k}.\quad\quad(6)

Firstly note that when n=0, the three expressions in (5) become \frac{1}{\binom{0}{0}},  \frac{1}{2^{1}}\frac{2^1}{1} and \frac{1}{1}, which are all equal to 1. Hence (6) holds for n=0. Assume it holds for n =m. That is,

\displaystyle S(m) := \sum_{k=0}^{m}\frac{1}{\binom{m}{k}} = \frac{m+1}{2^{m+1}}\sum_{k=1}^{m+1}\frac{2^k}{k} = (m+1)\sum_{k=0}^m \frac{1}{(m+1-k)2^k}.\quad\quad(7)

Then using (5), on the one hand,

\begin{aligned}  S(m+1) &= 1 + \frac{m+2}{2(m+1)}S(m)\\  &= 1 + \frac{m+2}{2(m+1)} \frac{m+1}{2^{m+1}}\sum_{k=1}^{m+1}\frac{2^k}{k} \\  &= 1 + \frac{m+2}{2^{m+2}}\sum_{k=1}^{m+1}\frac{2^k}{k}\\  &= \frac{(m+2)2^{m+2}}{2^{m+2}(m+2)} + \frac{m+2}{2^{m+2}}\sum_{k=1}^{m+1}\frac{2^k}{k}\\  &= \frac{m+2}{2^{m+2}}\sum_{k=1}^{m+2}\frac{2^k}{k},\quad\quad(8)  \end{aligned}

while on the other,

\begin{aligned}S(m+1) &= 1 + \frac{m+2}{2(m+1)}S(m)\\  &= 1 + \frac{m+2}{2(m+1)} (m+1)\sum_{k=0}^m \frac{1}{(m+1-k)2^k}\\  &= 1 + (m+2)\sum_{k=0}^m \frac{1}{(m+1-k)2^{k+1}}\\  &= 1 + (m+2)\sum_{k=0}^m \frac{1}{(m+2-(k+1))2^{k+1}}\\  &= 1 + (m+2)\sum_{k=1}^{m+1} \frac{1}{(m+2-k)2^{k}}\\  &= (m+2)\sum_{k=0}^{m+1} \frac{1}{(m+2-k)2^k}.\quad \quad(9)  \end{aligned}

Equations (8) and (9) show that if (6) holds for n=m, then it does for n=m+1. By the principle of mathematical induction, (6) then is true for all integers n\geq 0.

Another related sum that can be expressed in terms of S(n) is \displaystyle \frac{1}{\binom{2n}{0}} + \frac{1}{\binom{2n}{2}} + \frac{1}{\binom{2n}{4}} + \ldots + \frac{1}{\binom{2n}{2n}}. We have

\begin{aligned}& \sum_{k=0}^{2n} \frac{1}{\binom{2n}{2k}}\\&= \frac{2n+1}{2n+2}\sum_{k=0}^{2n} \frac{1}{\binom{2n+1}{k}}\text{\quad \quad (by (5))}\\  &= \frac{2n+1}{2n+2} S(2n+1).\quad\quad(10)  \end{aligned}

Note that more identities with inverses of binomial coefficients are in [2] (and references therein), where the integral

\displaystyle \frac{1}{\binom{n}{k}} = (n+1) \int_0^1 t^k (1-t)^{n-k}\ \text{d}t

is utilised.

References

[1] A. W. Plank, Mathematical Olympiads: The 1990 Australian Scene, University of Canberra, 1990.

[2] T. Mansour, Combinatorial Identities and Inverse Binomial Coefficients, available at http://math.haifa.ac.il/toufik/toupap02/qap0204.pdf

Next Page »

The Rubric Theme. Blog at WordPress.com.

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: