\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 8 (Due April 9rd, 2019 at 1:00PM)}
}
\date{}

\maketitle

\vspace{-1cm}

\subsection*{Problem 1}

If you are doing your final project:
Submit the introduction of your final project and the plan for the main body to 'Intro of Final Project' on Canvas by 1:00 pm April 9rd, 2019.

If you are not doing your final project:
I am lending you 1 free problem pass, but you will pay me back with continuously compounded interests and do 5 additional ones in homework 10.

What is the APY for this loan?

\subsection*{Problem 2}

The unit segment is cut at one randomly chosen point (uniformly distributed).
\begin{enumerate}
\item
  What is the variance of the length of the left piece?
\item
  What is the variance of the length of the shorter piece?
\item
  What is the average ratio of shorter to longer piece?
\end{enumerate}


\subsection*{Problem 3}

The unit segment is cut at two independently chosen random points (uniformly distributed).
\begin{enumerate}
\item
  What is the probability the three pieces fit into a triangle?

\item
  What is the variance of the length of left piece?

\item
  (Extra credit) What is the probability the three pieces fit into an acute triangle?

\item
  (Extra credit) What is the expected ratio of shortest to longest piece lengths?
\end{enumerate}

\subsection*{Problem 4}
In class, we discussed briefly about the following game of passing pomelo when passing to the left and right with equal probability \footnote{If you are doing this homework early, we will discuss this on Thusday}.
In this assignment, we will generalize the problem where the probability is not equal.

Suppose there are $n+1$ people numbered by $0, 1, ... , n$ standing in a circle. 
Person $0$ has a pomelo to start passing around.
Every time, the person $i$ who is holding the pomelo has probability $p$ to pass to person $i+1$ and probability $q=1-p$ to pass to person $i-1$
\footnote{These numbers are arranged in a circle, so person $0$ has probability $p$ to pass to person $1$ and probability $q$ to pass to person $n$. Similar holds for person $n$.}, with $p>1/2$.
The game ends when all but one have touched the pomelo, in which case the final person who never touches it will win the pomelo.
Let $P_i$ denote the probability that the person $i$ will win the pomelo.
We will compute $P_i$ as follows:

In order for person $i$ to win the pomelo, both person $i+1$ and person $i-1$ will touch the pomelo.
To compute $P_i$, we can condition on whether person $i-1$ will touch the pomelo before person $i+1$ or the other way around.
\begin{enumerate}
\item
What is the probability that person $i-1$ will touch the pomelo before person $i+1$?
\item
Given that person $i-1$ touches the pomelo before person $i+1$, what is the probability person $i$ eventually wins the pomelo?
\item
Given that person $i+1$ touches the pomelo before person $i11$, what is the probability person $i$ eventually wins the pomelo?
\item
Use the above three and compute the probability $P_i$.
\item
(Extra credit) Do you have any other ways of computing $P_i$?
\end{enumerate}



\subsection*{Problem 5}

Consider a sequence of independent identically distributed random variables $X_1, X_2, \dots$ such that for each $i$ either $X_i = 1$ or $X_i = -1$, both with probability $1/2$. The collection of partial sums $S_n = \sum_{i = 1}^n X_i$ for $n \geq 0$ constitute a \href{http://en.wikipedia.org/wiki/Random_walk}{\emph{random walk}}. Such processes have found many applications from physics and biology to financial mathematics. We will use this problem to explore computationally several questions concerning the behavior of random walks.

\begin{enumerate}
\item
  Write a function \texttt{random\_walk(k, n)} which returns a $k \x n$ matrix each of whose rows is a random walk. Don't use any loops.
  \footnote{
    Hint: You can first generate a $k \x n$ matrix with entries $\pm 1$. This can be done either by conditioning a uniform variable (see previous homework), or by manipulating the output from \href{http://docs.scipy.org/doc/numpy/reference/generated/numpy.random.binomial.html}{\texttt{np.random.binomial}}. Then compute row-wise cumulative sums using \href{http://docs.scipy.org/doc/numpy/reference/generated/numpy.cumsum.html}{\texttt{np.cumsum}}.
  }

\item
  Plot the progression progression of $k = 10$ random walks of length $n = 10^5$. Overimpose the plots of $\pm 2\sqrt{x}$. You can use a loop of length $k$ to go over different random walks.

\item
  Use $k = 100$ and $n = 10^5$ to compute the variance at each step of a random walk. Don't use any loops.

  Produce a log-log plot of your results. Conjecture a value $\alpha$ such that $Var(S_n) = O(n^\alpha)$.
  \footnote{
    Hint: You can use \href{https://docs.scipy.org/doc/numpy-1.6.0/reference/generated/numpy.var.html}{\texttt{np.var}} to compute the column-wise variance for the output of \texttt{random\_walk(k, n)}.

    If $y = C \cdot x^\alpha$, then $\log y = \alpha \cdot \log x + \log C$. It follows that the log-log plot of $x$ and $y$ is a line of slope $\alpha$. For the latter part, you can compare your plot to a line and compute its slope to guess $\alpha$. The value of $\alpha$ is easy enough to guess directly, so you don't need to fit a regression line.
  }

\item
  Given a random walk $S_0, S_1, S_2, \dots$, we can count how many times it returns to the origin. The variable
  \[
  R_n = |\{ i \;|\; X_i = 0 \textrm{ and } 0 \leq i \leq n \}|
  \]
  represents how many times the random walk is at the origin up to its $n$-th step. Since the random walk starts at the origin $S_0 = 0$, we take the convention that $R_0 = 1$.
  
  Write a function \texttt{num\_returns(X)} which accepts a $k \x n$ matrix consisting of random walks. The output should be a $k \x n$ matrix whose value at position $(i, j)$ is the number of returns the $i$-th random walk has makes to the origin up to and including step $j$. Since each random walk starts at $0$, all entries of your result should be positive. Don't use any loops.
  \footnote{
    Hint: You can compare the input $X$ to $0$ using \href{http://docs.scipy.org/doc/numpy/reference/generated/numpy.equal.html}{\texttt{np.equal}}. Convert the Boolean output to integers (0 and 1), compute row-wise cumulative sums, and add $1$.
  }

  Take column-wise means of the output of \texttt{num\_returns} to compute approximations for $\mathbb{E}(R_n)$. Produce a log-log plot of your results and use it to conjecture a value $\beta$ such that $\mathbb{E}(R_n) = O(n^\beta)$.

\item
  (Extra credit) Prove the conjectures you made above.

\item
  (Extra credit) Investigate the sequence of variables
  \[
  M_n = \max\{ |S_i| \;|\; 0 \leq i \leq n \}.
  \]
  The value of $M_n$ is the furthest distance the underlying random walk has traveled from the origin up to step $n$. Make a conjecture of the form $\mathbb{E}(M_n) = O(n^\gamma)$ and prove your claim.
\end{enumerate}

\begin{center}
  \includegraphics[width=0.45\textwidth]{plot_walks.png}
  \includegraphics[width=0.45\textwidth]{plot_var.png}
  
  \includegraphics[width=0.45\textwidth]{plot_rets.png}
  \includegraphics[width=0.45\textwidth]{plot_max.png}
\end{center}


\end{document}







