\input{ca_preamble.tex}

\newcommand{\PR}{\textbf{Pr}}
\newcommand{\Expect}{\textbf{M}}


\begin{document}

\lectitle{12}{� ����������� � ��������� �������������������}
 \lecauthor{�.\,������}
\date{29 ������ 2008}
\maketitle

����� ������ ������� $f:\ZZ_n \to \ZZ_n$ � ��������� �����
$x_0 \in \ZZ_n$. �� �������� $f$ � $x_0$ �������� ������������������:
\begin{equation}\label{eq:seq_formula}
x_n = f(x_{n-1}), n \ge 1.
\end{equation}

���������� ������ ������� ��������� ���������� � ������������ ������������������: � �������� ��������
�������� ����� ������� $x_s$, ��� ��� �������� $x_0, \ldots, x_{s-1}$ ��������, � ����� ����
$s$ ��������� ���������� ������������ ������� $x_h = x_s$. ��� ����������, ������� � �������
����� �� ��������� ����� $x_0$ ����� �������, ����� �������� ��� ������ ����������.

\begin {proposition}
��� ����� ��������� $f:\ZZ_n \to \ZZ_n$, $x_0 \in \ZZ_n$, ������� ����� �� ������� ���������
���������� � ������������������ \Ref{eq:seq_formula} �� ����������� �������� $\mathcal{O}(\sqrt n).$
\end {proposition}
\begin{proof}

�������� ������������� ������������ $<\Omega,\:\mathcal{F},\:\PR>$.
\begin{enumerate}
	\item
		$\Omega = \left\{ (f,x_0), f:\ZZ_n \to \ZZ_n, x_0 \in \ZZ_n \right\}$.
		
		��������� $\ZZ_n$ ��������
		$n$ ��������� ���������, ������ �� ������� ����� ���������� � ���� �� $n$ ���������. �������
		���������� $n^n$ ��������� ������� $f:\ZZ_n \to \ZZ_n$.
		
		����� $x_0$ ����� ������� �� $\ZZ_n$ $n$ ���������� ���������.
		
		����� �������, $\left|\Omega\right| = n \cdot n^n = n^{n+1}$.
	\item
		����� ��������� �������� $\xi$ ���� ����� ���� (������� � ��������), �� ������� ���� �������� ������
		���������� � ������������������, ������������ \Ref{eq:seq_formula}. ��� ���������� �����������
		������� $\left\{\xi = s\right\}, s \in \NN_0$. ���������� ���-�� �������, ������������������ �������.

		�������� $x_0, \ldots, x_{s-1}$ ������ ���� ��������, � $x_s$ ������ ��������� � ����� �� ���.
		���������� ���������� ����������� $f$, ���������� � ���� ������������. 	����� $x_0$ �����
		���������� � $x_1$ $n-1$ ���������, $x_2$ � $x_1$ --- $n-2$ ���������, \ldots ,
		$x_{s-2}$ � $x_{s-1}$ --- $n-s+1$ ���������. ��� �������� $x_0, \ldots, x_{s-2}$ �������� � ����
		$s-1$ �������� ��������� ��������� $\ZZ_n$, --- ��� ����� �� ��������� ����������� $f$ ��� ���� $s-1$
		���������. �����, $x_{s-1}$ � $x_{s}$ ����� ���������� ������ $s$ ���������, ����� �� ������ �
		����� �� �������������� ���������. ��� ����� ��������� ����������� $f$ ��� $s$ ��������� ���������
		$\ZZ_n$, �. �. $x_0$, \ldots, $x_{s-1}$ ��� ��������. �������� ��������� $f$ ��� ���������� $n-s$ ���������
		��������� $\ZZ_n$. ����� �� ���� $n-s$ ��������� ����� ���������� � ����� �� $n$ ���������
		$\ZZ_n$, � ��� ����� ������� $n^{n-s}$ ���������.
		
		����� $x_0$ ����� ������� ������������ ������� �� $n$ ���������.
		
		��������� �������� ������������, ��������:
		\[
			\PR(\left\{\xi = s\right\}) \mathop  = \limits^{def} \PR(s) =
				\frac{n\cdot(n-1)\cdot(n-2)\cdot\ldots\cdot(n-s+1) \cdot s \cdot n^{n-s}}{n^{n+1}} =
				\frac{n! \cdot s}{(n-s)! \cdot n^{s+1}}.
		\]
	\end{enumerate}		
	
	���������� ������� �������� �������� $s$. �������, ��� ������������ ������� ���������� ���������� ���
	��������� $s$, �������� �� �������� �� $\left\{1,\ldots,n\right\}$, ������� ����������� ����� �������� ����������
	������ 0. �������������, ��� $s = 0$ ������������ �� ����� ������, � ��� $s > n$ ��� ����������, ��� ��� ������� �� �����
	$n$ ��������� �������� ���������. ������� ����������� �������� $s$ ���������� �������� ������:
	
	\begin{align*}
		\Expect s &= \sum\limits_{s=1}^n {s\cdot\PR(s)} = \sum\limits_{s=1}^n {s^2\cdot\frac{n!}{(n-s)! \cdot n^{s+1}}}
			= \sum\limits_{s=1}^n {\binom n s \frac{s!}{n^{s+1}} s^2} = \\
			&= \sum\limits_{s=1}^n { \binom n s \frac {s! \cdot s} {n^s} \left( 1 - \frac {n-s} {n} \right) } =
			\sum\limits_{s=1}^n { \left[\frac {s} {n^s} \binom n s s! - \frac {s} {n^s} \binom {n-1} s s!\right] } = \\
			&= \sum\limits_{s=1}^n { \frac {s} {n^s} \binom n s s! } -
				\sum\limits_{s=1}^n { \frac {s} {n^{s+1}} \binom n {s+1} (s+1)! } = \\
			&= \sum\limits_{s=1}^n { \frac {s} {n^s} \binom n s s! } -
				\sum\limits_{s=2}^n { \frac {s-1} {n^s} \binom n s s! } =
			\sum\limits_{s=1}^n { \frac {s} {n^s} \binom n s s! } -
				\sum\limits_{s=1}^n { \frac {s-1} {n^s} \binom n s s! } = \\
			&= \sum\limits_{s=1}^n { \frac {s!} {n^s} \binom n s }
			= \left\{ s! = \Gamma(s+1) = \int\limits_0^\infty {e^{-t} t^s} dt \right\}
			=  \sum\limits_{s=1}^n { \frac 1 {n^s} \binom n s \int\limits_0^\infty {e^{-t} t^s} dt } = \\
			&= \int\limits_0^\infty { e^{-t} \left[\sum\limits_{s=1}^n { \binom n s \left(\frac t n\right)^s }\right] dt }
			= \int\limits_0^\infty { e^{-t} \left[ \left( 1 + \frac t n \right)^n - 1 \right] dt } = \\
			&= \int\limits_0^\infty { e^{-t} \left( 1 + \frac t n \right)^n dt } - 1 =
			\int\limits_0^\infty { e^{\left\{n ln \left(1 + \frac t n \right) -t\right\}} dt } - 1 =
			\left\{ n \rightarrow \infty \right\} = \\
			&= \int\limits_0^\infty { e^{\left\{n \left[\frac t n - \frac {t^2} {2n^2} + o\left(\frac t n\right)^3\right] -t\right\}} dt } - 1 =
			\int\limits_0^\infty { e^{\left\{ t - \frac {t^2} {2n} + n o\left(\frac t n\right)^3 -t\right\}} dt } - 1 = \\
			&= \mathcal{O}\left( \int\limits_0^\infty {e ^ {\frac {-t^2} {2n}} dt} \right) = 
			\mathcal{O}\left( \int\limits_0^\infty {e ^ {-\left\{\frac {t} {\sqrt {2n}}\right\}^2} dt} \right) = 
			\left\{x = \frac {t} {\sqrt {2n}}\right\} = \\
			&= \mathcal{O}\left( \sqrt {2n} \int\limits_0^\infty {e ^ {-x^2} dx} \right) =
			\mathcal{O}\left( \sqrt {2n} \frac {\sqrt {\pi}} 2 \right) = \mathcal{O}\left(\sqrt {n}\right).
	\end{align*}
	
����� �� ��������������� ���������� �����-������� � ��������� ��������.
\end{proof}

\begin {thebibliography}{0}
	\bibitem{} {\it ���� �.�.} ��������� ����������������. �.1: �������� ���������. 3-� ���. ~--- �.: ��������, 2006. � �.1.2.11.3.
\end {thebibliography}


\end{document}