
\documentclass[11pt,a4paper]{article}

\usepackage{fullpage}
\usepackage{times}
\usepackage{epsfig}
\usepackage{amssymb}
\usepackage{amsfonts}
\usepackage{enumerate}
%\usepackage[ruled,vlined]{algorithm2e}


%\textwidth=400pt
%\textheight=600pt

\setlength{\textwidth}{14cm}
\setlength{\textheight}{23cm}
\setlength{\oddsidemargin}{0pt}

\renewcommand{\baselinestretch}{1.15}
\setlength{\parskip}{2mm}
\setlength{\parindent}{0pt}
%\input{psfig.sty}

\pagestyle{plain}
\def\thepage{\small{--- Page \arabic{page} of 4 ---}}
\newcommand{\R}{\ensuremath{\mathbb R}}
\newcommand{\Z}{\ensuremath{\mathbb Z}}
\newcommand{\N}{\ensuremath{\mathbb N}}
\newcommand{\Q}{\ensuremath{\mathbb Q}}
\newcommand{\E}{\mbox{E}}
%\newcommand{\c}{\ensuremath{\mathbb c}}
%\newcommand{\b}{\ensuremath{\mathbb b}}
\newcommand{\F}{\ensuremath{\mathcal F}}
\newcommand{\SymGrp}{\ensuremath{\mathfrak S}}
\newcommand{\pr}{\ensuremath{\mbox{Pr}}}
\newcommand{\com}[1]{\ensuremath{\overline{#1}}}
%\newcommand{\or}{\ensuremath{\vee}}

\newcommand{\remove}[1]{}
\newcommand{\size}[1]{\ensuremath{\left|#1\right|}}
\newcommand{\ceil}[1]{\ensuremath{\left\lceil#1\right\rceil}}
\newcommand{\floor}[1]{\ensuremath{\left\lfloor#1\right\rfloor}}
%\newcommand{\R}{\mathbb{R}}
%\newcommand{\c}{\mathbf{c}}
%\newcommand{\b}{\mathbf{b}}
\newcommand{\mb}[1]{\ensuremath{\mathbf #1}}
\newcommand{\poly}{\operatorname{poly}}
\newcommand{\polylog}{\operatorname{polylog}}
\newtheorem{theorem}{Theorem}
\newtheorem{prop}{Proposition}
\newtheorem{obs}{Observation}


\newcommand{\answerbox}[1][3\baselineskip]{%
    \noindent\framebox[\linewidth]{%
        \raisebox{0pt}[0pt][#1]{}%
    }\par\medskip%
}

%\usepackage[top=1in, bottom=1in, left=0.5in, right=0.5in,showframe]{geometry}
\usepackage[top=0.5in, bottom=0.5in, left=0.5in, right=0.5in]{geometry}
\usepackage{blindtext}
\pagestyle{plain}

\newenvironment{proof}{{\bf Proof:  }}{\hfill\rule{2mm}{2mm}}
\newenvironment{proofof}[1]{{\bf Proof of #1:  }}{\hfill\rule{2mm}{2mm}}
\newenvironment{proofofnobox}[1]{{\bf#1:  }}{}
\newenvironment{solution}{{\bf Solution:  }}{\hfill\rule{2mm}{2mm}}
\begin{document}
\noindent\fbox{%
    \parbox{\textwidth}{%
\begin{center}
{\large \bf INDIAN STATISTICAL INSTITUTE}

{\underline{\bf Class Test II}}

M Tech (CS) -- I Year, 2017-2018 (Semester - I)

{\it Probability and Stochastic Processes}
\end{center}

\hrulefill 

\medskip 
Date: 27.09.2018 \hspace{1.75in} Maximum Marks : 30  \hfill %\hspace{0.8in}
Duration : 1.0 hours 

\hrulefill 
\medskip 

{\bf Note:} The question paper is of 40 marks. 
Answer as much as you can, but the maximum you can score is 30. Answer a question within its allotted box.

\medskip 

\hrulefill
  
\medskip  
    
{\bf Course:} (M Tech/JRF/PLP) $\rule{14cm}{0.15mm}$

\medskip 

{\bf Name:} $\rule{8cm}{0.15mm}$ \hfill {\bf Roll Number:} $\rule{5cm}{0.15mm}$

}%
}

\begin{itemize}
\item[(Q1)]  Let $X$ and $Y$ be independent variables, $X$ being equally likely to take any value in $\{0,1,\ldots,m\}$, and $Y$ similarly in $\{0,1,\ldots,n\}$. Find the mass function of $Z=X+Y$. \hfill[10]
\end{itemize}

%\answerbox[28 
%\baselineskip]
{\bf Ans.~} Let $[k]=\{0,\ldots,k\}$. Note that $X \in [m],  Y \in [n]$ and $Z \in [m+n]$. For $z \in [m+n]$, let 
$N_z$ be the number of solutions to $x+y=z$ such that $x \in [m]$ and $y \in [n]$.
\begin{eqnarray*}
\pr(Z=z) &=& \sum\limits_{x \in [m], y\in [n]:x+y=z}\pr(X=x,Y=y)\\
&=& \sum\limits_{x \in [m], y\in [n]:x+y=z}\pr(X=x)\cdot \pr(Y=y)\\
&=&\frac{N_z}{(m+1)(n+1)}.
\end{eqnarray*}

\begin{itemize}
\item[(Q2)] Define $\mbox{var}(Y~|~X)$, the conditional variance of $Y$ given $X$. Show that $\mbox{var}(Y) = \mbox{E}(\mbox{var}(Y~|~X)) + \mbox{var}(\mbox{E}(Y~|~X))$.  \hfill[10]
\end{itemize}
{\bf Ans.~}
$\mbox{var}(Y~|~X)=\E\left( \left( Y-\E\left( Y~|~X \right) \right)^2~|~X\right)=\mbox{E}\left(\E(Y^2~|~X) - (\E(Y~|~X))^2\right)$. For the second part,
\begin{eqnarray*}
 && \mbox{E}(\mbox{var}(Y~|~X)) + \mbox{var}(\mbox{E}(Y~|~X))\\
&=& \left[\mbox{E}\left(\E(Y^2~|~X) - (\E(Y~|~X))^2\right)\right] + \left[\E\left((\mbox{\E}(Y~|~X))^2\right)- \left( \E(\mbox{E}(Y~|~X))\right)^2\right]~(\because \mbox{var}(Y)=\E(Y^2)-(\E(Y))^2)\\
&=& \mbox{E}\left(\E(Y^2~|~X)\right) - \E\left((\E(Y~|~X))^2\right) + \E\left((\mbox{\E}(Y~|~X))^2\right)- \left( \E(\mbox{E}(Y~|~X))\right)^2\\
&=&\mbox{E}\left(\E(Y^2~|~X)\right) - \left( \E(\mbox{E}(Y~|~X))\right)^2\\
&=&\E(Y^2) - (\E(Y))^2~(\because \E(\E(Y~|~X))=\E(Y))\\
&=& \mbox{var}(Y)
\end{eqnarray*}

%\answerbox[45  \baselineskip]


\begin{itemize}
\item[(Q3)] A coin shows heads with probability $p$. Let $X_n$ be the number of flips required to obtain a run of $n$ consecutive heads. Show that $\E(X_n) = \sum\limits_{k=1}^n p^{-k}$. \hfill[10]
\end{itemize}
%\answerbox[45 \baselineskip]
{\bf Ans.~} Let $X_k$ be the random variable that denotes the number of tosses to get $k$ consecutive heads.
Note that $\E[X_1]=\frac{1}{p}$. Observe that, for $n \geq 2$,
\begin{eqnarray*}
\E\left(X_n~|X_{n-1}\right)&=& p(X_{n-1}+1)+(1-p)(X_{n-1}+1+\E(X_n))\\
\E\left( \E\left(X_n~|X_{n-1}\right) \right)&=& \E \left( p(X_{n-1}+1)+(1-p)(X_{n-1}+1+\E(X_n)) \right)\\
\E(X_n)&=&p(\E(X_{n-1})+1)+(1-p)(\E(X_{n-1})+1+\E(X_n))\\
\E(X_n)&=&\frac{1}{p}(\E(X_{n-1})+1)
\end{eqnarray*}
One can get the desired result after solving the above recurrence.

\begin{itemize}
\item[(Q4)] Let $X_{1}, \, \dots, \, X_{n}$ be independent random variables with 
$\mathrm{Pr} \left( X_{i} = 1\right) = \mathrm{Pr} \left( X_{i} = -1\right) = \frac{1}{2}$. 
Let $X = \sum_{i=1}^{n} X_{i}$. Show that for all $a > 0$, $\mathrm{Pr} \left( X \geq a \right) \leq e^{-a^{2}/2n}$.  
\hfill[10]

\end{itemize}
%\answerbox[44 \baselineskip]
{\bf Ans.~} Please refer Mitzenmacher and Utfal Theorem 4.7.
%The moment generating function of $X_i$, that is, $\mbox{MGF}(X_i)=\E[e^{tX}]=\frac{1}{2}(e^t+e^{-t})$. Observe that $\mbox{MGF(X)}=\frac{1}{2^n}(e^t+e^{-t})^n$.
\end{document}
