%10.11.13
\documentclass[a4paper, 12pt]{article}
%\usepackage[magyar]{babel}
\usepackage{t1enc}
\usepackage[latin2]{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 2012
\end{center}
\noindent
Every week, the assigned homeworks are worth 1 point in total.

\begin{itemize}
%
 \item[{\bf HW 1:}] (due date: 2012.09.14.)
 \begin{itemize}
   \item[HW 1.1] $70\%$ of students at the technical university are boys, $30\%$ are girls. $20\%$ of the boys and $75\%$ of the girls have long hair. Choosing a \emph{long haired} student at random, what is the probability that we choose a girl?
%
   \item[HW 1.2] We roll a red die and we denote the number rolled by $X$. After that, we roll $X$ green dice, and denote by $Y$ the \emph{sum} of the numbers rolled on the green dice. What is the expectation of $Y$?
 \end{itemize}
%
 \item[{\bf HW 2:}] (due date: 2012.09.21.)
 \begin{itemize}
  \item[HW 2.1] The generating function of a nonnegative integer valued random variable is
  $$g(z) = \frac38 + \frac38 z + \frac18 z^2 + \frac18 z^3$$. What is the discrete probability distribution (namely the probabilities $\prob(X=k)$)? What is the expectation and variance of $X$?
%
  \item[HW 2.2] We toss a fair coin $3$ times, and a biased coin with $\prob(heads)=\frac13$ also three times. Let $Z$ denote the \emph{total} number of heads seen. Calculate the generating function of $Z$.
 \end{itemize}
%
\item[{\bf HW 3:}] (due date: 2012.09.28.)
\begin{itemize}
\item[HW 3.1] We keep rolling a fair die until we first roll a $6$. Let $X$ denote the \emph{sum} of the numbers rolled before (and not including) that $6$. Calculate
\begin{enumerate}[a.)]
\item the generating function of $X$,
\item the expectation of $X$,
\item the variance of $X$.
\end{enumerate}
\emph{(Warning: What is the \emph{conditional} distribution of a number rolled \emph{under the condition that it's not a $6$}?)}
%
\item[HW 3.2]
Harry is organizing a \emph{pyramid scheme} in his family.\\ (See http://en.wikipedia.org/wiki/Pyramid\_scheme) The participants are not too persistent: every participant keeps trying to recruit new participants until the first failure (i.e. until he is first rejected). The probability of such a failure is $p$ at every recruit attempt, independently of the history of the scheme.

The first participant is Harry, he forms the $0$-th generation alone. The first generation consists of those recruited (directly) by Harry. The second generation consists of those recruited (directly) by members of the first generation, and so on.

Let $Z_k$ denote the size of the $k$-th generation ($k=0,1,2,\dots$), and let $N$ denote the total number of participants in the scheme (meaning $N=\sum_{k=0}^\infty Z_k$).

Answer the questions below
\begin{enumerate}[I.]
 \item for $p=\frac{2}{3}$,
 \item for $p=\frac{1}{3}$:
\end{enumerate}
%
\begin{enumerate}[a.)]
 \item What is the generating function of $Z_2$?
 \item What is the expectation of $Z_{10}$?
 \item How much is the probability $\prob(Z_3=0)$?
 \item What is the probability that the scheme dies out (that is, one of the generations will already be empty)?
 \item What is the expectation of $N$?
 \item What is the generating function of $N$?
\end{enumerate}
%
\end{itemize}
%
%
\item[{\bf HW 4:}] (due date: 2012.10.08.)
\begin{itemize}
\item[HW 4.1]
Let $X_1,X_2,\dots,X_n$ be independent, identically distributed random variables having Bernoulli distribution with parameter $p=\frac12$ (meaning $\prob(X_i=1)=p=1-\prob(X_i=0)=\frac12$). Let $n=10^6$ and $S_n=X_1+X_2+\dots +X_n$ (so $S_n\sim Bin(n=10^6;p=\frac12)$).
\begin{enumerate}[a.)]
\item If for some $K\in(0;10^6)$ we approximate the probability $\prob(S_n<K)$ using the central limit theorem, at most how big can the error in this estimate be, according to the Berry-Esséen theorem? (Warning: In some sources, the simplest form of the theorem stated is about random variables \emph{with zero expectation}. The Bernoullli distribution is \emph{not like that}.) (The constant $C$ in the Berry-Esséen theorem can be chosen as $C=0.4784$ (due to a result from 2010).)
%
\item Use the Hoeffding inequality to find a bound $K$, for which we can be sure that $$\prob(S_n > K)\le 10^{-8}.$$
Denote this bound $K$ as $K_H$.
%
\item Calculate the approximate value of the probability $\prob(S_n > K_H)$ using the Cramer theorem. Hint: the moment generating function of the Bernoulli distribution with parameter $p$ is $M(\lambda)=1-p+pe^\lambda$, from which the Cramer rate function is $$I(x)=x\ln\frac{(1-p)x}{p(1-x)}-\ln\frac{1-p}{1-x}.$$
\end{enumerate}
%
\end{itemize}

\item[{\bf HW 5:}] (due date: 2012.10.17.)
\begin{itemize}
\item[HW 5.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_osztalyokhoz}
 % 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 5.2]
John drives his car to work in London every day. According to his observations, the weather can be of three sorts: 
\emph{rain}, \emph{shower} or \emph{cloudburst}. Based on his experience, the weather of a certain day allows us to guess the weather of the next day in the following probabilistic sense:
$$\prob(\text{rain tomorrow} | \text{rain today})=1/10,$$
$$\prob(\text{cloudburst tomorrow} | \text{rain today})=6/10,$$
$$\prob(\text{rain tomorrow} | \text{cloudburst today})=2/10,$$
$$\prob(\text{cloudburst tomorrow} | \text{cloudburst today})=4/10,$$
$$\prob(\text{cloudburst tomorrow} | \text{shower today})=5/10,$$
$$\prob(\text{shower tomorrow} | \text{shower today})=4/10.$$
Let us denote the states of the weather by numbers: $0:=\text{``rain''}$, $1:=\text{``shower''}$, $2:=\text{``cloudburst''}$. 
Let us model the sequence of John's morning observations by a time homogeneous Markov chain.
\begin{enumerate}[a.)]
 \item Write the Markov transition matrix $P$. (Warning: the transition probabilities above are not in order.)
 \item Assuming that it is raining on the 1-st of April, what is the probability of the observation sequence ``00012'' (starting with the 1-st of April)?
 \item Assuming that it is raining on the 1-st of April, what is the probability that there is shower on the 3-rd of April?
 \item Assuming that it is raining on the 1-st of April, what is the approximate probability that there is shower on the 30-th of April?
 \item What proportion of the mornings has a shower, on the long run?
 \item If there is rain, John spends $20$ minutes driving in a traffic jam, but if there is shower, he spends $30$, and if there is a cloudburst, then $70$ minutes. How much time does he spend in the morning traffic jam, in daily average, on the long run?
\end{enumerate}
%
\end{itemize}



\end{itemize}



% %
% \item[{\bf 5.HF:}] (Bead\'asi hat\'arid\H o: 2012.03.13. Mivel cselesnek bizonyult, segítség után módosított határidő: 2012.03.20.)
% \begin{itemize}
% \item[HF 5.1]
% Egy lépcsőházban $3$ villanykörte van folyamatosan felkapcsolva. Mindegyik kiég időnként, mégpedig exponenciális eloszlású véletlen idő elteltével, $1$ rátával. (Az időt években mérjük, vagyis a körték átlagosan egy évig bírják.) Szintén véletlen időközönként, szintén $1$ rátával arra jár a gondnok, és az összes kiégett körtét jóra cseréli. Jelölje $X_t$ a $t$-kor világító égők számát. $X_t$ folytonos idejű Markov lánc.
% \begin{enumerate}[a.)]
%  \item Írjuk fel $X_t$ infinitezimális generátorát!
%  \item Adjuk meg a folytonos idejű Markov lánc $\underline{\lambda}$ ráta-vektorát (vagyis az egyes állapotokból történő elugrás rátáit), és a beágyazott \emph{diszkrét idejű} Markov lánc $Q$ átmenetmátrixát!
%  \item Mi $X_t$ stacionárius eloszlása?
%  \item Hosszú távon az idő mekkora hányadában van a lépcsőházban töksötét (vagyis nem világít egy égő se)?
%  \item Egy működő villanykörte villanyszámlája időegységenként (évente) $1$ batka. Mennyi az összes égő egy évre eső átlagos villanyszámlája hosszú távon?
%  \item Feltéve, hogy $t=0$-kor mindhárom égő működött, mi annak a valószínűsége, hogy $t$-kor is mind működik? Ezt elvileg mindenki ki tudja számolni, de megelégszem azzal, ha megadjátok ennek a függvénynek ($\prob(X_t=3|X_0=3)$-nak) a határértékét és az ahhoz jövő fő hibatag nagyságrendjét.
% \end{enumerate}
% %%
% \end{itemize}
% %
% \item[{\bf 6.HF:}] (``bónusz feladatsor'' +1 pontért. Bead\'asi hat\'arid\H o: 2012.03.20.)
% \begin{itemize}
% \item[HF 6.1]
% $9$-elemű mintát vettünk az $X$ valószínűségi változóból, ami (optimista) geometriai eloszlású, számunkra ismeretlen $p$ paraméterrel. Ezt kaptuk: $1,8,7,11,6,5,6,7,4,3$. Adjunk maximum likelyhood becslést $p$-re! A feladatot az is számolja rendesen végig, aki tudja, hogy mi fog kijönni.
% \item[HF 6.2]
% Egy műszer hosszúságot mér $\mu m$-ben. A mérés hibájáról tudjuk, hogy normális eloszlású:
% $hiba\sim \mathcal{N}(m,\sigma^2)$, sőt a szórásnégyzet is ismert: $\sigma^2=2$. A gyártó pedig azt állítja, hogy $m=0$.
% Ennek ellenőrzésére $6$ próbamérést végeztünk pontosan ismert hosszúságokon, és a következő hibákat kaptuk ($\mu m$-ben):
% $0.5$; $0.7$; $-0.9$; $-0.4$; $0.01$; $1.1$. Döntsünk $99\%$-os konfidenciaszinten (vagyis $\varepsilon=0.01$) arról a hipotézisről, hogy a gyártó igazat állít.
% \end{itemize}
%
%\end{itemize}%feladatsor-szamozas

\end{document}

