4
$\begingroup$

Background

I'm modeling Genetic Algorithm(GA) with Markov chains and deriving the expression for the expectation of the first hittig time in the MC with 1 absorbing state and $l-1$ transient states. This results is an expression for a sum involving square of a binomial coefficient

Problem I need to find a closed expression for $$\sum_{k=0}^{l/2} \binom{l/2}{k}^2 p^{2k}$$

where $p$ is a function of $l$ and lies between 0 and 1.

So far I've found a closed expression for $$\sum_{k=0}^{n}k^2 \binom{n}{k}^2$$

Any suggestions are very much appreciated.

Improve this question
$\endgroup$
19
  • $\begingroup$ I'm confused: why do you think there is hope to find a closed-form formula for your expression without knowing the exact dependence between p and l? $\endgroup$
    – Thierry Zell
    Commented Jan 23, 2011 at 1:48
  • $\begingroup$ @Thierry, if the binomial coefficient weren't squared, there would be the closed-form expression $(1+p^2)^{\ell/2}$, so maybe there's one here, too. $\endgroup$
    – Gerry Myerson
    Commented Jan 23, 2011 at 2:39
  • $\begingroup$ OK, let's say $p=\frac{1}{l}$ or $1-\frac{1}{l}$. Does this help. I mean I hope to find such formula as a closed form for arbitrary p. $\endgroup$
    – sigma_z_1980
    Commented Jan 23, 2011 at 4:08
  • 1
    $\begingroup$ Using the notation $n=\ell/2$, your first sum is the coefficient of $x^n$ in the polynomial $(1+x)^n(1+p^2x)^n$. As such, it can be evaluated as the integral of a complex valued rational function on the unit circle of the complex plane. Not that his helps much... As regards the $_2F_1$ expression provided by Mathematica, I believe this function is the exact expansion along increasing powers of $p$ which is written in the original question. :-) $\endgroup$
    – Did
    Commented Jan 23, 2011 at 15:36
  • 1
    $\begingroup$ @sigma: Sorry I was not more explicit. Here is a way to get at the result. Gerry is right, one works in the space $\mathbb{R}[x]$ of the polynomials wih one indeterminate $x$. Let us forget the coefficient $p$ for a moment and note that ${n \choose k}^2={n \choose k}{n \choose n-k}$, that ${n \choose k}$ is the coefficient of $x^k$ in $P(x)=(1+x)^n$ and that ${n \choose n-k}$ is the coefficient of $x^{n-k}$ in $Q(x)=(1+x)^n$ (yes I know, $P(x)=Q(x)$ but just wait and you will see). (to be cont'd) $\endgroup$
    – Did
    Commented Jan 24, 2011 at 0:55

1 Answer 1

Reset to default
5
$\begingroup$

According to Mathematica, your sum equals:

$(1-p^2)^{l/2} \mbox{LegendreP}\left(l/2, \frac{1+p^2}{1-p^2}\right),$

or

$\, _2F_1\left(-\frac{l}{2},-\frac{l}{2};1;p^2\right)$

The second sum is $n^2 \binom{2 n-2}{n-1}.$

Ain't technology grand...

EDIT The real question is: why do you want to know? The expressions I give above allow you to get asymptotics, get ODE satisfied by the functions, etc, etc. If you want an expression in terms of "elementary functions" (whatever that means in this case), with very high probability there are not any (this is less certain here because these are definite summmations). I strongly advise you to read Petkovsek and Zeilberger's "A=B."

Improve this answer
$\endgroup$
1
  • $\begingroup$ I'd like to get a closed expression because this will provide more understanding of convergence of Evolutionary algorithms, as this probability is important to obtain an exact expression for the expectation of the 1st hitting time. $\endgroup$
    – sigma_z_1980
    Commented Jan 23, 2011 at 21:29

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .