Asymptotic Limits of a New Type of Maximization Recurrence with an Application to Bioinformatics
Abstract
We study the asymptotic behavior of a new type of maximization recurrence, defined as follows. Let $k$ be a positive integer and $p_{k}(x)$ a polynomial of degree~$k$ satisfying $p_{k}(0) = 0$. Define $A_{0} = 0$ and for $n \geq 1$, let $A_{n} = \max\nolimits_{0 \leq i < n} \{ A_{i} + n^{k} \, p_{k}(\frac{i}{n}) \}$. We prove that $\lim_{n \rightarrow \infty} \frac{A_{n}}{n^k} \,=\, \sup \{ \frac{p_k(x)}{1-x^k}: 0 \leq x <1\}$. We also consider two closely related maximization recurrences~$S_{n}$ and~$S'_{n}$, defined as $S_{0} = S'_{0} = 0$, and for $n \geq 1$, $S_{n} = \max\nolimits_{0 \leq i < n} \{ S_{i} + \frac{i(n-i)(n-i-1)}{2} \}$ and $S'_{n} = \max\nolimits_{0 \leq i < n} \{ S'_{i} + {n-i \choose 3} + 2i { n-i \choose 2} + (n-i){ i \choose 2} \}$. We prove that $\lim\nolimits_{n \rightarrow \infty} \frac{S_{n}}{n^3} = \frac{2\sqrt{3}-3}{6} \approx 0.077350...$ and $\lim\nolimits_{n \rightarrow \infty} \frac{S'_{n}}{3{n \choose 3}} = \frac{2(\sqrt{3}-1)}{3} \approx 0.488033...$, resolving an open problem from Bioinformatics about rooted triplets consistency in phylogenetic networks.
Origin | Publisher files allowed on an open archive |
---|
Loading...