| Version current |
Version 6 |
| A sequence $\{a_n\}_{n=1}^\infty$ is called \emph{subadditive} if |
A sequence $\{a_n\}_{n=1}^\infty$ is called \emph{subadditive} if |
| it satisfies the inequality |
it satisfies the inequality |
| \begin{equation}\label{eqn:seq} |
\begin{equation}\label{eqn:seq} |
| a_{n+m}\leq a_n+a_m\qquad\text{for all $n$ and $m$}. |
a_{n+m}\leq a_n+a_m\qquad\text{for all $n$ and $m$}. |
| \end{equation} |
\end{equation} |
| The major reason for use of subadditive sequences is the following |
The major reason for use of subadditive sequences is the following |
| lemma due to Fekete. |
lemma due to Fekete. |
| \begin{lemma}[\cite{cite:polya_szegoi}] |
\begin{lemma}[\cite{cite:polya_szegoi}] |
| For every subadditive sequence $\{a_n\}_{n=1}^\infty$ the limit |
For every subadditive sequence $\{a_n\}_{n=1}^\infty$ the limit |
|
$\lim a_n/n$ exists and is equal to $\inf a_n/n$.
|
$\lim a_n/n$ exists and equal to $\inf a_n/n$.
|
| \end{lemma} |
\end{lemma} |
|
|
| Similarly, a function $f(x)$ is \emph{subadditive} if |
Similarly, a function $f(x)$ is \emph{subadditive} if |
| \begin{equation*} |
\begin{equation*} |
| f(x+y)\leq f(x)+f(y)\qquad\text{for all $x$ and $y$}. |
f(x+y)\leq f(x)+f(y)\qquad\text{for all $x$ and $y$}. |
| \end{equation*} |
\end{equation*} |
| The analogue of Fekete lemma holds for subadditive functions as |
The analogue of Fekete lemma holds for subadditive functions as |
| well. |
well. |
|
|
| There are extensions of Fekete lemma that do not require \eqref{eqn:seq} to hold for all $m$ and $n$. There are also results that allow one to deduce the rate of convergence to the limit whose existence is stated in Fekete lemma if some kind of both \PMlinkname{super-}{Superadditivity} and subadditivity is present. A good exposition of this topic may be found in \cite{cite:steele_azuma}. |
There are extensions of Fekete lemma that do not require \eqref{eqn:seq} to hold for all $m$ and $n$. There are also results that allow one to deduce the rate of convergence to the limit whose existence is stated in Fekete lemma if some kind of both \PMlinkname{super-}{Superadditivity} and subadditivity is present. A good exposition of this topic may be found in \cite{cite:steele_azuma}. |
|
|
| \begin{thebibliography}{1} |
\begin{thebibliography}{1} |
|
|
| \bibitem{cite:polya_szegoi} |
\bibitem{cite:polya_szegoi} |
| Gy{\"o}rgy Polya and G{\'a}bor Szeg{\"o}. |
Gy{\"o}rgy Polya and G{\'a}bor Szeg{\"o}. |
| \newblock {\em Problems and theorems in analysis}, volume~1. |
\newblock {\em Problems and theorems in analysis}, volume~1. |
| \newblock 1976. |
\newblock 1976. |
| \newblock \PMlinkexternal{Zbl |
\newblock \PMlinkexternal{Zbl |
| 0338.00001}{http://www.emis.de/cgi-bin/zmen/ZMATH/en/quick.html?type=html&an% |
0338.00001}{http://www.emis.de/cgi-bin/zmen/ZMATH/en/quick.html?type=html&an% |
| =0338.00001}. |
=0338.00001}. |
|
|
| \bibitem{cite:steele_azuma} |
\bibitem{cite:steele_azuma} |
| Michael~J. Steele. |
Michael~J. Steele. |
| \newblock {\em Probability theory and combinatorial optimization}, volume~69 of |
\newblock {\em Probability theory and combinatorial optimization}, volume~69 of |
| {\em CBMS-NSF Regional Conference Series in Applied Mathematics}. |
{\em CBMS-NSF Regional Conference Series in Applied Mathematics}. |
| \newblock SIAM, 1997. |
\newblock SIAM, 1997. |
| \newblock \PMlinkexternal{Zbl |
\newblock \PMlinkexternal{Zbl |
| 0916.90233}{http://www.emis.de/cgi-bin/zmen/ZMATH/en/quick.html?type=html&an% |
0916.90233}{http://www.emis.de/cgi-bin/zmen/ZMATH/en/quick.html?type=html&an% |
| =0916.90233}. |
=0916.90233}. |
|
|
| \end{thebibliography} |
\end{thebibliography} |
