You observe k i.i.d. copies of the discrete uniform random variable Xi , which takes values 1 through n with equal probability.
Define the random variable M as the maximum of these random variables, M=maxi(Xi) .
1.) Find the probability that M≤m , as a function of m , for m∈{1,2,…,n} .
2.) Find the probability that M=1 .
3.) Find the probability that M=m for m∈{2,3,…n} .
4.) For n=2 , find E[M] and Var(M) as a function of k .
5.) As k (the number of samples) becomes very large, what is E[M] in terms of n ?
As k→∞ , E[M]→
1. (m/n)^k
1.) The probability that M ≤ m is equivalent to the probability that all k samples are less than or equal to m. Since each sample is independent and uniformly distributed, this is given by:
P(M ≤ m) = P(X1 ≤ m) * P(X2 ≤ m) * ... * P(Xk ≤ m)
Since each Xi has equal probability of being less than or equal to m (which is 1/m), the probability is:
P(M ≤ m) = (1/m)^k
2.) To find the probability that M = 1, we need all k samples to be equal to 1. Since each Xi has equal probability of being 1 (which is 1/n), the probability is:
P(M = 1) = (1/n)^k
3.) To find the probability that M = m for m ∈ {2, 3, ..., n}, we need at least one sample to be equal to m and all other samples to be less than m. Since each sample has equal probability of being m (which is 1/n), and the rest of the samples have equal probability of being less than m (which is (m-1)/n), the probability is:
P(M = m) = P(X1 = m) * P(X2 < m) * ... * P(Xk < m)
= (1/n) * ((m-1)/n)^(k-1)
4.) For n = 2, there are only two possible values for M: 1 and 2. Let's calculate E[M] and Var(M) as functions of k:
For M = 1:
P(M = 1) = (1/2)^k
For M = 2:
P(M = 2) = 1 - P(M = 1) = 1 - (1/2)^k
E[M] = 1 * P(M = 1) + 2 * P(M = 2) = (1/2)^k + 2*(1 - (1/2)^k) = 2 - (1/2)^k
To calculate Var(M), we can use the formula:
Var(M) = E[M^2] - (E[M])^2
E[M^2] = 1^2 * P(M = 1) + 2^2 * P(M = 2) = (1/2)^k + 4*(1 - (1/2)^k) = 4 - 3*(1/2)^k
Var(M) = E[M^2] - (E[M])^2 = 4 - 3*(1/2)^k - (2 - (1/2)^k)^2
5.) As k (the number of samples) becomes very large, the behavior of E[M] can be observed. Let's analyze the expression for E[M] when k approaches infinity:
E[M] = 2 - (1/2)^k
As k approaches infinity, (1/2)^k approaches 0. Therefore, the term (1/2)^k becomes negligible, and we have:
E[M] → 2
So, as k approaches infinity, E[M] approaches 2 in terms of n.
1.) To find the probability that M≤m, we can consider the event that each Xi is less than or equal to m. Since Xi follows a discrete uniform distribution with values 1 through n, the probability that each Xi is less than or equal to m is m/n. Since the variables Xi are independent and identically distributed, the probability that M≤m is the product of the individual probabilities, which is (m/n)^k.
2.) To find the probability that M=1, we need all k observations to be equal to 1. Thus, the probability is (1/n)^k.
3.) To find the probability that M=m for m∈{2,3,…,n}, we need at least one observation to be equal to m and all other observations to be less than m. The probability that one particular observation is equal to m is 1/n and the probability that all other (k-1) observations are less than m is (m-1)/n. Therefore, the probability that M=m is (1/n) * ((m-1)/n)^(k-1).
4.) For n=2, the random variable M can only take values 1 and 2. Let's calculate E[M] and Var(M).
The probability that M=1 is given by the answer to question 2, which is (1/2)^k.
The probability that M=2 is 1 - the probability that M=1, which is 1 - (1/2)^k.
To calculate E[M], we multiply the values of M with their respective probabilities and sum them up: E[M] = 1*(1/2)^k + 2*(1 - (1/2)^k) = 1 + (1 - 2^(-k+1))/2.
To calculate Var(M), we can use the formula Var(M) = E[M^2] - (E[M])^2:
E[M^2] = 1^2*(1/2)^k + 2^2*(1 - (1/2)^k) = 1 + (3 - 2^(-k+1))/2.
Var(M) = E[M^2] - (E[M])^2 = [1 + (3 - 2^(-k+1))/2] - [1 + (1 - 2^(-k+1))/2]^2 = 9/4 - (1 - 2^(-k+1))^2/4.
5.) As k (the number of samples) becomes very large, E[M] approaches the expected value of the maximum of the discrete uniform random variable Xi, which is n. So, as k→∞, E[M]→ n.
To find the probability that M ≤ m, we need to consider the event that all k observations are less than or equal to m. Since each observation is an i.i.d. discrete uniform random variable, the probability of any single observation being less than or equal to m is 𝟏/m. Therefore, the probability that M ≤ m is the product of the probabilities of each observation being less than or equal to m.
1.) P(M ≤ m) = (𝟏/m)^k
To find the probability that M = 1, we have to consider the event that all k observations are equal to 1.
2.) P(M = 1) = (𝟏/n)^k
To find the probability that M = m for m ∈ {2, 3, ..., n}, we need to consider the event that at least one of the k observations is equal to m. The probability of any single observation being equal to m is 𝟏/n. Therefore, we subtract the probability that all observations are less than m to get the desired probability.
3.) P(M = m) = (𝟏/n)^k - (𝟏/(m-1))^k
For n = 2, the random variable M can only take the values 1 and 2. We can now find the expected value (E[M]) and variance (Var[M]) of M.
4.) E[M] = 1 * P(M = 1) + 2 * P(M = 2)
= 1 * (𝟏/2)^k + 2 * [(𝟏/2)^k - (𝟏/(1))^k]
= 1 - (𝟏/2)^k
Var[M] = E[M^2] - (E[M])^2
= 1 ^ 2 * P(M = 1) + 2 ^ 2 * P(M = 2) - [(1 - (𝟏/2)^k)]^2
= 1 * (𝟏/2)^k + 2 ^ 2 * [(𝟏/2)^k - (𝟏/1)^k] - [1 - (𝟏/2)^k]^2
= (𝟏/4)^k + 4 * [(𝟏/4)^k - 1] - [1 - (𝟏/2)^k]^2
As k (the number of samples) becomes very large, we can analyze E[M] in terms of n.
5.) As k → ∞, since the probability of getting any specific outcome diminishes, we can focus on the term with the highest probability in the sum. In this case, when E[M] is maximized, it means that the maximum possible outcome, n, has the highest probability.
Therefore, as k → ∞, E[M] → n.