## Saturday, June 18, 2016

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

Problem:

Solution:

(Part 1)

This probability is the same as drawing one particular coin from 10 coins, that would be $\frac{1}{10}$.

(Part 2)

Let $X_i$ be the indicator variable that the i friend get back his own coin. In the above, we already show that $P[X_i = 1] = \frac{1}{10}$.

The expected number of people getting their own coin is simply $E[\sum\limits_{i = 1}^{10} X_i] = \sum\limits_{i = 1}^{10} E[X_i] = \sum\limits_{i = 1}^{10} P[X_i = 1] = \sum\limits_{i = 1}^{10} \frac{1}{10} = 1$.

(Part 3)

Let $Y_i$ be the indicator variable that the i friend get back his own coin in the buy coffee case. Let's us imagine we simply replace the spent coin with a phantom coin and do the experiment as above again. Now everyone have the same chance of getting the phantom coin, and this time around $P[Y_i = 1] = \frac{1}{10} \times \frac {9}{10}$ because you need to get your own coin and the coin is not phantom.

The rest just follows exactly like above and the expected number of people getting their own coin is $\frac{9}{10}$

Again, to verify the expectation, I wrote this simple Monte Carlos simulation to prove that the bound is indeed the case.

using System;
using System.Linq;

class Program
{
static void Main(string[] args)
{
Random random = new Random();
int NUM_EXPERIMENT = 1000000;
int d = 0;
for (int e = 0; e < NUM_EXPERIMENT; e++)
{
int c = 0;
int unlucky = random.Next(10);
int[] a = Enumerable.Range(0, 10).ToArray();
for (int i = 0; i < 9; i++)
{
int j = random.Next(10 - i) + i;
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
for (int i = 0; i < 10; i++)
{
if (a[i] == i && i != unlucky)
{
c++;
}
}
d += c;
}
Console.WriteLine((d + 0.0) / NUM_EXPERIMENT);
}
}