I came up with a probability question today with (at least what I think is) a nifty solution.
Here is a statement of the problem: 'You are partaking in an experiment. The rules of the experiment are as follows: You flip a fair two sided coin, if you receive heads on a flip, you must roll a fair 6-sided dice, if you roll an even number, you get $2$ points, if you roll an odd number, you get $1$ point. After you receive heads and roll either an even or odd number, you are allowed to flip your coin again. However, if you receive a tails during any of your flips, you receive $0$ additional points and must stop the experiment immediately. How many points should you expect to receive in total? (What is the expected value of this experiment)'
So, as an example, I could receive tails on my first flip, leaving me with a final score of $0$. I could also flip heads, get an even number, and then flip tails, leaving me with $2$ points at the end of my experiment.
To get a better feel for the experiment, here is a plot of its probability distribution (how this plot was obtained will be explained later in this post):
The event with the highest probability is 'receiving a score of $0$', as there is a $0.5$ likelihood of receiving a tails on first flip. The event 'receiving a $2$' is slightly more probable than the event 'receiving a $1$', precisely by $\frac{1}{32}$.
Now, lets try and actually solve the problem. What is the expected value of this experiment?
We'll start by recalling the definition of 'expected value' :
$\textbf{Definition 1 (Expected Value)}$ : The expected value of an experiment with random variable $X$ is $\displaystyle E(X) = \sum_{\forall x} P(X=x)(x)$
In our case, our random variable is $X = no. \ of \ points $, and therefore $X$ can take on any of the values in $\{0,1,2,...\}$, or in other words, $X = \mathbb {N}$
We are currently faced with the task of trying to compute $E(X)$. Initially, I fell into a trap when faced with this problem, as I attempted to find a closed form expression for $P(X=x)$ in order to compute $E(X)$, a method that, while viable, leads to further messiness involving radicals and exponents.
While this was not the method I ultimately used in order to solve the problem, I'll go through it anyway for the sake of completeness.
I first noticed the following recurrence relation: $P(X=k) = \frac{1}{4} (P(X=k-1) + P(X = k-2) )$,
for all $k\geq 2, k\in \mathbb {N}$, with initial conditions: $P(X = 0) = \frac{1}{2} \ and \ P(X=1) = \frac{1}{8}$
I'll briefly justify this recurrence relation: Note that the only possible method to increase points at any point during the experiment is to flip heads, as flipping tails leaves the number of points at any particular point in time unchanged.
Therefore, if we have received $x+2$ points at the end of our experiment, we may have either flipped heads and rolled even after $x$ points or flipped heads and rolled odd after $x+1$ points.
Lets analyze this further: We'll denote sample points as sequences of $Heads = H$, $Tails = T$, $Even\ roll = E$, $Odd \ roll = O$
As an example, a sample point in the event $X = 4$ is $HOHOHET$
The $T$ at the end of any of our sequences is just to terminate the sequence, as it doesn't actually add or subtract any points.
Consider the event $X = x+2$. How many sample points are in the sample space of this event? Well, each sample point in $X = x+2$ is simply a sample point in $X=x+1$ with an additional $HO$, or is a sample point in $X = x$ with an additional $HE$.
To illustrate this, lets take $X=4$ as an example. I'll list out all of the sample points in $X=4$.
Here they are: $\{HEHET, HOHOHET, HOHEHOT, HEHOHOT, HOHOHOHOT\}$
Now, here are all the sample points for $X=3$
$\{HOHET, HEHOT, HOHOHOT\}$
and all the sample points for $X=2$
$\{HET, HOHOT\}$
First of all, we see that the number of sample points in the event $X=4$ is equal to the sum of the number of sample points in events $X=3$ and $X=2$.
Secondly, we see that as previously mentioned, each sample point in $X=4$ is either a sample point in $X=3$ with an additional $HO$ or a sample point in $X=2$ with an additional $HE$.
For example, take the sample point $HEHOHOT$. This is $HEHOT$ (a sample point of $X=3$) with an additional $HO$.
Now, what does this mean in terms of probability?
Well, an additional $HO$ translates to multiplication by $(\frac{1}{2})(\frac{1}{2}) = \frac{1}{4}$, and an additional $HE$ also translates to multiplication by $(\frac{1}{2})(\frac{1}{2}) = \frac{1}{4}$.
So, $P(X = k) = (probability \ of \ HO )(P(X = k-1)) + (probability \ of \ HE )(P(X = k-2))$
Since $(probability \ of \ HO ) = (probability \ of \ HE ) = \frac{1}{4}$, we have
$P(X=k) = \frac{1}{4} (P(X=k-1) + P(X = k-2) )$
Great, so how can we use this recurrence relation to determine a closed form expression for $P(X=k)$ ?
The answer lies in the theorem below:
$\textbf{Theorem 1 (Solution of second order linear homogeneous recurrence relation with distinct roots)}$
A recurrence relation $u_n = au_{n-1} + bu_{n-2}$ for non-zero $a,b$ has closed form solution:
$u_n = c(\lambda_1)^n + d(\lambda_2)^n$.
Where $\lambda_1$ and $\lambda_2$ are distinct roots of the characteristic equation:
$\lambda^2 - a\lambda - b = 0$.
and $c,d$ are constants that are determined by two initial conditions, namely $u_1 = known \ value$ and $u_2 = known \ value$
$\square$
One can show that Theorem 1 is indeed true by substituting this closed form solution back into the original recurrence relation, although this method of 'proving' Theorem 1 is quite unsatisfying and leaves much to be desired as it does not shed any light on what motivated Theorem 1 in the first place.
Unfortunately, I do not know much about what motivated Theorem 1, perhaps after some research I'll be able to write a post about this in future.
Anyway, with the help of Theorem 1, I was able to work out a closed form expression for $P(X = k)$.
Here it is:
$\displaystyle P(X = k) = (\frac{\sqrt{17} + 1}{4\sqrt{17}})(\frac{1 + \sqrt{17}}{8})^k + (\frac{\sqrt{17} - 1}{4\sqrt{17}})(\frac{1 - \sqrt{17}}{8})^k$
(This is also how I was able to obtain a plot of $P(X=k)$ against $k$)
Using this, it is possible to just plug the expression we obtained for $P(X=k)$ into the $E(X)$ summation and do a bit of algebra relating to series of the form $\displaystyle \sum_{\forall k} kr^k$ to work out the answer. However, this is quite messy and so I tried to avoid it with an alternative route that gets rid of the need for a closed form expression of $P(X=k)$ altogether.
Here is the alternative method:
$\displaystyle E(X) = \sum \limits_{k=0}^{\infty} (k)P(X=k) = (0)P(X=0) + (1)P(X=1) + \sum \limits_{k=2}^{\infty} (k)P(X=k)$
Now for $k\geq 2$ we know that $P(X=k) = \frac{1}{4} (P(X=k-1) + P(X = k-2) )$
This means that $\displaystyle \sum \limits_{k=2}^{\infty} (k)P(X=k) = \frac{1}{4}(\sum \limits_{k=2}^{\infty} (k)P(X=k-1) + \sum \limits_{k=2}^{\infty} (k)P(X=k-2))$
Lets concentrate on each individual term in this expression:
$\displaystyle \sum \limits_{k=2}^{\infty} (k)P(X=k-1) = \sum \limits_{k=2}^{\infty} (k-1)P(X=k-1) + \sum \limits_{k=2}^{\infty} P(X=k-1)$
We know that $\displaystyle \sum \limits_{k=2}^{\infty} P(X=k-1) = \sum \limits_{k=1}^{\infty} P(X=k-1) - P(X=0) = \sum \limits_{k=1}^{\infty} P(X=k-1) - \frac{1}{2} = 1 - \frac{1}{2} = \frac{1}{2}$.
Furthermore, $\displaystyle \sum \limits_{k=2}^{\infty} (k)P(X=k-2)) = \sum \limits_{k=2}^{\infty} (k-2)P(X=k-2)) + \sum \limits_{k=2}^{\infty} (2)P(X=k-2))$
We know that $\displaystyle \sum \limits_{k=2}^{\infty} (2)P(X=k-2)) = 2$.
Lastly, we can also see that $\displaystyle \sum \limits_{k=2}^{\infty} (k-1)P(X=k-1) = E(X)$
and that $\displaystyle \sum \limits_{k=2}^{\infty} (k-2)P(X=k-2) = E(X)$
Therefore, $\displaystyle \sum \limits_{k=2}^{\infty} (k)P(X=k) = \frac{1}{4}(E(X) + \frac{1}{2} + E(X) + 2) = (\frac{1}{2})E(X) + \frac{5}{8}$
Now, we have $\displaystyle E(X) = (0)(P(X=0)) + (1)(P(X=1)) + \sum \limits_{k=2}^{\infty} (k)P(X=k) = \frac{1}{8} + \sum \limits_{k=2}^{\infty} (k)P(X=k) = \frac{1}{8} + (\frac{1}{2})E(X) + \frac{5}{8}$
Re-arranging, we have $\displaystyle (\frac{1}{2})E(X) = \frac{6}{8}$ yielding $E(X) = 1.5$
$\square$
The second method still takes advantage of the recurrence relation, but does not go the extra mile in that an actual closed form expression for $P(X=k)$ is not necessary.
$\textbf{Definition 1 (Expected Value)}$ : The expected value of an experiment with random variable $X$ is $\displaystyle E(X) = \sum_{\forall x} P(X=x)(x)$
In our case, our random variable is $X = no. \ of \ points $, and therefore $X$ can take on any of the values in $\{0,1,2,...\}$, or in other words, $X = \mathbb {N}$
We are currently faced with the task of trying to compute $E(X)$. Initially, I fell into a trap when faced with this problem, as I attempted to find a closed form expression for $P(X=x)$ in order to compute $E(X)$, a method that, while viable, leads to further messiness involving radicals and exponents.
While this was not the method I ultimately used in order to solve the problem, I'll go through it anyway for the sake of completeness.
I first noticed the following recurrence relation: $P(X=k) = \frac{1}{4} (P(X=k-1) + P(X = k-2) )$,
for all $k\geq 2, k\in \mathbb {N}$, with initial conditions: $P(X = 0) = \frac{1}{2} \ and \ P(X=1) = \frac{1}{8}$
I'll briefly justify this recurrence relation: Note that the only possible method to increase points at any point during the experiment is to flip heads, as flipping tails leaves the number of points at any particular point in time unchanged.
Therefore, if we have received $x+2$ points at the end of our experiment, we may have either flipped heads and rolled even after $x$ points or flipped heads and rolled odd after $x+1$ points.
Lets analyze this further: We'll denote sample points as sequences of $Heads = H$, $Tails = T$, $Even\ roll = E$, $Odd \ roll = O$
As an example, a sample point in the event $X = 4$ is $HOHOHET$
The $T$ at the end of any of our sequences is just to terminate the sequence, as it doesn't actually add or subtract any points.
Consider the event $X = x+2$. How many sample points are in the sample space of this event? Well, each sample point in $X = x+2$ is simply a sample point in $X=x+1$ with an additional $HO$, or is a sample point in $X = x$ with an additional $HE$.
To illustrate this, lets take $X=4$ as an example. I'll list out all of the sample points in $X=4$.
Here they are: $\{HEHET, HOHOHET, HOHEHOT, HEHOHOT, HOHOHOHOT\}$
Now, here are all the sample points for $X=3$
$\{HOHET, HEHOT, HOHOHOT\}$
and all the sample points for $X=2$
$\{HET, HOHOT\}$
First of all, we see that the number of sample points in the event $X=4$ is equal to the sum of the number of sample points in events $X=3$ and $X=2$.
Secondly, we see that as previously mentioned, each sample point in $X=4$ is either a sample point in $X=3$ with an additional $HO$ or a sample point in $X=2$ with an additional $HE$.
For example, take the sample point $HEHOHOT$. This is $HEHOT$ (a sample point of $X=3$) with an additional $HO$.
Now, what does this mean in terms of probability?
Well, an additional $HO$ translates to multiplication by $(\frac{1}{2})(\frac{1}{2}) = \frac{1}{4}$, and an additional $HE$ also translates to multiplication by $(\frac{1}{2})(\frac{1}{2}) = \frac{1}{4}$.
So, $P(X = k) = (probability \ of \ HO )(P(X = k-1)) + (probability \ of \ HE )(P(X = k-2))$
Since $(probability \ of \ HO ) = (probability \ of \ HE ) = \frac{1}{4}$, we have
$P(X=k) = \frac{1}{4} (P(X=k-1) + P(X = k-2) )$
Great, so how can we use this recurrence relation to determine a closed form expression for $P(X=k)$ ?
The answer lies in the theorem below:
$\textbf{Theorem 1 (Solution of second order linear homogeneous recurrence relation with distinct roots)}$
A recurrence relation $u_n = au_{n-1} + bu_{n-2}$ for non-zero $a,b$ has closed form solution:
$u_n = c(\lambda_1)^n + d(\lambda_2)^n$.
Where $\lambda_1$ and $\lambda_2$ are distinct roots of the characteristic equation:
$\lambda^2 - a\lambda - b = 0$.
and $c,d$ are constants that are determined by two initial conditions, namely $u_1 = known \ value$ and $u_2 = known \ value$
$\square$
One can show that Theorem 1 is indeed true by substituting this closed form solution back into the original recurrence relation, although this method of 'proving' Theorem 1 is quite unsatisfying and leaves much to be desired as it does not shed any light on what motivated Theorem 1 in the first place.
Unfortunately, I do not know much about what motivated Theorem 1, perhaps after some research I'll be able to write a post about this in future.
Anyway, with the help of Theorem 1, I was able to work out a closed form expression for $P(X = k)$.
Here it is:
$\displaystyle P(X = k) = (\frac{\sqrt{17} + 1}{4\sqrt{17}})(\frac{1 + \sqrt{17}}{8})^k + (\frac{\sqrt{17} - 1}{4\sqrt{17}})(\frac{1 - \sqrt{17}}{8})^k$
(This is also how I was able to obtain a plot of $P(X=k)$ against $k$)
Using this, it is possible to just plug the expression we obtained for $P(X=k)$ into the $E(X)$ summation and do a bit of algebra relating to series of the form $\displaystyle \sum_{\forall k} kr^k$ to work out the answer. However, this is quite messy and so I tried to avoid it with an alternative route that gets rid of the need for a closed form expression of $P(X=k)$ altogether.
Here is the alternative method:
$\displaystyle E(X) = \sum \limits_{k=0}^{\infty} (k)P(X=k) = (0)P(X=0) + (1)P(X=1) + \sum \limits_{k=2}^{\infty} (k)P(X=k)$
Now for $k\geq 2$ we know that $P(X=k) = \frac{1}{4} (P(X=k-1) + P(X = k-2) )$
This means that $\displaystyle \sum \limits_{k=2}^{\infty} (k)P(X=k) = \frac{1}{4}(\sum \limits_{k=2}^{\infty} (k)P(X=k-1) + \sum \limits_{k=2}^{\infty} (k)P(X=k-2))$
Lets concentrate on each individual term in this expression:
$\displaystyle \sum \limits_{k=2}^{\infty} (k)P(X=k-1) = \sum \limits_{k=2}^{\infty} (k-1)P(X=k-1) + \sum \limits_{k=2}^{\infty} P(X=k-1)$
We know that $\displaystyle \sum \limits_{k=2}^{\infty} P(X=k-1) = \sum \limits_{k=1}^{\infty} P(X=k-1) - P(X=0) = \sum \limits_{k=1}^{\infty} P(X=k-1) - \frac{1}{2} = 1 - \frac{1}{2} = \frac{1}{2}$.
Furthermore, $\displaystyle \sum \limits_{k=2}^{\infty} (k)P(X=k-2)) = \sum \limits_{k=2}^{\infty} (k-2)P(X=k-2)) + \sum \limits_{k=2}^{\infty} (2)P(X=k-2))$
We know that $\displaystyle \sum \limits_{k=2}^{\infty} (2)P(X=k-2)) = 2$.
Lastly, we can also see that $\displaystyle \sum \limits_{k=2}^{\infty} (k-1)P(X=k-1) = E(X)$
and that $\displaystyle \sum \limits_{k=2}^{\infty} (k-2)P(X=k-2) = E(X)$
Therefore, $\displaystyle \sum \limits_{k=2}^{\infty} (k)P(X=k) = \frac{1}{4}(E(X) + \frac{1}{2} + E(X) + 2) = (\frac{1}{2})E(X) + \frac{5}{8}$
Now, we have $\displaystyle E(X) = (0)(P(X=0)) + (1)(P(X=1)) + \sum \limits_{k=2}^{\infty} (k)P(X=k) = \frac{1}{8} + \sum \limits_{k=2}^{\infty} (k)P(X=k) = \frac{1}{8} + (\frac{1}{2})E(X) + \frac{5}{8}$
Re-arranging, we have $\displaystyle (\frac{1}{2})E(X) = \frac{6}{8}$ yielding $E(X) = 1.5$
$\square$
The second method still takes advantage of the recurrence relation, but does not go the extra mile in that an actual closed form expression for $P(X=k)$ is not necessary.
No comments:
Post a Comment