Gregg O. answered • 06/14/16
Tutor
5.0
(366)
Engineering Valedictorian Available for Math Tutoring
This is a fun problem. Let's first handle the probability that the ith number in the list will be checked.
Let's first use n to stand for a number in the list, and then a subscript to note successorship. For instance, n1 < n3, since n3 is a "successor" in the list of integers ordered from least to greatest. To avoid confusion, I note that the subscript does NOT stand for position in the list.
Since the integers are distinct, for every j, we have numbers n1, n2, ... ,nj-1, nj such that
n1 < n2 < ... < nj-1 < nj.
For the ith number in the list to be checked, it must be the greatest out of all numbers which precede it. Let's examine the 3rd number (i=3) of the list. Here, we have 3 numbers, n1, n2, and n3. The third number will only be checked if n3 is in the third position in the list; if n3 occupies any other position, the succeeding numbers in the list must remain unchecked. This leaves 2 other numbers which can be arranged at will to occupy the first and second positions, from which we have 2 x 1 total arrangements such that n3 occurs last.
Assuming that each outcome is equally likely, we can divide the number of arrangements in the event that n3 occurs last by the total number of ordered arrangements of 3 numbers to calculate the probability the 3rd number on the list is checked:
2! / 3P3, which comes out to 1/3.
Likewise, for the 4th number on the list to be checked, n4 must be in the final position, leaving 3 numbers to be arranged at will. This produces 3! arrangements, out of a total of 4P4 possible arrangments:
3! / 4P4 = 1/4.
In general, for the ith number we have
(i-1)! /iPi = (i-1)! / i! = (i-1)! / [(i-1)! * i] = 1/i.
I'm a bit tired now, so I'll get back to you on the expected value part tomorrow. Hope this has helped!
Stacy S.
My mistake, the events are independent - it still seems extremely complicated to calculate the expected value though, which makes me question if I'm thinking about it the right way.
If X is the random variable representing the number of marked numbers in the list, then E(X) = P(X = 1) * 1 + P(X = 2) * 2 + ... + P (X = 20) *20. But how do I come up with an elegant way to represent P(X = r)?
Report
06/14/16
Gregg O.
Sorry for the late reply. To handle the expected value of the number of checked integers on the list, we'll assign a discrete random variable, Xi, to the ith position in the list (note that this produces 20 discrete RVs). Each Xi can have two values: 1 if the ith number in the list is checked, or 0 if it is not.
The number of checked integers in the list is then given by X1 + X2 + ... + X20. This is the crucial insight in finding the expected value of the number of the checked integers on the list
We can calculate the expected value of each Xi from its PMF, which is
{1 - 1/i, x=0
PXi(x) = {1/i, x=1
This simply states that the probability of Xi being 0 is (1 - 1/i), while the probability of it being 1 is 1/i. The expected value for Xi is then ∑xP(Xi = x), or 0(1-1/i) + 1(1/i) = 1/i. To summarize,
E(Xi) = 1/i.
Now, the expected value of the sum of random variables is equal to the sum of the expected values. That is,
E[∑Xi] = ∑[E(Xi)], or
∑1/i = 1 + 1/2 + 1/3 + ... + 1/20.
This is calculator work, and leads to a rounded answer of 3.598.
Report
06/17/16
Stacy S.
06/14/16