\documentclass[11pt,letterpaper]{article}
%% alternative for ACL stylesheet
% \documentclass[11pt,a4paper]{article}
% \usepackage{acl2015}
% \usepackage{times}
% \usepackage[round]{natbib} % for ACL stylesheet: https://clear.colorado.edu/CompSemWiki/index.php/Adding_ACL_Style_Citations
\usepackage[top=1in,bottom=1in,left=1in,right=1in]{geometry}
\usepackage{natbib}      % http://merkel.zoneo.net/Latex/natbib.php
\usepackage{palatino}
\bibpunct{(}{)}{;}{a}{,}{,}
\usepackage{chngpage}
\usepackage{stmaryrd}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{graphicx}
\usepackage{lscape}
\usepackage{subfigure}
\usepackage[usenames,dvipsnames]{color}
\definecolor{myblue}{rgb}{0,0.1,0.6}
\definecolor{mygreen}{rgb}{0,0.3,0.1}
\usepackage[colorlinks=true,linkcolor=black,citecolor=mygreen,urlcolor=myblue]{hyperref}
% possible colors: https://en.wikibooks.org/wiki/LaTeX/Colors#The_68_standard_colors_known_to_dvips
\newcommand{\bocomment}[1]{\textcolor{Bittersweet}{[#1 -BTO]}}
\newenvironment{itemizesquish}{\begin{list}{\labelitemi}{\setlength{\itemsep}{0em}\setlength{\labelwidth}{2em}\setlength{\leftmargin}{\labelwidth}\addtolength{\leftmargin}{\labelsep}}}{\end{list}}
\newcommand{\ignore}[1]{}
\newcommand{\transpose}{^\mathsf{T}}
\newcommand{\inner}[1]{\langle #1 \rangle}
\newcommand{\smallsec}[1]{\noindent \textbf{#1\ }}

\newcommand{\solution}[1]{{\color{Blue}[\textbf{Solution:} #1]}}
% \newcommand{\solution}[1]{}
\theoremstyle{definition}
\newtheorem{question}{Question}[section]
% \newtheorem{question}{Question}

\title{
    Homework 0: Probability Review and Survey
}
\author{CS 585, UMass Amherst, Fall 2016}

\date{}

\begin{document}
\maketitle

\newcommand{\spaceplz}{\vspace{1in}}

\section*{Note}

Wikipedia is a useful resource for basic probability.

Make a PDF file of your answers, and upload it to Moodle by Friday at 5pm.  We will only accept PDF format.

\section{Domain of a joint distribution}

\subsection{}

$A$ and $B$ are discrete random variables.  $A$ could take on one of 4 possible values.  $B$ could take on one of 3 possible values.  (In other words, the size of $\text{domain}(A)$ is 4, and the size of $\text{domain}(B)$ is 3.)  How many possible outcomes does the joint distribution $P(A,B)$ define probabilities for?

\subsection{}
Say we have a sequence of $n$ binary random variables
$A_1, A_2,\ldots A_n$.  How many possible outcomes
does the joint distribution $P(A_1,A_2,\ldots A_n)$ define probabilities for?

\section{Independence versus Basic Definitions}

Say we have three random variables $A$ and $B$ and $C$.
Note that we're using standard probability theory notation where $P(A,B)=P(B,A)$,
which simply means the joint probability of both $A$ and $B$ occurring.

%The MacKay reading is slightly different (he uses this notation to indicate ordering; we will come back to that later in the course).

\subsection{}
Which of the following statements is always true? .

\begin{enumerate}
\item $P(A|B) = P(B|A)$
\item $P(A,B) = P(A|B) P(B)$
\item $P(A,B) = P(A) P(B)$
\item $P(A|B) = P(A)$
\item $P(A,B,C) = P(A) P(C)$
\item $P(A,B,C) = P(A) P(B) P(C)$
\item $P(A,B,C) = P(A) P(B|A) P(C|A,B)$
\item $P(A) = \sum_{b \in \text{domain}(B)} P(A, B=b)$
\item $P(A) = \sum_{b \in \text{domain}(B)} P(A | B=b) P(B=b)$
\end{enumerate}

\subsection{}
Now assume that $A$, $B$, and $C$ are all independent of each other.
Which of these statements is true?

%
%\subsection{} Which of the following statements is true?
%
%\begin{align*}
%(\text{Statement\ A})\ \ \ \ \
%     P(A_1,A_2,\ldots,A_n) &= P(A_1) P(A_2) \ldots P(A_n) \\
%(\text{Statement\ B})\ \ \ \ \ 
%    P(A_1,A_2,\ldots,A_n) &= P(A_1) P(A_1, A_2) P(A_2,A_3) \ldots P(A_{n-1},A_n) \\
%    &= \prod_i P(A_{i-1}, A_i) \\
%(\text{Statement\ C})\ \ \ \ \ 
%    P(A_1,A_2,\ldots,A_n) &= P(A_1) P(A_2|A_1), P(A_3|A_2) \ldots P(A_n|A_{n-1}) 
%    \\
%    &= \prod_i P(A_i | A_{i-1}) \\
%(\text{Statement\ D})\ \ \ \ \ 
%    P(A_1,A_2,\ldots,A_n) &= P(A_1) P(A_2|A_1), P(A_3|A_1,A_2) \ldots P(A_n|A_1\ldots A_{n-1}) \\
%      &= \prod_i P(A_i | A_1,A_2,\ldots A_{i-1}) \\
%\end{align*}
%
%\noindent
%To be clear: In Statement B, each of the terms is the joint probability between two consecutive variables.  In Statement C, each of the conditional probabilities conditions on the immediate variable before it.  In Statement D, each of the conditional probabilities conditions on every variable before it.  That is, each term has the form $P(A_i \mid A_1, A_2,\ldots A_{i-1})$.)
%
%\subsection{} 
%Now assume that all of these random variables are independent of each other.  Which statements are true?

\section{Logarithms}

\subsection{Log-probs}
Let $p$ be a probability, so it is bounded to $[0,1]$ (between 0 and 1, inclusive).
What is the range of possible values for $\log(p)$?  Please be specific about open versus closed intervals.

\subsection{Prob ratios}
Let $p$ and $q$ both be probabilities.
What is the range of possible values for $p/q$?

\subsection{Log prob ratios}
What is the range of possible values for $\log(p/q)$?

%\section{Sum rule}
%
%\noindent
%The ``law of total probability'' or the ``sum rule'' can be stated as either of the following.
%
%\[ P(A) = \sum_{b \in \text{dom}(B)} P(A,B=b) \]
%\[ P(A) = \sum_{b \in \text{dom}(B)} P(A|B=b) P(B=b) \]
%
%\noindent
%Please give an English explanation for what this means.

%Start with the joint distribution over three variables, $P(A,B,C)$, and derive an equivalent expression that only uses the following three terms:
%
%    $P(A|B=b)$, $P(B=b|C=c)$, and $P(C=c)$
%
%\noindent
%Your final answer can be a sum, product, or combination of sums and products, of the three terms above. For example, $\sum_{b \in \text{dom}(B)} \prod_{c \in \text{dom}(C)} P(A|B=b)+P(C=c) P(B=b|C=c)$ legally satisfies this requirement, though it is a wrong answer because it is not equivalent to $P(A,B,C)$.  In order to derive the answer, you should start with $P(A,B,C)$ and only apply the sum rule.

\section{Deriving Bayes Rule}

The definition of conditional probability can be written as $P(A,B) = P(A|B)P(B)$ or alternatively as $P(A|B) = P(A,B)/P(B)$.
Starting from this, derive Bayes Rule, in this form:

\[ P(A|B) = \frac{P(B|A) P(A)}{P(B)} \]

\noindent
It should take only a few lines to prove/derive this.  Note that you can apply the definition of conditional probability not just for $P(A,B)$ but also for $P(B,A)$.  Here we are using standard notation where comma indicates conjunction/intersection so order of variables doesn't matter when defining a joint event.

\section{Survey}

\subsection{}
What natural languages do you know?  Which is your favorite?

\subsection{}
What programming languages do you know?  Which is your favorite?

\subsection{}
What do you hope to get out of this course?

%\bibliographystyle{plainnat}
%\bibliography{brenocon}
\end{document}
