## Friday, June 17, 2016

### Coursera Approximation Algorithms Part I - Peer Assignment 4 - Question 1

Problem:

Solution:

(Part 1)

With probability $\frac{1}{2}$, $n_{t + 1} = \frac{9}{8}n_t$, so $n_t - n_{t+1} = n_t - \frac{9}{8}n_t = -\frac{1}{8}n_t$
With probability $\frac{1}{4}$, $n_{t + 1} = n_t$, so $n_t - n_{t+1} = n_t - n_t = 0$
With probability $\frac{1}{4}$, $n_{t + 1} = \frac{1}{2}n_t$, so $n_t - n_{t+1} = n_t - \frac{1}{2}n_t = \frac{1}{2}n_t$

Therefore $E[n_t - n_{t-1}|n_t] = \frac{1}{2}(-\frac{1}{8}n_t) + \frac{1}{2}(0) + \frac{1}{4}(\frac{1}{2}n_t) = \frac{1}{16}n_t$

(Part 2)

Obviously, we can set $f(n_t) = \frac{1}{16}n_t$

(Part 3)

We simply apply the given Wald's equation:

$E[T] \le \frac{1}{2f(\frac{1}{2})}+ E\left[\int\limits_{n_{T-1}}^{n_0}{\frac{1}{f(z)}dz}\right]$

$E[T] \le \frac{1}{2\frac{1}{16}\frac{1}{2}}+ E\left[\int\limits_{n_{T-1}}^{n_0}{\frac{1}{\frac{1}{16}z}dz}\right]$

$E[T] \le 16 + E\left[16 \int\limits_{n_{T-1}}^{n_0}{\frac{1}{z}dz}\right]$

$E[T] \le 16 + 16 E\left[\int\limits_{n_{T-1}}^{n_0}{\frac{1}{z}dz}\right]$

$E[T] \le 16 + 16 E[\ln(n_0) - \ln(n_{T-1})]$

Now $n_0 = x$, we know $n_{T-1} > 1$ (since he hasn't leave yet), so the final bound is

$E[T] \le 16 + 16 \ln x$

To verify the bound, I wrote this simple C# program to empirically estimate the expectation using Monte Carlos simulation and compare it to the bound, the bound seems to consistently bound the expectation, so we should be good.

using System;

public class Test
{
public static void Main()
{
Random r = new Random();
double cs = 0;
double X = 10;

for (int i = 0; i <= 1000; i++)
{
double x = X;
int c = 0;
while (x > 1)
{
double p = r.NextDouble();
if (p < 0.5)
{
x *= 9.0 / 8;
}
else if (p < 0.75)
{
x *= 1.0 / 2;
}
c++;
}
cs += c;
}

double bound = 16 + 16 * Math.Log(X);
double expectation = cs/1000.0;
Console.WriteLine(bound / expectation);
}
}