There are $N$ coins, $N \geq 1$. We place them randomly on vertices of $M$-sided regular polygon, $M \geq N$, in every vertice there is at most $1$ coin.
We call X the number of sides with coins on both vertices. Calculate the expected value and variance of $X$.
We have as many sides as there are vertices, that is $M$. That's why:
$$X = \sum_{i=1}^{M} x_i \ \text{ , where: } x_i = 1 \text{ if side $i$ has coins on both vertices, } x_i = 0 \text{ otherwise. }$$
We have then that for expected value:
$$\mathbb{E} X = \mathbb{E} \sum_{i=1}^{M} x_i = \sum_{i=1}^{M} \mathbb{E} x_i = M \mathbb{P}(x_i = 1)$$
When we think what's the probability of having one of $N$ coins on a chosen one of $M$ vertices it's $ \ \frac{N}{M} \ $. Then on another (when we have already placed the former one), it's: $ \ \frac{N-1}{M-1} \ $. Therefore:
$\mathbb{P}(x_i = 1) = \frac{N}{M} \cdot \frac{N-1}{M-1}$
And we get that: $\mathbb{E} X = M \cdot \frac{N}{M} \cdot \frac{N-1}{M-1} = \frac{N(N-1)}{M-1}$
For the variance I though of using the formula: $Var(X) = \mathbb{E} X^2 - \left( \mathbb{E}X \right)^2 $.
We see that: $\left( \mathbb{E}X \right)^2 = \left( \frac{N(N-1)}{M-1} \right)^2$
It's harder to find $\mathbb{E} X^2$:
We know that: $\mathbb{E} X^2 = \mathbb{E} \left( \sum_{i=1}^{M} x_i \right)^2 = \mathbb{E} \sum_{i=1}^{M} x_i^2 + \mathbb{E} 2 \sum_{j=1}^{M} \sum_{i=1}^{j-1} \ x_i \ x_j = \sum_{i=1}^{M} \mathbb{E} x_i^2 + \sum_{j=1}^{M} \sum_{i=1}^{j-1} \mathbb{E} \ x_i \ x_j$
So we need $\mathbb{E} \ x_i \ x_j$, there are $2$ possibilities:
- segments $i$ and $j$ don't have no common vertives: $\mathbb{E} x_i x_j = \frac{N(N-1)(N-2)(N-3)}{M(M-1)(M-2)(M-3)}$
- segments $i$ and $j$ have a common vertice: we have 3 consecutive vertices with coins:$\mathbb{E} x_i x_j = \frac{N(N-1)(N-2)}{M(M-1)(M-2)}$
Now we need to put those $2$ possibilities into a formula for $\mathbb{E} X^2$. When we take a segment $i$, it makes a $2^{nd}$ case with $2$ segments and $1^{st}$ case with all $M-3$ other segments. Therefore we have that for $\frac{M(M-1)}{2}$ pairs there are $M$ pairs of the $2^{nd}$ type and $\frac{M(M-1)}{2} - M$ pairs of $1^{st}$ type.
Therefore we have that:
$\mathbb{E} X^2 = M \left( \frac{N(N-1)}{M-1} \right)^2 + 2 \left( M \frac{N(N-1)(N-2)}{M(M-1)(M-2)} + \left( \frac{M(M-1)}{2} - M \right) \frac{N(N-1)(N-2)(N-3)}{M(M-1)(M-2)(M-3)} \right)$
And finally the $Var(X)$ is equal to:
$M \left( \frac{N(N-1)}{M-1} \right)^2 + 2 \left( M \frac{N(N-1)(N-2)}{M(M-1)(M-2)} + \left( \frac{M(M-1)}{2} - M \right) \frac{N(N-1)(N-2)(N-3)}{M(M-1)(M-2)(M-3)} \right) - \left( \frac{N(N-1)}{M-1} \right)^2 $
Is that correct?
I think if $x_i$ and $x_j$ don't share a vertex, then the chance of both is $$\frac{N(N-1)(N-2)(N-3)}{M(M-1)(M-2)(M-3)}$$