Solution: 2018 Fall Final - 22

Author: Michiel Smid

Question

Zoltan's Noodle House is a popular restaurant in downtown Ottawa. When you order the surprise dish, you get Mi Quang with probability 1/4, Bun Cha Ca with probability 1/3, and Banh Xeo with probability 5/12.
Tri enjoys going to this restaurant, because the food reminds him of his mommy's food back home in Da Nang.
Tri runs the following recursive algorithm:

$\mathbf{Algorithm}\ \TriIsHungry\mathrm{:}$

$//$	$\text{the results of all}$ $\text{orders are independent}$

$\text{Tri orders the surprise dish;}$
$\mathbf{if}\ \mathrm{Tri}\ \mathrm{gets}\ \mathit{Mi}\ \mathit{Quang}$
$\mathbf{then}\ \text{Tri eats the dish;}$
$\qquad\ \ \TriIsHungry$
$\mathbf{else}\ \mathbf{if}\ \mathrm{Tri}\ \mathrm{gets}\ \mathit{Bun}\ \mathit{Cha}\ \mathit{Ca}$
$\qquad\, \mathbf{then}\ \text{Tri eats the dish;}$
$\qquad \qquad\ \ \, \TriIsHungry$
$\qquad\, \mathbf{else}\ \text{Tri eats the dish;}$

$\hspace{4.05em}$

$\text{Tri pays the bill}$ $\text{and goes home}$

$\qquad\, \mathbf{endif}$
$\mathbf{endif}$

Define the random variable $X$ to be the number of dishes that Tri eats when running algorithm $\TriIsHungry$.
What is the expected value $\mathbb{E}(X)$ of the random variable $X$?

(a)

12/5

(b)

5/12

(c)

5/7

(d)

7/5

Solution

We’re looking for the number of times Tri eats when running the algorithm, which is akin to saying \enquote{how many times do we call TriIsHungry?}

The probability that we call TriIsHungry again is $ \frac{5}{12} $ since we only stop when we get Banh Xeo

Geometric Distrbution tells us that the expected number of times until something happens is $ \frac{1}{Pr} $

$ \mathbb{E}(X) = \frac{1}{ \frac{5}{12}} $

$ \mathbb{E}(X) = \frac{12}{5} $