%10.11.13
\documentclass[a4paper, 12pt]{article}
%\usepackage[magyar]{babel}
\usepackage{t1enc}
\usepackage[utf8]{inputenc}
\usepackage{tabularx}
\usepackage{hhline}
\usepackage[leqno,intlimits]{amsmath}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{epsfig}
%\usepackage{subfigure}
\usepackage{psfrag}
\usepackage{enumerate}
\usepackage{mdwlist}
% \usepackage{enumitem}
\usepackage{color}
%\usepackage{enumitem}


%\hyphenpenalty=10
\tolerance=1000

\setlength{\marginparwidth}{0pt}
\addtolength{\textwidth}{100pt}
\addtolength{\hoffset}{-50pt}
\addtolength{\textheight}{160pt}
\setlength{\voffset}{-80pt}

\newcommand*{\hop}{\bigskip\noindent}
\newcommand{\TT}{\mathbb{T}}
\newcommand{\Sb}{\mathbb{S}}
\newcommand{\Rb}{\mathbb{R}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\EE}{\mathbb{E}}
\newcommand{\cF}{\mathcal{F}}
\newcommand{\prob}{\mathbb{P}}

\begin{document}
\begin{center}
{\bf Advanced Mathematics for Electrical Engineers B\\
homeworks for the ``Stochastics 2'' part}\\
fall semester 2013
\end{center}
\noindent
Every week, the assigned homeworks are worth 1 point in total.

\begin{itemize}
%
 \item[{\bf HW 1:}] (due date: 20.09.2013)
 \begin{itemize}
   \item[HW 1.1] We roll a fair die and denote the number rolled by $X$. We than toss a fair coin $X$ times, and denote the number of heads by $Y$.
    \begin{enumerate}[a.)]
     \item Calculate the expectation of $Y$.
     \item Find the conditional probability $\prob(X=5\,|\,Y=5).$
    \end{enumerate}
 \end{itemize}
%
 \item[{\bf HW 2:}] (due date: 04.10.2013)
  \begin{itemize}
   \item[HW 2.1]
   Jerry is serving customers in his computer store. Initially there is a single costumer, Tom there. While Tom is served, a random number of further customers -- having a pessimistic Geometric distribution with parameter $p$ -- joins the queue. Then again, while each customer is served, the number of those joining the queue has the same pessimistic Geometric distribution with parameter $p$, and is independent from whatever happened before.
   
   The first customer, Tom, forms the $0$-th generation alone. We call the ``first generation'' those who arrive while Tom is being sreved. The ``second generation'' consists of those arriving while members of the first generation are being served, and so on.

   Jerry can only take a rest when the queue becomes empty.
   
Let $Z_k$ denote the size of the $k$-th generation ($k=0,1,2,\dots$), and let $N$ denote the total number of customers Jerry has to serve before he can take a rest (meaning $N=\sum_{k=0}^\infty Z_k$).

Answer the questions below
\begin{enumerate}[I.]
 \item for $p=\frac{3}{4}$,
 \item for $p=\frac{1}{4}$:
\end{enumerate}
%
\begin{enumerate}[a.)]
 \item What is the generating function of $Z_2$?
 \item What is the expectation of $Z_{8}$?
 \item How much is the probability $\prob(Z_4=0)$?
 \item What is the probability that Jerry can (sooner or later) take a rest (that is, one of the generations will already be empty)?
 \item What is the expectation of $N$?
\end{enumerate}

  
\end{itemize}

\item[{\bf HW 3:}] (due date: 07.10.2013)
  \begin{itemize}
   \item[HW 3.1]
   An internet service provider has 3600 costumers. On Monday at 8 pm, each costumer has a random demand of bandwidth, which, if measured in Mbit/s, is uniformly distributed in the interval $[0;4]$. There will be a tie-up in the service if the total demand exceeds the total bandwidth of $8000$ Mbit/s that the provider can use.
    \begin{enumerate}[a.)]
     \item The provider is trying to use the central limit theorem to estimate the probability that there will be a tie-up (on Monday at 8 pm). At most how much will \emph{the error they make with that estimate} be, according to the Berry-Esseen theorem?
     \item Use the Hoeffding inequality to estimate the probability of a tie-up.
    \end{enumerate}
\end{itemize}

\item[{\bf HW 4:}] (due date: 14.10.2013)
\begin{itemize}
\item[HW 4.1]
The graph shown in Figure~\ref{fig:ML_osztalyokhoz} shows the possible one-step transitions (that have positive probability) for a time-homogeneous discrete time Markov chain. Classify the states, grouping in the same class those that communicate with each other. For every class, decide
\begin{itemize}
 \item if it is essential or inessential,
 \item if it is recurrent or transient,
 \item its period, and whether it is periodic or aperiodic.
\end{itemize}
%
\begin{figure}[hbt]
 \centering
 \includegraphics{ML_osztalyokhoz2}
 % ML_osztalyokhoz.eps: 0x0 pixel, 300dpi, 0.00x0.00 cm, bb=0 0 127 117
 \caption{Graph representation of a Markov chain (without probabilities)}
 \label{fig:ML_osztalyokhoz}
\end{figure}
%
\item[HW 4.2]
A computer program solves tasks that consist of four subtasks each. At the end of each time period, we record which subtask it is working on -- and, if it happens to be idle, waiting for a new task, then we write $0$ -- so the program can be in the states $0,1,2,3,4$. From the states $1$, $2$, $3$ and $4$, the program can move on to the next state with probability $\frac12$ in any time period, independently of what happened before (here we mean that $4$ is followed by $0$). With the remaining probability $\frac12$ it keeps working on the same subtask. If the program is in the idle state $0$, then, in every time period, it moves to state $1$ with probability $\frac{1}{10}$ (independently of the past), otherwise it stays idle.

Model the sequence of states recorded by a time-homogeneous Markov chain.

\begin{enumerate}[a.)]
 \item Give the Markov transition matrix $P$.
 \item Assuming that the program was initially in the $0$ state, what is the probability of observing the sequence ``0001223440''? (We also record the initial state.)
 \item Assuming that the initial state is $0$, what is the probability that the program will be working exactly on subtask $1$ after $3$ time units?
 \item Assuming that the initial state is $0$, what is the approximate probability that the program will be in state $0$ again after $1000$ time units?
 \end{enumerate}
%
\end{itemize}
%
\item[{\bf HW 5:}] (due date: 25.10.2013)
\begin{itemize}
\item[HW 5.1]
Requests to a network server arrive at random times, and enter the queue. The time between the arrivals of two consecutive requests is independent of the past, exponentially distributed, and its expected value is $3$ seconds. 

When there is no request in the queue, the server does nothing. If there are $1$ or $2$ requests, then one process works on the first one, and completes it during an exponentially distributed random time with expected value $4$ seconds (independently of the past).

If there are $3$ or $4$ requests queueing, then the resources of the server are doubled, thus there will be two processes working simultaneously on (the first) two requests, and complete them during exponentially distributed random times with expected value $4$ seconds, independently of each other (and the past).

There can be at most $4$ requests in the queue. If there are already $4$, possibly arriving further requests are lost.

Let $X_t$ denote the number of requests in the queue at time $t$. $X_t$ is a continuous time Markov chain.

\begin{enumerate}[a.)]
 \item Give the state space of the Markov chain $X_t$.
 \item Give the possible jumps of the Markov chain and the rates of these jumps. (Measure time in seconds.) \textbf{Warning,} one has to be careful when finding out rates of jumps starting from states $3$ and $4$. (Hint: if there are two processes running simultaneously, these will surely not complete exactly at the same time. A jump occurs when \emph{one of them} completes. What is the rate of this?)
 \item Calculate the infinitesimal generator, the rate vector (or stay time parameter vector) $\underline{\lambda}$ and the transition matrix $Q$ of the embedded discrete time Markov chain.
 \item What is the stationary distribution of $X_t$?
 \item In what proportion of the time will there be $4$ requests in the queue on the long run?
 \item On the long run, what proportion of arriving requests is lost? (This needs some thinking, but is not hard.)
 \item Doing nothing is free, but running a process costs $1$ penny per second. (So if there are two processes running, that's two pence per second.) How much is the average cost per second of the operation of this server on the long run?
\end{enumerate}
  
\end{itemize}
%
\end{itemize}
%

\end{document}

