%\documentclass[12pt,a4paper, german]{article}
%\usepackage{a4kopka}
\documentclass[12pt,a4paper]{article}
\usepackage{ngerman}
%\usepackage{fleqn}
\usepackage{array}
\usepackage[latin1]{inputenc}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsfonts}
%\usepackage{mathbbol}
\usepackage{amstext}
%\usepackage{fancyhdr}
\usepackage{relsize}
%\usepackage{epic}
\usepackage{graphics}
\usepackage{graphicx}
\usepackage[T1]{fontenc}
\usepackage{a4wide}
\usepackage{makeidx}\usepackage{german}
\usepackage{textcomp}


\newcommand{\D}{\displaystyle}
%%%%%%%%%%%%%%%%%%%%

\newcommand{\IR}{{\mathbb{R}}}
\newcommand{\IN}{{\mathbb{N}}}
\newcommand{\IZ}{{\mathbb{Z}}}
\newcommand{\IF}{{\mathbb{F}}}
\newcommand{\IK}{{\mathbb{K}}}
\newcommand{\IQ}{{\mathbb{Q}}}
\newcommand{\IC}{{\mathbb{C}}}
\newcommand{\IP}{{\mathbb{P}}}
\newcommand{\IE}{{\mathbb{E}}}

\newcommand{\ep}{{\varepsilon}}
\newcommand{\ph}{{\varphi}}
\newcommand{\thet}{{\vartheta}}
\newcommand{\rh}{{\varrho}}
\newcommand{\de}{{\delta}}
\newcommand{\la}{{(}}
\newcommand{\ra}{{)}}
\newcommand{\Om}{{\Omega}}
\newcommand{\al}{{\alpha}}
\newcommand{\be}{{\beta}}
\newcommand{\ga}{{\gamma}}
\newcommand{\gwh}{{\widehat{\gamma}}}
\newcommand{\om}{{\omega}}
\newcommand{\La}{{\Lambda}}
\newcommand{\Ga}{{\Gamma}}
\newcommand{\De}{{\Delta}}
\newcommand{\wh}{{\widehat}}

\newcommand{\foh}{{\mathfrak{h}}}

\newcommand{\nach}{{\rightarrow}}
\newcommand{\Nach}{{\,\rightarrow\,}}
\newcommand{\Fou}{{\mathcal{F}}}
\newcommand{\sk}{{\,|\,}}

\def\be{\begin{eqnarray*}}
\def\ee{\end{eqnarray*}}
\def\bel{\begin{eqnarray}}
\def\eel{\end{eqnarray}}

\def\ex{\exists}
\def\all{\forall}

\def\a{\alpha}
\def\eh{\frac{1}{2}}
\def\A{\mathcal{A}}
\def\R{\mathbb{R}}
\def\N{\mathbb{N}}\def\NN{\mathbb{N}}
\def\E{\mathbb{E}}
\def\P{\mathbb{P}}
\def\C{\mathbb{C}}
\def\B{\mathcal{B}}
\def\F{\mathcal{F}}
\def\S{\mathcal{S}}
\def\Z{\mathbb{Z}}
\def\O{\mathcal{O}}
\def\e{\epsilon}
\def\ep{\tilde{\delta}}
\def\d{\delta}
\def\lm{\lambda}
\def\id{\mathbb{I}}
\def\Sp{\textrm{Sp}}
\def\lili{\lim\limits}
\def\nn{\nonumber}
\def\fa{\bigwedge\limits}
\def\one{1}
\def\chiop{\chi_{\{\delta>L\}}}
\def\eqiv{\Longleftrightarrow}
\def\lra{\longrightarrow}
\newcommand{\ab}[1]{\left( #1\right)}


%\newcommand{\cosh}{\mbox{cosh}}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{remarks}[theorem]{Remarks}
%%%%%%%%%%%%%%%%%%%%

\addtolength{\voffset}{-15pt} \addtolength{\textheight}{-10pt}
%\addtolength{\textheight}{-11pt} \addtolength{\headsep}{6pt}

\setlength{\parskip}{10pt plus 2pt minus 1pt}
\setlength{\parindent}{0pt}
\newcommand{\wk}{\mbox{$\,<$\hspace{-5pt}\footnotesize )$\,$}}
\thispagestyle{empty} \addtolength{\voffset}{15pt}

\setlength{\textheight}{10in}

\begin{document}

\rule{\textwidth}{0.3pt}
\begin{center}
\textbf{\large Analysis auf Graphen}
\end{center}
\textbf{Wintersemester 2015/2016\hfill Prof. Dr. M. Keller}

\rule{\textwidth}{0.3pt}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% Hier geht's los
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\textbf{Blatt 10}\hfill % Nr des Blatts
\textbf{Abgabe 20.01.2016}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Sei $(b,c)$ ein endlicher Graph über $(X,\deg)$ mit
\begin{align*}
    \deg(x)=\sum_{y\in X}b(x,y)+c(x).
\end{align*}
Sei $P:\ell^{2}(X,\deg)\to\ell^{2}(X,\deg)$ ein Operator mit Matrix
$p:X\times X\to [0,\infty)$ gegeben durch
\begin{align*}
    p(x,y)=\frac{b(x,y)}{\deg(x)}
\end{align*}
d.h.
$$Pf(x)=\sum_{y\in X}p(x,y)f(y).$$
Sei weiterhin $p_{n}:X\times X\to[0,\infty)$ die Matrix der $n$-ten
Potenz $P^{n}=P\circ\ldots\circ P$ des Operators $P$. Sei
$Y=(Y_{n})$ die Markovkette die gegeben ist durch die
Übergangswahrscheinlichkeiten
\begin{align*}
    \mathbb{P}(Y_{n+1}=y\mid Y_{n}=x)=p(x,y),\quad x,y\in X.
\end{align*}
Weiterhin sei $L=L_{b,c,\deg}$ der zu $(b,c)$ über $(X,\deg)$
gehörige Operator und $\lambda_{0}=\inf\sigma(L)$ der kleinste
Eigenwert. Für einen linearen Operator auf $\ell^{2}(X,m)$ sei
$\|A\|=\sup_{\|f\|=1}\|Af\|$ die Operatornorm.




\begin{itemize}




\item[(1)]
Sei der Graph zusammenhängend. Zeigen Sie, dass $\lambda_{0}=0$ dann
und nur dann wenn  für die Operatornorm von $P$ gilt $\|P\|=1$.
Zeigen sie weiterhin, falls $\|P\|<1$, dann
\begin{align*}
    \lim_{\al\downarrow 0}(L+\al)^{-1}f
    =\sum_{n=0}^{\infty}P^{n}f,
\end{align*}
  für alle $f\in
\ell^{2}(X,\deg)$. (Tipp: Teleskopsumme)

\newpage

\item[(2)]Zeigen Sie, dass die Gleichung in Aufgabe (1) auch
   für $\|P\|=1$ mit $f\ge0$ gilt, wobei allerdings beide Seiten
   der Gleichung in diesem Fall $+\infty$ sind.


\item[(3)] Zeigen Sie, dass für alle $x\in X$ der  Grenzwert
\begin{align*}
    \rho:=\lim_{n\to\infty}\|P^{n}\|^{1/n}
\end{align*}
existiert.


\item[(4)] Sei
\begin{align*}
    \rho_{x,y}=\limsup_{n\to\infty}p_{n}(x,y)^{1/n}
\end{align*}
für $x,y\in X$ für einen zusammenhängenden Graphen. Zeigen Sie, dass
für alle $x,y,x',y'\in X$ gilt
\begin{align*}
    \rho_{x,y}=\rho_{x',y'}=\rho=1-\lambda_{0}.
\end{align*}

 \end{itemize}

% \textbf{Zusatzaufgabe}

% \begin{itemize}
%   \item [(Z1)] Für $n\in\N\cup\{0\}$ sei
%$$R_{x}(n)=\mathbb{P}(\#\{Y_{k}=x, \, k\in \N_{0}\}=n\mid Y_{0}=x)
%$$ die Wahrscheinlichkeit, dass die Markovkette, die in $x$ startet
%sich genau $n$ mal in $x$ aufhält (d.h. $n-1$ mal zurückkehrt).

%Zeigen Sie, dass falls der Graph zusammenhängend ist
%\begin{align*}
 %   R_{x}(\infty)=R_{y}(\infty)\quad\mbox{und}\quad R_{x}(\infty)\in\{0,1\}.
%\end{align*}
%für alle $x,y\in X$ und $R_{\infty}(x)=0$ äquivalent ist zu
%$c\neq0$.
% \end{itemize}
\end{document}
