# How to calculate the following variance in a recursive way

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$$

• It would be easier to understand if you wrote "the first [person] will e assigned to either group..." May 29 '20 at 4:59
• You can calculate $E[X_{n+1}^2|X_n]$. May 29 '20 at 4:59
• Thank you so much for the comment, if possible, could you be more specific May 29 '20 at 5:10
• 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]$. May 29 '20 at 5:38
• 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 May 29 '20 at 5:54

$$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}$$