\documentclass[11pt]{article}

%\usepackage{customizations}
\usepackage{listings}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage[enableskew]{youngtab}
\usepackage{hyperref}
\usepackage{graphicx}

\renewcommand{\mod}[1]{\ensuremath{\;\textrm{mod }{#1}}}
\usepackage[all]{xy}



\textwidth=15cm
\oddsidemargin=0.7cm
\voffset=-1cm
\textheight=20cm

\begin{document}

\newcommand{\x}{\times}

\title{
  MATH 157: Mathematics in the world \\
  \Large{Homework 6 (Due March 26th, 2019 at 1:00PM)}
}
\date{}

\maketitle

\vspace{-1cm}

\subsection*{Problem 0 - Final project vs Final exam}

\textbf{In case of the choice of a final project, please look at the list of possible topics, that you can find among the Files on Canvas, and choose two or three of them. Feel free to come up with your own ones if you have some other interesting ideas for final projects. Me and Patrick will meet then personally with everyone of you.}

\vspace{0.5cm}

\textbf{Please solve all $6$ problems.}







\subsection*{Problem 1}

The tiny nation of Chocoladia focuses its industry on chocolate production. While Chocoladia has no national holidays (every day is a chocolate day), the labor laws require chocolate factory owners to give all of their workers a holiday every time one of them has a birthday. For example, if a factory employs ten people (including the owner) with distinct birthdays, each of them will receive ten days of holidays a year. Furthermore, the labor laws require employers to hire without discrimination on the basis of birthdays.

Imagine you are planning to start a chocolate factory.
\begin{enumerate}
\item
  How many workers would you hire if you would like to maximize the output of your operation?
  \footnote{
    Hint: Assume there are $n$ days in the year and you have hired $k$ workers. What is the probability that any given day is a working day in your factory? What is the expected number of man-days your workers will produce?

    The problem boils down to finding the value of $k$ which maximizes the expected number of man-days. You can do this by hand, but if the solution is not clear, feel free to use a computer too.

    For simplicity, you can also assume that each year has exactly $365$ days.
  }
  
\item
  What is the answer if you are trying to maximize the efficiency of your business?
  \footnote{
    Assume all workers are paid a fixed yearly salary, independent of the number of workers you hired. You can also assume the only costs of your business are worker salaries. Your task is to maximize the ratio of expected man-hours to the cost of the operation.
  }
\end{enumerate}

 \subsection*{Problem 2}

We start with a randomly shuffled deck of cards and draw from it until we pick the first ace. The goal of this problem is to find the average number of cards we will draw before the game stops.

\begin{enumerate}
\item
  Assume the symmetry principle applies in this discrete setting. Put differently, the four aces divide the deck (the remaining 48 cards) in 5 pieces with identical distributions. Compute the expected number of cards that come before the first ace. What is the answer to our original question?
  \footnote{
    Hint: The 48 non-ace cards are split in 5 parts with equal expected lengths.
  }

\item
  The position $X$ of the first ace can vary between $1$ (the first card is an ace) and $49$ (the last four cards are aces). Find an expression for the probability $\mathbb{P}(X = k)$.
  \footnote{
    Hint: If the first ace is at position $k$, then the first $k-1$ cards are non-aces (they come from a pool of $48$ cards). What is the probability of drawing an appropriate card in position $1$? What about positions $2$ and $3$? Keep going until positions $k-1$ and $k$.
  }

\item
  Compute the expectation $\mathbb{E}(X)$.
  \footnote{
    If you are having trouble doing on paper, feel free to provide a computational solution.
  }
  Does your answer match part (a) above?
\end{enumerate}



\subsection*{Problem 3}
In class, we have computed the average number $E$ of throws before you get a $6$ conditioned on the event that all throws before the first $6$ are even numbers (including the last throw).
In this question, you are asked to write a python program to approximate this conditional expectation $E$.
\begin{enumerate}
\item Write a function \texttt{Roll} which returns a random number between 1 to 6. 
\footnote{In python, you can use \texttt{np.random.randint(a, b)} to generate a random integer $n$ with $a\leq n < b$.}
\item Write a function \texttt{ConditionalExpectation} that takes an integer $N$ as input, and generate $N$ sequences of random dice rolls until the first 6.
Output the estimated conditional expectation $E$ by selecting appropriate subset of the $N$ sequences.
\item Plot your result for $N \in [1, 10000]$. Does this confirm with our computation in class?
\end{enumerate}

\subsection*{Problem 4}
We will call two events $A, B \in \mathcal{F}$ independent if
$$
\mathbb{P}(A\cap B) = \mathbb{P}(A) \cdot \mathbb{P}(B)
$$
Given two discrete random variables $X$, $Y$, we say $X, Y$ are independent if
$$
\mathbb{P}(X=i, Y=j) = \mathbb{P}(X=i) \cdot \mathbb{P}(Y=j)
\footnote{The left side is the probability of $X=i$ and $Y=j$}
$$
In this problem, we will show that if $X, Y$ are independent, then
$$
\mathbb{E}(XY) = \mathbb{E}(X)\cdot \mathbb{E}(Y).
$$
\begin{enumerate}
\item For simplicity, we will assume the random variables $X, Y$ are taking values in $\mathbb{N}$.
Let $\mathbb{E}(X) = \sum_{i=0}^\infty i\mathbb{P}(X=i)$ and $\mathbb{E}(Y)=\sum_{j=0}^\infty i\mathbb{P}(X=j)$.
Write $\mathbb{E}(X)\cdot \mathbb{E}(Y)$ as a double sum (with indices $i, j$).
\item Let $n=ij$, rewrite your double sum in terms of
$$
\sum_{n=0}^\infty ...,
$$
where each summand is some finite sum.
\item Use the fact that $X, Y$ are independent to rewrite each summand.
\item Use this to show $\mathbb{E}(XY) = \mathbb{E}(X)\cdot \mathbb{E}(Y)$.
\end{enumerate}

\subsection*{Problem 5}
In class, we have played the Casino game (Lecture 13, Problem 3). In this problem, we will use python to compute the expected value of the game with a regular deck.
Let $E(m,n)$ to denote the expected value of game with a deck of $m$ black cards and $n$ red cards.
\begin{enumerate}
\item What is $E(m, 0)$?
\item What is $E(0, n)$?
\item What is the value of the game $E(m,n)$ in terms of $E(m-1, n)$ and $E(m, n-1)$?
\footnote{Note that you can always choose not to play, in which case you get $0$. So the value of the game should be the maximum of $0$ and the value of the game if you choose to play.}
\item Write a recursive python program to compute $E(m,n)$, and print out the value of $E(2,2)$ and $E(3,3)$.
\item If you try to use your program to compute $E(26, 26)$, what happens? Why?
\item Instead of recursion, rewrite your code and use a 2-dimensional list to store data $E(i,j)$.
Print out the value of $E(26,26)$.
\end{enumerate} 

\subsection*{Problem 6}
In class, we have played the H/T game (Lecture 13, Problem 3). In this problem, I am going to reveal the trick.
Let $x$ be the probability that you will choose head, and $y$ be the probability that I will choose head.
\begin{enumerate}
\item What is the expected value $\mathbb{E} = \mathbb{E}(x,y)$ of your return?
\item Think of $\mathbb{E}(x,y)$ as a function of $y$, is there a way for me to choose $y$ so that $\mathbb{E}(x,y)$ is always negative no matter what $x$ is? Find the range for $y$.
\footnote{This problem can be an explanation why individuals may lose money in the stock market in the long run. Me, as a funding manager, can choose either to buy a stock (showing H) or sell a stock (showing T). If you, as an individual player, buy the stock or sell the stock at the same as me, you can gain profit from it. Otherwise, you will lose money. As you figured out, an individual player has negative expectation for this game no matter what strategy to choose.}
\end{enumerate}


\end{document}







