\documentclass[a4paper,12pt]{article}
\usepackage[utf8]{inputenc}


\usepackage[english]{babel}
\usepackage{tabularx}
\usepackage{hhline}
%\usepackage[leqno,intlimits]{amsmath}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{epsfig}
%\usepackage{subfigure}
\usepackage{psfrag}
\usepackage{enumerate}
\usepackage{mdwlist}

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

\setlength{\marginparwidth}{0pt}
\addtolength{\textwidth}{4cm}
\addtolength{\hoffset}{-2cm}
\addtolength{\textheight}{4cm}
\setlength{\voffset}{-3cm}

\def\diff{\,\mathrm{d}}
\def\prob{\mathbb{P}}
\def\expect{\mathbb{E}}

\def\IR{\mathbb{R}}
\def\IN{\mathbb{N}}

\def\sigalg{\mathcal{F}}

\newcommand{\li}{\lim\limits_{n\to\infty}}


\newtheorem{theorem}{Theorem}
\newtheorem{definition}{Definition}



\begin{document}
\begin{center}
{\bf Probability 1\\
CEU Budapest, fall semester 2013}\\
Imre Péter Tóth\\
{\bf Homework sheet 8 -- due on 18.11.2013 -- and exercises for practice}\\
\end{center}


\begin{enumerate}[8.1]
%
\item \textbf{(homework)} Durrett~\cite{durrett}, Exercise 5.2.5
%
\item \textbf{(homework)} Durrett~\cite{durrett}, Exercise 5.2.6
%
\item \label{ex:life_universe_} \emph{Life, the Universe, and Everything.} Arthur decides to keep rolling a fair die until he manages to roll two $6$-es consecutively. What is the expected number of rolls he needs?
%
\item \textbf{(homework)} Bob keeps tossing a fair coin and makes notes of the results: he writes ``H'' for heads and ``T'' for tails. Calculate the expected number of tosses
\begin{enumerate}[a.)]
 \item until the charater sequence ``HTHT'' shows up,
 \item until the charater sequence ``THTT'' shows up.
\end{enumerate}
%
\item Alice and Bob keep tossing a fair coin until either the word $A$:=``HTHT'' or the word $B$:=``THTT'' shows up. If the word appearing first is $A$, then Alice wins, and if $B$, then Bob. Introduce the notation $p_A:=\prob(\text{Alice wins})$, $p_B:=\prob(\text{Bob wins})$. Let $\tau$ be the random time when the game ends.
\begin{enumerate}[a.)]
 \item Think of a casino, as in the solution of the ABRACADABRA problem \cite{ai}, where all players bet for (consecutive letters of) the word $A$. Using the capital of this casino as a martingale, express $\expect\tau$ using $p_A$ and $p_B$.  
 \item Now think of another casino, where all players bet for (consecutive letters of) the word $B$. Using the capital of this other casino as a martingale, get another expression for $\expect\tau$ using $p_A$ and $p_B$.
 \item Solve the system of equations formed by the two equations above, to calculate $\expect\tau$, $p_A$ and $p_B$.
\end{enumerate}
%
\item A monkey keeps pressing keys of a typewriter with $26$ keys printing the letters of the English alphabet, uniformly and independently of the past, until the word ``ABRACADABRA'' shows up. Denote this random time by $\tau$. Beside the monkey -- as in the original ABRACADABRA solution \cite{ai}-- operates a casino where players can always bet for the next key pressed in a fair game: if their guess is wrong, they lose their bet entirely, while if it is correct, they lose it and get back $26$ times more.

Before every keypress, a new player arrives, who will bet all his money first on ``A'', then on ``B'', then on ``R'', etc. through the ABRACADABRA sequence, as long as he keeps winning or the game ends. (If he loses once, he goes home immediately.) This is just like in the original ABRACADABRA solution.

However, the later a player arrives, the less money he has to play with: there is some fixed $z\in(0,1)$ such that the $n$-th player arrives with $\$z^{n-1}$.

Show that the fortune of the casino is a martingale, and use the optional stopping theorem to calculate the generating function of $\tau$.
%
\item 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$).

\emph{$0$-th question: What is the distribution of $Z_1$ (which is the same as the distribution of the number of participants recruited by any fixed member of the scheme)? This distribution has a name.}

Answer the questions below
\begin{enumerate}[I.]
 \item for $p=\frac{2}{3}$,
 \item for $p=\frac{1}{2}$,
 \item for $p=\frac{1}{3}$:
\end{enumerate}
%
\begin{enumerate}[a.)]
 \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 In case ``not dying out'' has positive probability, what is the growth rate of $Z_n$ on this event? 
\end{enumerate}
%
\item Let $N,X_1,X_2,X_3,\dots$ be independent, and let them all have (optimistic) geometric ditribution with parameter $p=\frac16$. Calculate the expectation of
$$S=:\sum_{k=1}^N (X_k+1).$$
What has this got to do with Exercise~\ref{ex:life_universe_}?

\emph{Hint: use the method of characteristic functions, or simply apply the theorem we had about sums with random number of terms.}

\end{enumerate}

\begin{thebibliography}{1}
 \bibitem{durrett}Durrett, R. \emph{Probability: Theory and Examples}. \textbf{4th} edition, Cambridge University Press (2010)
 \bibitem{ai}Ai, Di. \emph{Martingales and the ABRACADABRA problem}.\\ \verb+http://math.uchicago.edu/~may/VIGRE/VIGRE2011/REUPapers/Ai.pdf+ (2011)
\end{thebibliography}


\end{document}

