puzzles in probability & mathematical statistics

Question 1: An urn contains "k" black balls and a single red ball. Peter and Paula take turns drawing balls from the urn (without replacement) until someone draws the red ball (after which they win. If you are given the chocice to either go first or second, which one should you do?

Solution: My Naive brute force approach was to start enumerating all of the possibilities out. Essentially, see if I could get a "historical" mathematical representation of the probability of winning given k+1 balls and you going first. It was quite cumbersome. The elegant solution is to think about it in the following way. ALL of the balls are going to be drawn. If the number of balls in the urn is even, regardless of who goes first, each player will get half of the balls in the urn. Clearly, it is equally likely for the red ball to be in either half. We are essentially saying, that of all the different permutations of balls within the urn, half of those permutations contain the red ball in slots that belong to Peter and in the other half of those permutations, the red ball will be in slots that belong to Paula. If the number of balls is odd (i.e (k+1) mod 2 = (1)) then whoever goes first will have more permuations in which the red ball is in my slot - since the red ball is equally likely to be in any slot and I will have more slots allotted to me in this transformed problem. Thus, if the number of balls is ODD you have a slightly higher change of winning if you go first, and it does not matter if the number of balls is even

Question 2: There are a bunch of people playing in a tennis tournament. There are 2 female players and 8 male players. The matches are selected by randomly drawing the players names from a hat - the first two names play, the 3rd and 4rth play, etc. What is the probability that there will not be a single match involving two female players?

Solution: Try to generalize into the case where there are 2n players and 2 <= k <= n are female plaers. What is probability p(k,n) that among the n matches there will not be a single one involving two female players? Let's try a counting approach. Let's also only focus on the female players since that is the probability we are most interested in. There are "n" games. Therefore, there are C(n,k) different combinations in which all the female players are in different ones. For each of those games, the female player could be in the first or second slot, so we have to multiply C(n, k) * 2^k. The total combination space is a situation that consists of 2n spaces, of which "k" female players need to be slotted in. There are thus C(2n, k) ways of doing this. Thus, the most general formula for the probability is:

C(n,k) * 2^k / C(2n, k)

Question 3: Assume Peter and Paula are playing a game that consists of several rounds. Each player has a 1/2 change of winning each round and whoever reaches "n" rounds first wins the game. Suppose the game is interrupted when Peter needs "a" more rounds and Paula needs "b" more rounds to win. What are the respective probabilites for both Peter and Paula to then win the game?

Soltuion: Again, one could try to brute force through all of the possibilities, taking a historical probability approach and enumerating all of the paths to victory for each player. However, we can liken this to question 1; there are going to be at most a+b-1 more games to be played. So let's just transform this problem to the problem in which both Peter and Paula definitely play a+b-1 more games. If this is the case, then if Peter wins, that means of those a+b-1 games, he has won at least a or more of them. So the probability of Peter winning then is equivalent to the probability of playing a+b-1 games and having peter win at least a of those games. Since the likelihood of winning is the same for both Peter and Paula, the total number of ways that a+b-1 games could occur is 2^(a+b-1). The number of ways that Peter wins is $\sum_{i=a}^{a+b-1} \binom{a+b-1}{i}$ Thus:

$P(Peter) = \frac{1}{2^(a+b-1)} \sum_{i=a}^{a+b-1} \binom{a+b-1}{i}$

Question 4: Suppose I flip a coin 2n times. How often is it the case that I get an even n:n split?

Solution: This one is fairly straightforward. The principles we will leverage is "counting". Counting is easy in this case, and we can determine the probability by looking at the total number of cases of an n:n split over the total number of cases. Clearly the total number of cases is $2^{2n}$. The number of cases in which there is an even split is essentially equivalent to me selecting $n$ flips out of the total $2n$ flips and designating them as "heads". The other $n$ will then be counted as "tails". This will be the total number of cases in which there is an even split (since in any even split there must be "n" heads and we have enumerated all of the cases in which we have selected "n"). Thus: $P= \frac{\binom{2n}{n}}{2^{2n}}$

Question 5: Imagine that there is an urn with 6 balls. 3 red and 3 blue. One ball is removed. Peter then draws from the urn 6 times (with replacement) and each time he draws the ball, it is red. Paula draws the ball 600 times (100 times more!) and 303 times it is a red ball and 297 times it is a blue ball. Both will of course predict that the ball that was removed was Blue, since they both got a greater fraction of red balls. But which one has more strength in their conviction?

Solution: This classically falls into the category of a Bayes Theorem. We are observing some state as "evidence" for some other hidden probability. So let's just write out the definitions and see what happens:

(insert photo from iPad)

Question 6: Suppose a company has a policy such that any day in which one of their "n" workers has a birthday is considered a full holiday. Now suppose the company needs to make a hiring decision regarding the optimal number of employees to hire to maximize their expected "working days" which is defined as n_workers * days_worked. Assume that the probability that any given person has their birthday on day i is equal to 1/365.

Solution: The first step is to think about the general relationship between n and working_days. Assume n = 1. Then the expected number of working days is 364. What happens as we increase n? Clearly it starts to increase, with n=2, the expected working days would be 2 * E[days_worked]. E[days_worked] is 364 * (1/365) + (363) * (364/365). Obviously though, if we increase n to extremely large values, E[days_worked] would go to zero.

So there must be some optimal value. We can write this expression as a function of "n" and then solve a simple optimization function over it. The easiest way to think of E[days_worked] is actually from the perspective of any single day (like most probability problems, adopting the right lens is the key to making the problem solvable). Clearly we can use linearity of expectation s.t E[days_worked] = $\sum P(day)$. The probability that for a specific day being a day that is worked is clearly $(364/365)^n$ - the likelihood that all "n" workers have a birthday not on that day. Thus, the final expression is: $E[working_{days}] = n * \sum_{i=1}^{365} (364/365)^n$

Question 7: Suppose Pater draws "n" samples from a distribution and orders them by value. Then Paula draws another sample and slots it in according to its correct rank (i.e. if it is greater than 50 of the values it is slotted in rank 51 and if it lower than all of Peters values it is slotted in at rank 1). Is it more likely that Paula's draw has rank 51, or rank 1?

Solution: This problem already hints at multiple ways of thinking about probability that are touched on before. First, we can try to reason about small cases, such as when Peter only draws 1 or 2 samples. Can we then use the pattern to come up with a general formula to determine the probability Paula's value will occupy rank "k" over n+1 total samples. The second idea here is to try to cast it into an equivalent problem - which is that of counting the number of permutations. This is much easier than thinking through how different independent realizations will "rank" according to each other. We can essentially think of the problem as drawing n+1 realizations from the same distribution, and clearly each permutation of the ordering is going to be equally likely since they are coming from the same distribution. Therefore, it is equally likely that Paula's draw falls into any of those n+1 slots which are equivalent to the ranks. Therefore, every rank has likelihood (1/n+1)

Question 8: Suppose we have two independent RVs, X, Y. One can clearly imagine the two different cases of a.) mixing two independent R.V's and b.) drawing from a new distribution that is defined as a mixture of X and Y. Concretely, we can define two different new RVs: A = 1/2(X+Y) and B, with f(b) = 1/2(fx(b) + fy(b)). For A, we sample from both X and Y, and then create a new realization that is the average of those two values. For B, we define a new distribution that half of the time comes from a distribution equivalent to X and half of the time comes from a distribution equivalent to Y. How do the means and variances compare?

Solution: For both A & B it is clearly the case that the means are exactly the average of the means of A & B (we can see this from the straightforward application of expected value properites). Let's look at the variance of A.

(insert photo from iPad)

Lets also look at the variance of B. The first step is to try to come up with an expression of B that we can reason about at a different level; just operating at the level of the PDF is possible (we could write out the definition of variance and proceed directly from there) but this would obviously be way too cumbersome. Instead, we can define an Indicator Variable I and define B as B := IX + (1-I)Y where I takes on a value of 1 with probability 1/2 and takes a value of 0 with probability 1/2.

(insert photo from iPad)

Question 9: Suppose we are trying to raise money for an event and we discover that each person asked to donate donates from an exponential distribution with mean 20. If we are trying to raise $100 total, then what is the distribution, mean, and variance of the number of successive donars needed until at least $100 has been collected?

Solution: The phrasing of the problem seems to suggest that a recursive or historical approach might be best suited. Imagine that we get one donor. Based on what they donate, we essentially end up with an analagous problem but with a smaller target goal. Thus, we can condition on the first donor and then reason through what the likely following outcomes would be. If the mean of the exponential distribution is 20, then the $\lambda$ paramter is 1/20. We can thus write the following: $f(n \mid 100) = \int_{0}^{100} \lambda e^{-\lambda x} f(n-1 \mid 100 - x) \ dx$. Solving this equation is a technical matter involving recurrence relations which I will not go into detail here

Question 10: Suppose we have some random Poisson process defined as ${N(t), t \geq 0}$. Recall that a Poisson Process is a stochastic process that is used to model the probability of some number of events occuring in the time interval "t". So when we define it above like so, we are saying the set of all the number of events that are occuring after time "t". The number of events when t=0 is 0. The number of events that occur in disjoint time intervals are independent. And the number of events in any time interval is modelled by a Poisson R.V. These last two conditions is basically thought of as P(N(t + h) - N(t) = k) = Poisson(k * h). This is the formal definition of the Poisson Process.

Suppose we let $W$ be the waiting time for the first time no event in {N(t)} has occured in the last $\tau$ time units. What is $E[W]$?

Solution: Let's first understand what this question is actually trying to ask. We want the expected waiting time for no events to happen in a given interval of $\tau$. Given the independence of successive events (given in the problem statement), this again also leads us to think of a similar recurrence or historical approach to tackling the problem.

(insert photo from iPad)