Category Archives: teaching

Shreve I.3: State prices and other option prices

Suppose the stock having current share price $S_0$ may either go up or down, to $S_1(H)=uS_0$ or $S_1(T)=dS_0$. Suppose we have a “stock option” $V_1$ that pays 1 dollar if $H$ occurs and zero otherwise; $V_1(H)=1$ and $V_1(T)=0$. By the binomial asset pricing model (Shreve volume I chapter 1) the price of this option should be
$$
V_0 = \frac{1}{1+r} (\tilde p V_1(H) + \tilde q V_1(T)) = \frac{\tilde p}{1+r}
$$
[This is the state price of the state H.] Here
$$
\tilde p = \frac{1+r-d}{u-d}
$$

Suppose we fix $d=1/2$ and let $u\rightarrow\infty$. So we are looking at a stock that will either drop by 50%, or increase enormously. Then $V_0\rightarrow 0$, i.e., the option becomes worthless.

This may seem surprising since the option depends on heads/tails but not explicitly on the stock price associated with H/T. But the way to look at it is this: if there exists a stock that will either drop by 50% or increase enormously, then it better be very unlikely that the stock should increase.

Say $u=1000$ and $r=1/2$. Then to replicate the option we would buy $\Delta_0 = \frac{V_1(H)-V_1(T)}{S_1(H)-S_1(T)} = \frac{1}{999.5 S_0}$ shares. Because of the $S_0$ in the denominator this is just $\epsilon:=\frac{1}{999.5}$ dollars worth of shares.

We would need an initial capital of
$$
X_0 = \frac{1+r-0.5}{(1000-0.5)(1+r)} = \frac{1}{(3/2)(999.5)} = 2\epsilon/3
$$
which is two-thirds of the amount we invested in the stock. With such initial capital we have set up a portfolio guaranteeing to get exactly the value of the option $V_1(\omega)$ back at time 1.

Case 1: Tails occurs. Then the value of the option is zero, and the value of our portfolio is calculated as follows: we had to borrow $\epsilon/3$ to buy stock, which means we now owe somebody $(1+r)\epsilon/3 = \epsilon/2$. But the stock we bought now has value $\epsilon/2$; so we have 0 overall.

Case 2: Heads occurs. The value of the option is 1; we owe somebody $\epsilon/2$ but we the stock we bought has value $1000\epsilon$; and indeed
$$
1000\epsilon – \epsilon/2 = 1
$$

Generally the portion of our capital that we buy stock for is
$$
\frac{\Delta_0 S_0}{X_0} = \frac{(\Delta V/\Delta S)S_0}{[\tilde p V_1(H)+\tilde q V_1(T)]/(1+r)}
= \frac{\Delta V/(u-d)}{[\tilde p V_1(H)+\tilde q V_1(T)]/(1+r)}
$$
$$
= \frac{\Delta V/(u-d)}{[\tilde p \Delta V + V_1(T)]/(1+r)}
$$

$$
= \frac{\Delta V/(u-d)}{[((1+r-d)/(u-d)) \Delta V + V_1(T)]/(1+r)}
$$

$$
= \frac{(1+r)\Delta V}{[((1+r-d)/(u-d)) \Delta V + V_1(T)](u-d)}
$$

$$
= \frac{(1+r)\Delta V}{(1+r-d)\Delta V + V_1(T)(u-d)}
$$

$$
= \frac{(1+r)\Delta V}{(1+r-d)V_1(H) – (1+r-u) V_1(T)}
$$

$$
= \frac{(1+r)\Delta V}{((1+r)-d)V_1(H) + (u-(1+r)) V_1(T)}
$$
where $\Delta V = V_1(H)-V_1(T)$. It is worth looking at when this fraction will be more than 1, i.e., replicating the option involves borrowing from the money market. This is when
$$
\frac{V_1(H)}{V_1(T)} > \frac{S_1(H)}{S_1(T)}
$$
i.e., the option payoff is, in some sense, more dependent on the heads/tails outcome than the stock price is.
For instance, if the option were constant ($V_1(H)=V_1(T)=c$) then we need not borrow to replicate it; we would buy 0 shares of stock and invest the whole initial capital $c/(1+r)$ in the money market.

Shreve II.4.5 Black-Scholes by mostly hand and a bit calculator

Let us consider the first example in Ch. 15 of Hull: Options, Futures, and other derivatives (6th edition).

$S_0=49$, $K=50$, $r=0.05$, $\sigma=0.2$, $T=0.3846 = 20/52$.

The price of the option per share should come out to $2.4$ according to Hull. We will check this against the Black-Scholes pricing formula for a call option $c$ on page 295.

We first calculate by hand that $\sigma^2/2=1/50$, $r\pm \sigma^2/2=(5\pm 2)/100$, and
$(r\pm\sigma^2/2)T = \frac{5\pm 2}{(13)(20)}$.

Moreover $S_0/K = 49/50$. A good approximation to the natural logarithm for inputs near 1 is $\ln x \approx x-1$.

Thus $\ln (S_0/K)\approx -\frac{1}{50}$.

Hence $(r+\sigma^2/2)T + \ln(S_0/K) \approx \frac{5+2}{(13)(20)} – \frac{1}{50} = \frac{9}{1300}$. This is the numerator of $d_1$. The denominator is $\sigma\sqrt{T} = \sqrt{5/13}/5 = 1/\sqrt{65} \approx 1/\sqrt{64} = 1/8 = .125$. So we have

$d_1 \approx \frac{9/1300}{1/8} = \frac{18}{325}$. It is tempting to say this is approximately $6\%$; a little calculator help shows it is approximately $5.5\%$. Then we also have $d_2 = d_1-\sigma\sqrt{T}\approx 5.5\% – 12.5\% = -7\%$.

Next we need to approximate the cumulative distribution function of the standard normal distribution, $N(d)$. Note that $N(0)=1/2$ and that $N'(0)=e^{-0^2/2}/\sqrt{2\pi} = 1/\sqrt{2\pi}$, so a linear approximation for $d\approx 0$ is $N(d)\approx \frac{1}{2} + \frac{d}{\sqrt{2\pi}}$.
A quite good approximation for $\sqrt{2\pi}$ is 2.5 (a little calculator help helps here).
This gives $N(d_1)\approx \frac{1}{2} + \frac{11}{500}$ and $N(d_2)\approx \frac{1}{2} – \frac{14}{500}$.

Next we approximate the exponential function near zero: $e^{-rT}\approx 1-rT = 1-\frac{1}{52}$ and $Ke^{-rT}\approx 50(1-\frac{1}{52})$.

Finally, $c = S_0 N(d_1) – K e^{-rT} N(d_2) = \frac{1}{2}(-\frac{1}{26}) + \frac{1}{500}(49\cdot 11 + 50(\frac{51}{52})(14))$. To get a good approximation we replace $50(51/52)$ by $49$, and get

$c \approx \frac{1225}{500} – \frac{1}{52} \approx \frac{2450}{1000} – \frac{1}{50} = 2.43$ which agrees to the precision given with our desired answer $2.4$.

Shreve II.6.5 Why is the yield curve increasing and concave down?

Link to stockcharts.com (Click on Animate!)

Suppose the probability of default during a year $t$, given that there was no default before year $t$, is $p(t)$. We are considering a loan with term $T$ and constant annual interest $r$, with a principal of 1 and no dividend payments. We stipulate that the expected money we get back at time $T$ should equal the principal. So
$$
1 = \mathbb E((1+r)^T \cdot 1_{\text{no default}}) = (1+r)^T \prod_{t=1}^T (1-p(t))
$$
This gives
$$
\ln(1+r) = \frac{1}{T} \sum_{t=1}^T (-\ln(1-p(t))
$$
We use the approximation $\ln (1+x)\approx x$ and get
$$
r \approx \frac{1}{T} \sum_{t=1}^T p(t).
$$
To use calculus let us instead write

$$
r(T) = \frac{1}{T} \int_{t=1}^T p(t) dt.
$$
Now $dr/dT>0$ if and only if $p(T)> \frac{1}{T}\int_{0}^T p(t)dt$, in other words $p(\cdot)$ is increasing. To use the approximation we must assume that $p(\cdot)$ nevertheless stays close to $0$ in any single year.

So the yield curve being increasing corresponds to an increasing risk of default per year. Now notice that $p(t)$ is bounded above, certainly by 1 and hopefully by something much less than 1.

But whenever $p(t)$ is an increasing and bounded function, then its running average $r(t)$ will be increasing and converging to $\lim_{t\to\infty}p(t)$. Hence $r(t)$ will increase by less and less as we approach $\lim_{t\to\infty}p(t)$.

If the debtor has not defaulted by the year 2200, then it may be because some more favorable conditions may have set in than the present ones. Thus it is reasonable to think that $p(t)$ is decreasing for very large $t$. But a typical scenario where a concave down yield curve is expected is something like U.S. Treasury bonds, which have been solvent for much longer than the term $T$ (say, a couple of centuries compared to at most 30 years). So if the U.S. is solvent in 2042, the conditions are probably no better than they are now. It is more likely that the present stable conditions will have loosened a bit, forcing $p(t)$ to increase.

Shreve II.6.9 Kolmogorov forward equation for geometric Brownian motion

For a nontrivial example of the use of Kolmogorov’s forward equation (the Fokker-Planck equation) where it can be contrasted with Kolmogorov’s backward equation, we look beyond Brownian motion, since the generator of the Brownian motion process is its own adjoint and applied to the transition density is the same in both the $x$ and $y$ variables. So we consider the next simplest example, the geometric Brownian motion process, which is given by
$$
dX_t = \mu X_t dt + \sigma X_t dW_t
$$
where we will assume $\sigma=1$ and $\mu=0$.

Generators and their adjoints

The generator for the GBM process in the $x$ variable is
$$
A = \frac{1}{2}x^2\frac{\partial^2}{\partial x^2}
$$
Following Øksendal’s book we need to find the adjoint $A^*$, satisfying $\langle Af,g\rangle = \langle f,A^* g\rangle$. The adjoint of $\partial/\partial x$ is $-\partial/\partial x$; this follows by integration by parts and the theory of distributions (where test functions are $C^\infty$ with compact support and hence the boundary terms vanish). Thus the adjoint of $A$, in the $y$ variable, is
$$
f\mapsto \frac{1}{2}\frac{\partial^2}{\partial y^2} (y^2 f)
$$
Using the product rule several times, we have
$$
A^*_y p = \frac{1}{2}\frac{\partial^2}{\partial y^2} (y^2 p) = p + 2y\frac{\partial p}{\partial y} + \frac{1}{2}y^2\frac{\partial^2 p}{\partial y^2}
$$

The pdf

By Shreve volume II page 119 the transition density for GBM is
$$
p(t,x,y)=\frac{1}{y\sqrt{2\pi T}}\exp\left(-\frac{(\log (y/x)-\nu T)^2}{2T}\right)
$$
where $\nu=\mu-\sigma^2/2=-1/2$, and where it is important to keep $x$ vs. $y$ straight.

Backward equation

If we wanted the backward equation we would replace $T$ by $T-t$ where $T>t$ and we are looking at the transition from $(t,x)$ to $(T,y)$ (instead of from $(0,x)$ to $(T,y)$). The resulting $p=p(t,x;T,y)$ gives the pdf of $X(T)$, as a function of $y$, given that $X(t)=x$. As $t\rightarrow T$ and with $x:=X(t)$ this pdf in $y$ will converge toward a Dirac delta function at the point $X(T)$. The backward equation is an expression of the fact that $p(t,X(t);T,y)$ is a martingale for fixed $T$ and $y$. It is the kind of martingale that keeps betting too much and hence will almost surely lose all its money. For a while the pdf at $y$ may be going up because $X$ approaches $y$, but this will only last for so long.

The backward equation can be verified and states that
$$
\frac{\partial p}{\partial t} = -A_x p
$$

Not-famous versions

On the other hand, since $p$ is a function of $t$ and $T$ only through $T-t$, it also follows that
$$
\frac{\partial p}{\partial T} = A_x p
$$
although this latter equation is not as famous as the Forward and Backward ones. It connects moving the future distribution forward in time, with space derivatives at the past time. Nor is it famous that
$$
\frac{\partial p}{\partial t} = – A^*_y p
$$

Verification of the Kolmogorov forward equation

In order to verify Kolmogorov’s forward equation we will have to take $\partial/\partial T$ of the transition density expression, which turns out to be less tedious if we use the functions $Q=\frac{1}{T}\log(y/x)$ and $R=Q+\frac{1}{2}$. If we ignore the trivial $\sqrt{2\pi}$ factor, after a while we obtain:
\begin{eqnarray}
p&=&\frac{1}{y\sqrt{T}}\exp(-R^2T/2) \\
\frac{\partial p}{\partial t} &=& p\cdot \left(\frac{-1}{2T} +RQ-R^2/2\right) \\
2y\frac{\partial p}{\partial y} &=& 2p(-1-R)\\
\frac{1}{2}y^2\frac{\partial^2 p}{\partial y^2} &=& \frac{p}{2}\left((-1-R)^2 +1+R-\frac{1}{T}\right)
\end{eqnarray}
By adding lines we get
$$
A^*_y p = \frac{\partial p}{\partial T}
$$
which is Kolmogorov’s forward equation.

Deterministic automaton complexity of strings

The deterministic automaton complexity of a finite binary string \(x=x_1\ldots x_k\) is defined to be the least number \(A(x)\) of states of a finite state automaton \(M\) such that \(x\) is the only string of length \(k\) in the language accepted by \(M\). It was introduced by Shallit and Wang (2001).

In a Discrete Mathematics class in Spring 2009, students Jason Axelson, Chris Ho and Aaron Kondo wrote a C program that calculated the complexity of all strings of length at most 7.

Results:
\[A()=1,\quad A(0)=2,\]
\[A(x_1\ldots x_k)\le k \quad\text{ for } k\ge 2,\]
\[A(x_1\ldots x_k)\le k-1 \quad\text{ for } k\ge 5.\]
\[A(x)\le 5 \quad\text{ for } k=7.\]

The string \(011100\) is the only string (starting with a 0) of length 6 or less with the property that its complexity is increased when read backwards:
\[A(011100)=4\ne 5=A(001110).\]

String 011100

A table of complexities is available:

Table of constants \(c\) with given property \(\forall x\in\{0,\dots,b-1\}^n\)

In the large-alphabet limit, Kayleigh graphs apply and we upper bound is \(\lfloor n/2\rfloor + 2\).
The example \(x=01\) shows the deterministic \(A(x)\) is not well defined unless
we also specify \(b\).
http://math.hawaii.edu/~bjoern/dfa-complexity-of-01-as-3-ary

Length \(n\) \(b=1\), \(A(x)\le cn + 1\) \(b=2\), \(A(x)\le cn\) \(b=3\), \(A(x)\le cn\) \(b=4\), \(A(x)\le cn\)
0 0 \(\infty\) \(\infty\) \(\infty\)
1 0 2 2 2
2 0 1 3/2? 1
3 0 1 1 1
4 0 1 1 1
5 0 0.8 1 1
6 0 0.83 in progress
7 0 0.714285
8 0 0.75
9 0 0.777 or 0.666

News (September 6, 2015): For binary strings of length at most 8, you may view witnessing automata using the format

http://math.hawaii.edu/~bjoern/dfa-complexity-of-011

Thus, the following table is now partially obsolete.

Complete table for binary strings of length \(\leq 7\) and partial table for length \(8\)

In the following table we only consider strings starting with 0, since strings starting with 1 have the same complexity as the string obtained by flipping each bit (e.g., \(K(001)=K(110)\)).

In the following table, \(\delta_i = 0102\) means that \((\delta(0,i),\delta(1,i),\delta(2,i),\delta(3,i)) = (0,1,0,2)\)
in a witnessing DFA with 4 states, found by the MATH 301 students’ program.
Curiously, note that below there are no instances of permutation automata (where \(\delta_i\) is a bijection) except for the empty string.

\(A^-(x)\) denotes incomplete DFA complexity, i.e., there is no requirement that the transition functions be total.
We have \(A_N(x)\le A^-(x)\le A(x).\)

String \(x\) Complexity \(A(x)\) \(\delta_0\) \(\delta_1\) \(A^-(x)\)
1 0 0 1
0 2 00 10 1
00 2 01 11 1
01 2 00 10 2
000 2 01 11 1
001 3 110 200 2
010 3 100 210 2
011 3 111 220 2
0000 2 01 11 1
0001 3 022 122 2
0010 4 1120 2321 3
0011 3 202 100 3
0100 4 1130 2211 3
0101 3 122 202 2
0110 4 1110 2231 3
0111 3 122 212 (avoids 0) 2
00000 2 01 11
00001 3 022 122
00010 4 1120 2322
00011 4 1122 2320
00100 4 1102 2331
00101 4 1132 2301
00110 4 1101 2332
00111 4 1131 2302
01000 4 1302 2131
01001 4 1223 2320
01010 3 122 202
01011 4 1221 2320
01100 4 1001 2303
01101 4 1322 2120
01110 4 1220 2321
01111 3 122 212 (avoids 0)
000000 2 01 11
000001 3 022 122
000010 4 0313 2333
000011 4 0333 2313
000100 5 11240 23221
000101 5 11241 23220
000110 5 11220 23241
000111 4 2033 1002
001000 5 13240 22211
001001 4 1321 2220
001010 4 2313 1233 (avoids 0)
001011 4 2032 1003
001100 4 1320 2223
001101 5 13241 22230
001110 5 13220 22243 4 (\(A_N=3\))
001111 4 2313 3133
010000 4 2133 3313
010001 5 12243 23220
010010 4 1220 2321
010011 5 12231 23240
010100 4 2313 1303
010101 3 122 202
010110 5 12210 23241
010111 5 12211 23240
011000 5 13240 21221
011001 4 2002 1033
011010 5 13220 21241
011011 4 1221 2320
011100 4 1220 2323
011101 5 12241 23210
011110 4 2313 1323 (avoids 0)
011111 3 122 212
0000000 2
0000001 3
0000010 4
0000011 4
0000100 5
0000101 5
0000110 5
0000111 5
0001000 5
0001001 5
0001010 5
0001011 5
0001100 5
0001101 5
0001110 5
0001111 5
0010000 5
0010001 5
0010010 4
0010011 5
0010100 4
0010101 4
0010110 5
0010111 5
0011000 5
0011001 5
0011010 5
0011011 5
0011100 5
0011101 5
0011110 5
0011111 4
0100000 4
0100001 5
0100010 5
0100011 5
0100100 4
0100101 5
0100110 5
0100111 5
0101000 5
0101001 5
0101010 3
0101011 4
0101100 5
0101101 5
0101110 5
0101111 5
0110000 5
0110001 5
0110010 5
0110011 5
0110100 5
0110101 5
0110110 4
0110111 5
0111000 5
0111001 5
0111010 5
0111011 5
0111100 5
0111101 5
0111110 4
0111111 3
String Complexity Witness
00000000 2 \(0^*\)
00000001 3 \(0^* 1\)
00000010 4 \(0^* 10\)
00000011 4 \(0^* 11\)
00000100 5 \(0^* 100\)
00000101 5 \(0^* 101\)
00000110 5 \(0^* 110\)
00000111 5 \(0^* 111\)
00001000 6 \(0^* 1000\)
00001001 6 \(0^* 1001\)
00001010 6 \(0^* 1010\)
00001011 6 \(0^* 1011\)
00001100 6 \(0^* 1100\)
00001101 6 \(0^* 1101\)
00001110 6 \(0^* 1110\)
00001111 5 d0: (1, 2, 3, 3, 0), d1: (4, 0, 1, 2, 0) better than \(0^* 1111\)
00010000 6 \(0001 0^*\)
00010001 \(\le\)5 \((0001)^*\)
00010010 \(\le\)6 \(0(001)^* 0\)
00010011 \(\le\)6 \(0(001)^* 1\)
00010100 \(\le\)6 \( 00 (01010…)00\)
00010101 \(\le\)5 \( 00 (01)*\)
00010110 5 witness (K-H)
00010111 5 no trash
00011000 \(\le\)6 \( 00011,00011,…\)
00011001 \(\le\)6 \( 0 (0011,0011,…)\)
00011010 6 witness (K-H)
00011011 \(\le\)6 \( 00(011)^*\)
00011100 5 witness (K-H)
00011101 6 witness (K-H)
00011110 \(\le 6\) (Christina M) (Jiehua H)
00011111 \(\le 5\) (Jiehua H)
00100000 \(\le 5\) (Christina M) (Jiehua H)
00100001 \(\le 6\) (Christina M) (Jue W)
00100010 \(\le 6\) (Jue W)
00100011 \(\le 6\) (Jue W)
00100100 \(\le 6\) (Jue W)
00100101 \(\le 5\) (Jue W)
00100110 \(\le 6\) (Jue W)
00100111 \(\le 6\) (Jue W)
00101000 \(\le 6\): \(a \rightarrow_0 b \rightarrow_0 c \rightarrow_1 b\) and \(c \rightarrow_0 d \rightarrow_0 e\) plus one thrash (Frank S)
00101001 \(\le 6\) (Jue W)
00101010 \(4\) (Christina M)
00101011 5\(\le 7\) d0: (1, 2, 1, 0, 4), d1: (3, 0, 4, 0, 2)
00101100 \(\le 7\)
00101101 \(\le 7\)
00101110 \(\le 7\)
00101111 \(\le 6\) (Christina M)
00110000 \(\le 6\) (Christina M) (Jue W)
00110001 \(\le 6\) (Jue W)
00110010 \(\le 7\)
00110011 \(\le 7\)
00110100 \(\le 7\)
00110101 \(\le 7\)
00110110 \(\le 7\)
00110111 \(\le 7\)
00111000 \(\le 6\) (Jue W)
00111001 \(\le 7\)
00111010 \(\le 6\) (Jue W)
00111011 \(\le 7\)
00111100 \(\le 6\) (Christina M) (Jue W)
00111101 \(\le 6\) (Christina M) (Jue W)
00111110 \(\le 5\) (Christina M) (Jue W)
00111111 \(4\) (Christina M) (Jue W)
01000000 \(4\) (Christina M) (Jue W)
01000001 \(\le 5\) (Christina M) (Jue W)
01000010 \(\le 6\) (Christina M) (Jue W)
01000011 \(\le 6\) (Christina M) (Jue W)
01000100 \(\le 7\)
01000101 \(\le 7\)
01000110 \(\le 7\)
01000111 \(\le 7\)
01001000 \(\le 7\)
01001001 \(\le 7\)
01001010 \(\le 7\)
01001011 \(\le 7\)
01001100 \(\le 7\)
01001101 \(\le 7\)
01001110 \(\le 7\)
01001111 \(\le 6\) (Christina M)
01010000 \(\le 6\) (Christina M)
01010001 \(\le 6\) (Christina M)
01010010 \(\le 6\) (Christina M)
01010011 \(\le 6\) (Christina M)
01010100 4 \(\le 4\) (Christina M)
01010101 3 (\(\le 4\) Christina M)
01010110 \(\le 6\) (Christina M)
01010111 \(\le 6\) (Christina M)
01011000 \(\le 7\)
01011001 \(\le 7\)
01011010 \(\le 7\)
01011011 \(\le 7\)
01011100 \(\le 7\)
01011101 \(\le 7\)
01011110 \(\le 6\) (Christina M)
01011111 \(5\) (Christina M)
01100000 \(5\) (Christina M)
01100001 \(\le 6\) (Christina M)
01100010 \(\le 7\)
01100011 \(\le 7\)
01100100 \(\le 7\)
01100101 \(\le 7\)
01100110 \(\le 7\)
01100111 \(\le 7\)
01101000 \(\le 7\)
01101001 \(\le 7\)
01101010 \(\le 7\)
01101011 \(\le 7\)
01101100 \(\le 7\)
01101101 \(\le 7\)
01101110 \(\le 7\)
01101111 \(\le 6\) 4 consecutive
01110000 \(\le 6\) (Christina M)
01110001 \(\le 7\)
01110010 \(\le 7\)
01110011 \(\le 7\)
01110100 \(\le 7\)
01110101 \(\le 7\)
01110110 \(\le 7\)
01110111 \(5\) (Jue W)
01111000 \(\le 6\) (Christina M)
01111001 \(\le 6\) 4 consecutive
01111010 \(\le 6\) (Christina M)
01111011 \(\le 6\) (Chelsea T) (Christina M)
01111100 \(5\) (Chelsea T) (Christina M)
01111101 \(5\) (Chelsea T) (Christina M)
01111110 \(4\) (Chelsea T) (Christina M)
01111111 \(3\) (Chelsea T) (Christina M)

Increasing approximation to $e$

As is well known, $f(x)=(1+\frac{1}{x})^x$ converges to $e$ as $x\rightarrow\infty$. Sometimes it is good to know that this convergence is monotone which for future reference I will discuss here. We first note that $f(x)=\exp(g(x))$ where
$$\label{1}\tag{1}
g(x)=x\ln\left(1+\frac{1}{x}\right)
$$ and $\exp(x)=e^x$. So it suffices to show $g$ is monotonically increasing to the limit $1$. To that end, rewrite
$$
g(x)=\frac{\ln(1+\frac1x)}{1/x}
$$
and then apply L’Hopital’s rule, and we have that the limit is 1.
How do we know the convergence is monotone? Well, using (\ref{1}) it is readily calculated that $g”(x)<0$ for all $x>0$.

Claim: A function that is concave down and converges to a finite limit as $x\rightarrow\infty$ must necessarily be increasing.

Proof: If we ever had $g'(a)<0$ then $g'(x)\le g'(a)<0$ for all $x\ge a$. By the Mean Value Theorem, on every interval $[n,n+1]$ with $n\ge a$ the function $g$ decreases by at least $|g'(a)|$.

(Namely, if $g(n+1)-g(n)> g'(a)$ then ${\frac{g(n+1)-g(n)}{(n+1)-n}} > g'(a)
$ and so there would be some $x\in [n,n+1]$ with $g'(x)>g'(a)$.)

Consequently $\lim_{x\rightarrow\infty}g(x)=-\infty$.
End of proof of claim.

Transition to Advanced Math: Take-home midterm

Do the following problems from Humphreys and Prest:
1.4#2
2.2#5
2.4#6

For the next and last two problems refer to the page Automaton complexity.

Prove that
4. $A(x_1,\ldots,x_k)\le k+1$ for all $k$.
5. $A(x_1,\ldots,x_k)\le k$ for $k\ge 3$.

6. Extra credit (up to 4% of the course): improve some of the $\le$ estimates on the table of complexities.

(I proved in class that $A(x_1,\ldots,x_k)\le k+2$ for all $k$.)

It is essential to write legibly and show your work. If your work is absent or illegible, and
at the same time your answer is not perfectly correct, then no partial credit can be awarded.
Completely correct answers which are given without justification may receive little or no credit.

During this exam, you are permitted to use calculators, notes, or books.

You are not allowed to collaborate with others, except on the extra credit problem.

Statistical Inference: Take-Home Midterm

Take-Home Midterm

Do 4 of the 5 problems here:
Statistical inference take-home midterm
and do the following
Question 6:

Here we consider Bounce rate (see another midterm question) for visitors to www.math.hawaii.edu during January 1 – March 22, 2012, for two types of web traffic: Direct Traffic and Search Traffic. Conduct a t-test for equality of means as in Section 9.2, Case Study 9.2.1. The data is here (CSV format). You may use Excel, Google Docs, or whichever software you want; show all work by also turning in files used.

Solution to Question 6:

If we let $X$ and $Y$ denote direct traffic and search traffic then $\overline x = 0.652859756097561$ and $\overline y = 0.70355243902439$. Moreover $\sum x_i^2 = 35.44131437$ and $\sum y_i^2 = 40.87052961$. The sample variances (determined by the function “var” in Google Docs) are $s_x^2 = 0.006059182187594$ and $s_y^2 = 0.003477466475459$. Since the sample sizes are equal ($n=m$), the pooled sample variance is just the average of these two, $s_p^2 = 0.004768324331527$. The factor $\sqrt{1/n+1/m}=\sqrt{2/n}$ with $n=82$ is 0.156173761888606, and the value of the statistic $t$ is $$\frac{\overline x-\overline y}{s_p \sqrt{2/n}}$$ which comes out to -4.7006109896853.

This is far enough from zero that we reject the null hypothesis; i.e., search traffic has a significantly higher bounce rate. This may be because search traffic is often traffic on a very specific page (such as a Fortran page) which is the only page the visitor is interested in.