1
$\begingroup$

I'm taking a course on Coursera about approximation algorithms for fun and one of the modules uses probability to analyze the cost of a linear program with randomized rounding solution to the set cover problem.

One of the problem set questions is a basic probability question and is as follows:

You ask ten of your friends to give you one dollar (coin) each so that you can buy your favourite pizza.

When you reach the pizza place you realize that it's closed. So you return the coins to your friends by giving each of them a random coin.

1) How likely is that each of them gets the coin they put back?

2) How many of them will get in expectation the coin they put back? (Try to prove this elegantly using techniques discussed in the course)Define the random variables you use.

3) Now suppose that you take one coin to buy a coffee somewhere else. You redistribute the others dollar coins giving each of your friends one coin chosen uniformly at random. How many of your friends will get in expectation the coin they put back?

I've solved the first two parts and I'm thinking for the third part that I should define a random variable Xi that represents whether or not persion i get the coin back that she put in and E[Xi] is the probability that she gets it back.

The probability that she gets it back is 9 / 10 * 1 / 10 = 9 / 100. There's a 9 / 10 chance that her coin was not the coin that I bought coffee with and a 1 / 10 chance that she picks her coin or is left out as there are 9 coins for 10 remaining people.

Taking X as the number of folks that get their coins back I have

E[X] = sum(E[Xi]) over all persons E[X] = 90 / 100 = .9 people are expected to get their coin back.

Is my reasoning sound here? If not, can somebody show me the error of my ways?

Thanks so much,

Stead

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ Welcome to Computer Science! The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$
    – Raphael
    Commented May 26, 2016 at 18:45
  • 2
    $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$
    – Raphael
    Commented May 26, 2016 at 18:46
  • $\begingroup$ Understood. Thanks so much for the feedback. $\endgroup$
    – Steadman Dillroper
    Commented May 27, 2016 at 14:13

1 Answer 1

Reset to default
0
$\begingroup$

Your approach looks good. Let's just write it clearly. Let's look at $E[X_1]$.

With probability $1/10$ the first coin was used to buy the coffee, thus the value is $X_1=0$.

With probability $9/10$ we are back in the situation of part II (we can add a new "Gold" coin - the party that gets this coin will not get his dollar back), so the expectation of this case is just like in Part II.

Adding both cases (with the appropriate weight) should solve your question, for $X_1$, and by the linearity of expectations, and since all parties are symmetric, the answer is $10 E[X_1]$.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.