Suppose we need to divide people into two groups A and B, the first person will be assigned to either of the group with probability $0.5$, from the second person, the assignment will be done based on the following rule:
If the number of person in the group A is $a$ and the number of people in the group B is $b$, then for the $(a+b+1)_{th}$ assignment, the probability of assignment to Group A is $\frac{b}{a+b}$ and the probability of assignment to Group B is $\frac{a}{a+b}$.

After finishing the assignment of $n$ person, we define $X_{n}$ as the random variable for the number of person in Group A. Apparently we have $E(X_{n}) =\frac{n}{2} $, also I assume that the variance $V(X_{n})$ can be calculate in a recursive way.

My question is how to prove the following recursive formula:
$V(X_{n}) = \frac{n-3}{n-1} V(X_{n-1}) + \frac{1}{4}$

By applying conditional probability, I was able to calculate the expectation in a recursive way as below:
$E({X_{n+1}|X_{n}}) = P({X_{n+1} = X_{n} + 1|X_{n}})(X_{n}+1) + P({X_{n+1} = X_{n} |X_{n}})X_{n} = (1-\frac{1}{n})X_{n} + 1$

$E({X_{n+1}}) = E_{X_{n}}(E({X_{n+1}|X_{n}})) = (1-\frac{1}{n})E(X_{n}) + 1$

  • $\begingroup$ It would be easier to understand if you wrote "the first [person] will e assigned to either group..." $\endgroup$
    – Michael
    May 29 '20 at 4:59
  • $\begingroup$ You can calculate $E[X_{n+1}^2|X_n]$. $\endgroup$
    – Michael
    May 29 '20 at 4:59
  • $\begingroup$ Thank you so much for the comment, if possible, could you be more specific $\endgroup$
    – koori
    May 29 '20 at 5:10
  • $\begingroup$ How did you calculate $E[X_n]$? I assume it was via $E[X_{n+1}|X_n]$ or $E[X_{n+1}|X_n=a]$. $\endgroup$
    – Michael
    May 29 '20 at 5:38
  • $\begingroup$ Thank you for the comments, I will try to use the conditional expectation to calculate $E(X_{n})$. Previously, I just assume that it is $n/2$ since the distribution is symmetric $\endgroup$
    – koori
    May 29 '20 at 5:54

Similarly, we can calculate:
$E({X^{2}_{n+1}|X_{n}}) = (X_{n} +1)^{2}\frac{n-X_{n}}{n} +X_{n}^{2}\frac{X_{n}}{n} = (X_{n} +1)^{2} - \frac{2X_{n}+X_{n}^2}{n}$

$V({X_{n+1}|X_{n}}) = E({X^{2}_{n+1}|X_{n}}) - E({X_{n+1}|X_{n}})^2 =\frac{X_{n}}{n} - \frac{X_{n}^2}{n^2} $

$V({X_{n+1}}) = E_{X_n}(V({X_{n+1}|X_{n}})) + V_{X_n}(E({X_{n+1}|X_{n}})) = \frac{E(X_{n})}{n} - \frac{E(X_{n}^2)}{n^2} +(\frac{n-1}{n})^2V(X_n) $
Since we have $E(X_{n}) =\frac{n}{2} $ and $E(X_{n}^2) =V(X_n) + E(X_n)^2$, Finally we can get

$V(X_{n+1}) = \frac{n-2}{n} V(X_{n}) + \frac{1}{4}$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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