stats510 -Homework 1 - Solved

#1
The following exercise is given in the notes. We can replace the Axiom of Countable Additivity with the Axiom of Finite Additivity. As explained, countable additivity implies finite additivity. For a decreasing sequence of sets , let Ai & B mean that . From this, consider the following:

If Ai & ∅, then lim P(Ai) = 0. (Axiom of Continuity (from above))

i→∞

Show that the Axiom of Finite Additivity and the Axiom of Continuity imply the Axiom of Countable Additivity.

#2
Let Ω be an uncountable sample space and A be the set of co-countable sets

A = {A ⊂ Ω : A is countable or Ac is countable},

which was shown to be a sigma algebra in the lecture. Show that the mapping P with domain A where for any A ∈ A we have

(

0  if A is countable P(A) =

1  if Ac is countable

is a well-defined set function on A and a probability measure on A.

#3
Suppose 8 balls are thrown randomly into 20 boxes. What is the probability that a single box receives all 8 balls? What is the probability that no box receives more than one ball?

#4
A box contains light bulbs and some are defective. Suppose the box has 24 light bulbs and 4 are defective. Suppose one person selects 10 bulbs from the box and another person takes the remaining bulbs. Write the probability that all four defective bulbs are picked by the same person.

#5
A deck of 52 cards contains four aces. If the cards are shuffled and distributed in a (uniformly) random manner to four players, what is the probability that all players receive exactly one ace?

#6
Suppose n players enter a tournament. If n is even, then in the first round, players are paired against one another randomly to play a match. Assume all players are equally skilled so that when any two play a match, the winner is determined randomly. The loser in each pair is eliminated, and the winner in each pair continues to the next round. If n is odd, then one player is selected at random to bypass to the second round without playing a match. The remaining players are put into a common room, where this procedure is repeated. Repeat this procedure until a single individual remains. Given two players A and B, write the probability that A and B ever play against each other in the tournament.

#7
In graph theory, a tree T = (V,E) with vertex set V and edge set E is a connected graph where every pair of vertices v1,v2 ∈ V has one and only one path of edges joining them. (In this problem, edges are undirected.) Such a tree is (unrooted) binary if every vertex has degree 1 or 3. Recall that the degree of a vertex v in an undirected graph is the number of edges incident with v. The vertices of degree 1 are called leaves or leaf vertices, while the vertices of degree 3 are called interior vertices.

(a)              Suppose a binary tree has n leaves. Prove that for n ≥ 2, the number of edges is |E| = 2n−3 and the number of vertices is |V | = 2n−2. (Suggestion: Use induction on n.)

Before the next part, we introduce more terminology. Given a binary tree with n leaves, we may attach to each leaf a unique label Ai,i ∈ {1,...,n}. If the labels are unique, we say that the tree with its leaf-labels are a phylogenetic tree. Two phylogenetic trees are considered identical if permuting the leaf labels does not affect the hierarchical clustering. For instance, in Figure 1, switching the labels C and D does not change any relationship between C and any of the other vertices (note that examples of this type are not exhaustive).

(b)              Suppose there are n leaves in a phylogenetic tree. Write the number of possible phylogenetic trees and prove your result.

#8
Consider a symmetric simple random walk on the integers starting at 0. In the first step, you start at 0 and go either left (negative) or right (positive) by one integer each with probability 1/2. Then repeat this procedure independently at any step in the process. Suppose you walk exactly n steps.

Write the probability the walk after step n is at 0.


 

Figure 1: Two phylogenetic trees with C and D switched. It turns out that these reflect the same hierarchy, so we regard them as identical.