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 haveE[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
Linearity of Expectation
algorithm analysis
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]$.