Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I came across these numbers in my work some time ago. This type of expressions do not exist in closed form (not to confuse with Vandermonde convolution), I already know that. To simplify I denote $$P(r;s;k)=\binom{\frac{n}{2}+r}{k} \binom{\frac{n}{2}-r}{k+s}$$

Here is why I think these numbers are interesting: anyone can see combinatorial structures in algorithms or elsewhere, but these expressions converge.

Experiment 1, $r=0, s=0:$ There are $n$ fair coins, of them half are heads $H$, half are tails $T$. Each coin is flipped w.p. $\frac{1}{n}$, i.e. proportional to size of the sample. The question is, after the experiment is over, what is the probability that the ratio of $H$/$T$ remains the same, i.e. half and half. The tricky thing is, in order to preserve the ratio, we need to flip an $\mathit{even}$ number of coins, or, more specifically, an equal number of $H$ and $T$ (obviously two $H$ or two $T$ won't do): either 0 $H$ and 0 $T$, or 1 $H$ and 1 $T$ and so on till $\frac{n}{2} \ H, \frac{n}{2} \ T$. The probability to preserve the ratio (and the first such number) is therefore $$ h_{0,0}= \lim _{n \to \infty} \sum_{k=0}^{\frac{n}{2}} P(0;0;k) \frac{1}{n^{2k}} \bigg(1-\frac{1}{n}\bigg)^{n-2k} \approx 0.465267 $$

Experiment 2, $r=0,s=1$: same setup as before, but now I need to obtain $\textit{exactly}$ one more $H$ coin as a result of the experiment (or $T$, it does not matter by symmetry). To do this, I need to flip $exactly$ one more $T$ than $H$, hence we need to flip an $odd$ number of coins:

$$ h_{0,1}= \lim _{n \to \infty} \sum_{k=0}^{\frac{n}{2}-1} P(0;1;k) \frac{1}{n^{2k+1}} \bigg(1-\frac{1}{n}\bigg)^{n-2k-1} \approx 0.208912 $$

Experiment 3, $r=1,s=0$. This comes directly after experiment 2: we have $\frac{n}{2}+1 \ H$ and $\frac{n}{2}-1 \ T$. We want the same result as in Experiment 1: maintain the current proportion of $H$ and $T$ (i.e. flip an even number of coins), but clearly this time around the upper bound on the summation is $\frac{n}{2}-1$.

$$ h_{1,0}= \lim _{n \to \infty} \sum_{k=0}^{\frac{n}{2}-1} P(1;0;k) \frac{1}{n^{2k}} \bigg(1-\frac{1}{n}\bigg)^{n-2k} \approx 0.465225 $$

and so on for $h_{r,s}, 0 \leq r,s \leq n$. So here is what I'd like to know:

1) Have these numbers arisen in some other context (I never ended up publishing a paper)

2) Is there some rigorous way to prove these numbers are irrational? I've shown the $\lim$ part simply by taking large $n$, so I guess this not rigorous enough.

3) If there is something I've missed, I'd like to know too.

Thanks for the suggestions.

share|improve this question
    
I'm getting $\approx 0.46576$ for $h_{0,0}$. That's close to your value but not exactly the same. Could my number be correct, or did I make a mistake somewhere? If it's correct, I'll type up my answer sometime in the next day or two. Unfortunately, I don't have time right now. –  Mike Spivey Jan 13 '13 at 7:08
    
I mentioned that my proof is purely numerical and is probably not rigorous, hence different values for $h$. Is the question too silly/unreasonable as it didn't generate too much interest? –  Alex Jan 13 '13 at 16:07
2  
It's really hard to make sense sometimes of how this community responds to questions and answers. I've been surprised many times at which of my questions and answers get a lot of attention and which don't. At any rate, I think your question is interesting (and hard). Also, I will post my answer at some point. We'll see if I have time this afternoon to type it up. –  Mike Spivey Jan 13 '13 at 20:53
    
Thanks Mike. Please do give your answer. Do you think posting this question on MO would make sense? –  Alex Jan 13 '13 at 20:55
    
I would wait a few more days. I think there are some really good mathematicians who browse the unanswered questions here every few days or so, so you might yet get a complete answer. –  Mike Spivey Jan 13 '13 at 20:59

1 Answer 1

up vote 4 down vote accepted

I find $$h_{0,0} = \frac{I_0(1)}{e} \approx 0.4657596,$$ where $I_0(x)$ is a modified Bessel function. That answers your question about $h_{0,0}$ arising in some other context.

As far as the irrationality of $h_{0,0}$, of course $1/e$ is transcendental. The value of $I_0(1)$ is irrational as well (see argument at end of post). Since irrational times irrational might be rational, though, this doesn't completely answer your question about $h_{0,0}$.

I'm not sure about $h_{0,1}$ and $h_{1,0}$. Perhaps my argument below could be modified.


Proof that $h_{0,0} = I_0(1)/e$.

Since the total number of coins must be even, let's consider $2n$ coins. Then $$h_{0,0} = \lim_{n \to \infty} \sum_{k=0}^n \binom{n}{k} \binom{n}{k} \left(\frac{1}{2n}\right)^{2k} \left(1 - \frac{1}{2n}\right)^{2n-2k}.$$ With a little algebra, the summation can be simplified to $$\left(1 - \frac{1}{2n}\right)^{2n} \sum_{k=0}^n \binom{n}{k}^2 \frac{1}{(2n-1)^{2k}}.$$ Now, $\sum_{k=0}^n \binom{n}{k}^2 x^k$ can be expressed in terms of Legendre polynomials $P_n$. (See, for instance, my answer here.) With $x = 1/(2n-1)^2$, we have $$\sum_{k=0}^n \binom{n}{k}^2 x^k = (1-x)^n P_n\left(\frac{1+x}{1-x}\right) = \left(1-\frac{1}{(2n-1)^2}\right)^n P_n\left(1 + \frac{1}{2n^2-2n}\right).$$

Since $\left(1 - \frac{1}{2n}\right)^{2n} \to 1/e$ and $\left(1-\frac{1}{(2n-1)^2}\right)^n \to 1$ as $n \to \infty$, we're left with determining the asymptotics of the Legendre polynomial expression.

According to the DLMF, for $x > 1$, and $n \to \infty$, $$P_n(x) \sim \frac{\cosh^{-1} x}{\sinh(\cosh^{-1}x)} I_0\left((n+1/2)\cosh^{-1}(x)\right).$$

The asymptotic calculations from here are a bit painful. Essentially we need to use $\cosh^{-1}(x) = \log(x+ \sqrt{x^2-1})$ (see, for instance, here) and $\sinh(\cosh^{-1}x) = \sqrt{x^2-1}$. We get $\displaystyle \frac{\cosh^{-1} y}{\sinh(\cosh^{-1}y)} \to 1$ and $(n+1/2)\cosh^{-1}(y) \to 1$ as $n \to \infty$ for $y = 1 + \frac{1}{2n^2-2n}$.

This establishes $$h_{0,0} = \frac{I_0(1)}{e},$$ as I mention as the top of the post.


Proof that $I_0(1)$ is irrational.

The modified Bessel function $I_0(x)$ has the nice representation $$I_0(x) = \sum_{k=0}^{\infty} \frac{x^{2k}}{k!k!4^k}.$$ Thus $$I_0(1) = \sum_{k=0}^{\infty} \frac{1}{k!k!4^k}.$$ To prove that the value of this infinite sum is irrational, you can mimic Sondow's proof of the irrationality of $e$. Start with the interval $[1,2]$. At step $k$, divide the current interval into $4k^2$ equal subintervals and take the second subinterval each time. This creates a sequence of nested intervals such that $\displaystyle \frac{a_k}{k!k!4^k} < I_0(1) < \frac{a_k+1}{k!k!4^k}$ and $a_k$ is an integer. This proves that $I_0(1)$ cannot be represented in the form $\displaystyle \frac{r}{k!k!4^k}$ for any integer $r$. However, every rational number can be expressed in the form $\displaystyle \frac{r}{k!k!4^k}$ for some integer $r$. For instance, $\displaystyle \frac{p}{q} = \frac{p (q-1)! q! 4^q}{q!q!4^q}$. Therefore, $I_0(1)$ is irrational.

share|improve this answer
    
You might also note that according to Maple $$I_0(x)/e^x = \sum _{k=0}^{\infty }{\frac { \left( -1 \right) ^{k} \left( 2\,k \right) !\,{2}^{-k}{x}^{k}}{ \left( k! \right) ^{3}}} $$ I don't know if that will help in proving that this is irrational for $x=1$. –  Robert Israel Jan 14 '13 at 4:21
    
Wow, that's a great answer! I knew about the representation using Legendre polynomial, but the rest is new. One more thing I'm thinking is something with the general expression for $h(r,s)$. I still may put it on MO in case someone gets interested. –  Alex Jan 14 '13 at 4:22
    
@RobertIsrael: Thanks! I'll have to take a look at that. –  Mike Spivey Jan 14 '13 at 4:47

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.