9
$\begingroup$

Basically I want to know whether the sum being discrete uniform effectively forces the two component random variables to also be uniform on their respective domains.

To be a bit more precise:

Suppose we know $X$ and $Y$ are independent and

$$ X+Y \sim UNIF({1, \dots , n})$$

Does this necessarily imply that both $X$ and $Y$ are discrete uniform as well?

$\endgroup$
  • 2
    $\begingroup$ @SandeepSilwal: I think what Aaron Pereira meant here is "uniform on their supports". E.g. the sum of $X$ uniform on $\{0,1,4,5\}$ and $Y$ uniform on $\{0,2,8,10\}$ is uniform on $\{0,1,\ldots,15\}$. $\endgroup$ – Mateusz Kwaśnicki Nov 12 at 19:59
  • 6
    $\begingroup$ This question seems to be open, and has been asked (in slightly differing form) at MO: mathoverflow.net/questions/339137/… $\endgroup$ – user44191 Nov 12 at 20:44
  • 4
    $\begingroup$ @user44191: Indeed! The question that you linked is, however, more general, and in one of the comments Lutz Mattner gives a reference to an affirmative answer in this particular case: Krasner and Ranulac (1937), Sur une propriété des polynomes de la division du cercle, C.R. Acad. Sci. Paris 204, 397--399. $\endgroup$ – Mateusz Kwaśnicki Nov 13 at 0:46
  • 1
    $\begingroup$ This is Problem 1 in link.springer.com/article/10.1007/s000170050051, Über das Fälschen von Würfeln by Ehrhard Behrends, Elem. Math. 54 (1999), 15–29. Unfortunately my preview (all I can read) stops at the statement of the problem. According to the MathSciNet review 'The author actually solves a more general problem in number theory involving the partitioning of integers.' $\endgroup$ – Mark Wildon Nov 13 at 12:00
  • 1
    $\begingroup$ @MarkWildon : The paper by Behrends is available at ems-ph.org/journals/… $\endgroup$ – Iosif Pinelis Nov 13 at 18:24
3
$\begingroup$

1. Proof of the claim

The following lemma shows that $X$ and $Y$ may also be regarded as integer-valued random variables in OP's scenario.

Lemma. Assume that $X$ and $Y$ are independent random variables. Suppose that there exists a finite set $S\subset\mathbb{R}$ satisfying $$ \mathbb{P}(X+Y \in S) = 1 \qquad \text{and} \qquad \mathbb{P}(X+Y = s) > 0, \quad \forall s \in S. $$ Then there exist $x_0, y_0 \in \mathbb{R}$ such that $X' := X + y_0$ and $Y' := Y + x_0$ satisfy $$\mathbb{P}(X' \in S) = 1 \qquad\text{and}\qquad \mathbb{P}(Y' \in S) = 1.$$ Moreover, $\mathbb{P}(X' = \min S) > 0$ and $\mathbb{P}(Y' = \min S) > 0$.

The proof is postponed to the end. Now write $[\![n]\!] := \{0, \cdots, n-1\}$. Then we prove

Proposition.(1, Lemma 2.1) Let $X$ and $Y$ be independent random variables such that $X+Y$ is uniformly distributed over $[\![n]\!]$. Then both $X$ and $Y$ have uniform distribution.

The following proof is based on the reference 1) mentioned in @Mark Wildon's comment.

Proof. In light of the lemma above, we may assume that both $X$ and $Y$ are supported on $[\![n]\!]$ as well as $\mathbb{P}(X=0,Y=0)=1/n$. Using this, set

$$ A(x) := \sum_{k\geq 0} a_k x^k \qquad \text{and} \qquad B(x) := \sum_{k\geq 0} b_k x^k $$

where $a_k := p_X(k)/p_X(0)$ and $b_k := p_Y(k)/p_Y(0)$. Then it follows that $a_k, b_k$ are all non-negative, $a_0 = b_0 = 1$, and

$$ A(x)B(x) = 1 + x + \cdots + x^{n-1}. $$

From this, it is easy to check that both $A(x)$ and $B(x)$ are palindromic, which will be used later.

Now, to establish the desired assertion, it suffices to show that all of the coefficients of $A(x)$ and $B(x)$ lie in $\{0, 1\}$. To this end, assume otherwise. Let $k_0$ be the smallest index such that either $a_{k_0} \notin \{0, 1\}$ or $b_{k_0} \notin \{0, 1\}$. We know that $k_0 \geq 1$. Moreover,

$$ a_{k_0} + \underbrace{ a_{k_0-1}b_{1} + \cdots + a_1 b_{k_0 - 1} }_{\in \mathbb{N}_0} + b_{k_0} = [x^{k_0}]A(x)B(x) \in \{0, 1\}, $$

forces that $a_{k_0} + b_{k_0} = 1$. So both $a_{k_0}$ and $b_{k_0}$ lie in $(0, 1)$. But if we write $d = \deg B(x)$, then we have $b_{d-k_0} = b_{k_0}$ and $b_d = b_0 = 1$, and so,

$$ 1 < a_{k_0}b_{k_0} + 1 \leq a_{d} + \cdots + a_{k_0}b_{d-k_0} + \cdots + b_{d} = [x^{d}]A(x)B(x) \in \{0, 1\}, $$

a contradiction. Therefore no such $k_0$ exists and the desired claim follows. $\square$

References.

1) Behrends, E., 1999. Über das Fälschen von Würfeln. Elem. Math. 54, 15–29. https://doi.org/10.1007/s000170050051

2. Further questions

Based on some simulations as well as actual computation for small $n$, I conjecture that the followings hold:

Conjecture. Let $A(x)$ and $B(x)$ be monic polynomials with coefficients in $[0, \infty)$. Assume that there exists an integer $n \geq 1$ such that $$ A(x)B(x) = 1 + x + \cdots + x^{n-1}. $$ Then there exist positive integers $1 = n_0 \mid n_1 \mid \cdots \mid n_d = n$, not necessarily distinct, such that $$ A(x) = \frac{(x^{n_1} - 1)}{(x^{n_0} - 1)} \frac{(x^{n_3} - 1)}{(x^{n_2} - 1)} \cdots, \qquad B(x) = \frac{(x^{n_2} - 1)}{(x^{n_1} - 1)} \frac{(x^{n_4} - 1)}{(x^{n_3} - 1)} \cdots. $$

This implication of this conjecture is that, up to shift, $X$ is supported on the set of the form

$$ \{ (c_0 + c_2 n_2 + c_4 n_4 + \ldots) : c_k \in [\![n_{k+1}/n_k]\!] \} $$

and likewise $Y$ is supported on

$$ \{ (c_1 n_1 + c_3 n_3 + c_5 n_5 + \ldots) : c_k \in [\![n_{k+1}/n_k]\!] \}. $$

This may be regarded as the converse of the fact that, if $Z$ is sampled uniformly at random from the set $[\![n]\!]$ and $Z = \sum_{k\geq 0} C_k n_k$ with $C_k \in [\![n_{k+1}/n_k]\!]$, then $C_k$'s are independent.

Addendum - Proof of Lemma.

First, we note that both $X$ and $Y$ are bounded. Indeed, choose $x > 0$ so that $\mathbb{P}(|X| \leq x) > 0$ and note that

$$ \mathbb{P}(|Y| \geq y) = \frac{\mathbb{P}(|Y| \geq y, |X| \leq x)}{\mathbb{P}(|X| \leq x)} \leq \frac{\mathbb{P}(|X + Y| \geq y - x)}{\mathbb{P}(|X| \leq x)} $$

can be made to vanish if $y$ is chosen sufficiently large. This shows that $Y$ is bounded. A similar argument shows that $X$ is also bounded.

Next, choose the smallest interval $[x_0, x_1]$ so that $\mathbb{P}(X \in [x_0, x_1]) = 1$, and likewise, choose the smallest interval $[y_0, y_1]$ so that $\mathbb{P}(Y \in [y_0, y_1]) = 1$. Then $x_0 + y_0 = \min S$. Indeed,

  • If $x_0 + y_0 < s$, then write $s = x+y$ with $x > x_0$ and $y > y_0$. Then

    $$ 0 < \mathbb{P}(X \leq x, Y \leq y) \leq \mathbb{P}(X + Y \leq s) $$

    shows that $s \geq \min S$. Letting $s \downarrow x_0 + y_0$, this proves $x_0 + y_0 \geq \min S$.

  • If $x_0 + y_0 > s$, then $\mathcal{D} := \{(x, y) : x+y \leq s\} \cap ([x_0, x_1]\times[y_0, y_1]) = \varnothing$, and so,

    $$ \mathbb{P}(X+Y \leq s) = \mathbb{P}((X, Y) \in \mathcal{D}) = 0. $$

    This implies that $s < \min S$ and thus $x_0 + y_0 \leq \min S$.

Together with $\mathbb{P}(X+Y = \min S) > 0$, this implies $\mathbb{P}(X = x_0) > 0$ and $\mathbb{P}(Y = x_0) > 0$. From this,

$$ \mathbb{P}(X+y_0 \notin S) = \mathbb{P}(X+Y \notin S \mid Y = y_0) \leq \frac{\mathbb{P}(X+Y \notin S)}{\mathbb{P}(Y = y_0)} = 0 $$

and hence $\mathbb{P}(X+y_0 \in S) = 1$. A similar argument shows that $\mathbb{P}(Y+x_0 \in S) = 1$, and therefore the claim follows by setting $a = y_0$ and $b = x_0$. $\square$

$\endgroup$
  • $\begingroup$ Minor nitpick: your remark "In light of the lemma above, we may assume that both $X$ and $Y$ are supported on $[[n]]$" cannot be true. If $X$ and $Y$ have support on $\{0, ..., n-1 \}$, the sum $X + Y$ is supported on $\{0, ..., 2n - 2\}$. If the sum is only to have support on $\{0, ..., n-1\}$, then $X$ and $Y$ must be supported on strict subsets of $\{0, ..., n-1 \}$. I believe your proof allows for this anyway, but worth correcting. $\endgroup$ – bursneh Nov 14 at 0:24
  • $\begingroup$ @bursneh, Here, $X$ is supported on a set $S$ mean that the support of (the distribution of) $X$ is a subset of $S$. Please correct me if I am using the terminology incorrectly. $\endgroup$ – Sangchul Lee Nov 14 at 0:28
  • 1
    $\begingroup$ I believe we have different interpretations of the term "$X$ is supported on $S$". My definition when I first encountered the term was: "All the possible values of $x \in S$ have $P(X=x) > 0$", rather than just a subset. I guess this may just be a cultural difference. $\endgroup$ – bursneh Nov 14 at 0:53
  • 1
    $\begingroup$ I think this should be the accepted answer: I didn't check the lemma carefully, but the first section is correct and adds some useful details to the proof of Lemma 2.1(ii) in the Behrends' paper. $\endgroup$ – Mark Wildon Nov 14 at 19:05
6
$\begingroup$

As Lutz Mattner pointed out in his comment to another question, an affirmative answer is given in: Krasner and Ranulac (1937), Sur une propriété des polynomes de la division du cercle, C.R. Acad. Sci. Paris 204, 397–399 (which, unfortunately, does not seem to be available online, except for the Russian version due to D. Raikov). Connection to the other question was observed by @user44191.

$\endgroup$
4
$\begingroup$

(A rather trivial remark, but too long for a comment.)

Phrase it in a different language: two polynomials $P$ and $Q$ with non-negative coefficients have product equal to $$P(x) Q(x) = 1 + x + x^2 + \ldots + x^{n-1} = \frac{1 - x^n}{1 - x} .$$ What does it tell us about $P$ and $Q$?

Write $\sigma = e^{2 \pi i / n}$, so that $$ P(x) Q(x) = \prod_{k = 1}^{n - 1} (x - \sigma^k) .$$ Clearly, for some partition $\{1,2,\ldots,n-1\} = A \cup B$ and appropriate constants $a$ and $b$, we have $$ P(x) = a \prod_{k \in A} (x - \sigma^k) , \qquad b P(x) = \prod_{k \in B} (x - \sigma^k) . $$ For simplicity, let us require that $P(0) = Q(0) = 1$.

Since $P$ and $Q$ are real-valued, if $A$ contains $k$, it also contains $n - k$. Any such partition leads to a factorization $P(x) Q(x)$ where $P$ and $Q$ have real-valued (possibly negative) coefficients.

However, we require the coefficients of $P$ and $Q$ to be non-negative. Does this imply that the coefficients of $P$ and $Q$ are all $0$ and $1$?

$\endgroup$
  • $\begingroup$ The answer to your final question is 'yes', by Lemma 2.1(ii) in the Behrends' paper that Iosif Pinellis linked to above: ems-ph.org/journals/…. Therefore $X$ and $Y$ are uniformly distributed on their supports, as required. The Behrends' paper goes on to classify the possible support sets in Corollary 3.4. $\endgroup$ – Mark Wildon Nov 14 at 18:59
  • 1
    $\begingroup$ @MarkWildon: Actually, this is a much, much older result, as explained in the other answer, which I made CW, because it is essentially due to Lutz Mattner (in another thread). The above "answer" was just a preliminary comment, if you feel it is no longer relevant, I will be happy to delete it. $\endgroup$ – Mateusz Kwaśnicki Nov 14 at 20:04
  • $\begingroup$ I see: I had not noticed your second answer below when I wrote my comment. Up to you of course, but I see no reason to delete your first answer. $\endgroup$ – Mark Wildon Nov 14 at 20:37
2
$\begingroup$

Let $Z = X + Y$. I'll assume $n$ is an integer. More generally, I'll allow Z to take values in $S_Z = \{z_1, ..., z_n \}$. As $Z$ is uniform on $S_Z$, we know that

$$P(Z = z) = \frac{1}{n}$$

for any $z \in S_Z$.

Let $S_X, S_Y$ represent the supports of $X, Y$ respectively. Let $p_x = P(X = x)$ and $q_x = P(Y = x)$. As they are independent, we can therefore write $P(Z = z)$ as

$$ P(Z = z) = \sum_{x \in S} p_x q_{z-x} . $$

Therefore, we have the following set of consistency equations

$$ \sum_{x \in S} p_x q_{z-x} = \frac{1}{n} \tag{1}$$

for all $z$. We can solve this iteratively assuming a total order on the supports $S_X$ and $S_Y$. Let $x_{(i)}$ be the $i$th minimal element of $S_X$, $y_{(i)}$ be the $i$th minimal element of $S_Y$, and $z_{(i)}$ be the $i$th minimal element of $S_Z$. We must have that $x_{(1)} + y_{(1)} = z_{(1)}$, as the sum of the minima of both sets $S_X$ and $S_Y$ must map to the minimum of the support of $Z$, so by the consistency equations $(1)$, we obtain

$$p_{x_{(1)}}q_{y_{(1)}} = \frac{1}{n} .$$

If we require that the distributions of $X$ and $Y$ are uniform, i.e., $p_{x_{(1)}} = 1/|S_X|$ and $q_{y{(1)}} = 1/|S_Y|$, then we must have

$$ |S_X||S_Y| = n \tag{2} $$

and therefore uniformity can only hold if both $|S_X|$ and $|S_Y|$ divide $n$. Hence, the distributions of $X$ and $Y$ are not always uniform.

Another way to interpret equation $(2)$ is that the mapping $X + Y$ across the supports of $S_X$, $S_Y$ must map to a unique element in $\{1,...,n\}$. This is shown explicitly in the expanded cases below for $z_{(2)}, z_{(3)}$, and $z_{(4)}$ in equation $(1)$.

In fact, if the mapping does map to unique elements, then the consistency equations become

$$p_{x_{(i)}}q_{y_{(j)}} = \frac{1}{n}, \;\;\; i \in \{1, ..., |S_X|\}, \; j \in \{1, ..., |S_Y|\},$$

Summing over $i$ or $j$ respectively produces

$$p_{x_{(i)}}= \frac{1}{|S_X|} \;\;\; q_{y_{(j)}}= \frac{1}{|S_Y|}$$

where equation $(2)$ emerges from summing over both $i$ and $j$ and is used in the last equation. Therefore, the underlying probability distributions must be uniform in this case.


The rest of this answer covers later orders but produces the same result.

For the case $z = z_{(2)}$, we must consider both the minimal elements and the next-to-minimal elements of $S_X$ and $S_Y$. Let $x_{(2)}, y_{(2)}$ be the next-to-minimal elements of $S_X$ and $S_Y$ respectively. There are three possible cases here:

  1. $x_{(1)} + y_{(2)} = z_{(2)}$
  2. $x_{(2)} + y_{(1)} = z_{(2)}$
  3. $x_{(1)} + y_{(2)} = x_{(2)} + y_{(1)} = z_{(2)}$

Hence, for $z = z_{(2)}$ we get (for the 3 cases)

  1. $p_{x_{(1)}} q_{y_{(2)}} = \frac{1}{n}$
  2. $p_{x_{(2)}} q_{y_{(1)}} = \frac{1}{n}$
  3. $p_{x_{(1)}} q_{y_{(2)}} + p_{x_{(2)}} q_{y_{(1)}} = \frac{1}{n}$

Let us focus on cases 1 and 2. Consider $z = z_{(3)}$. In these cases, we must have that

  1. $x_{(2)} + y_{(1)} = z_{(3)}$
  2. $x_{(1)} + y_{(2)} = z_{(3)}$

as we can exclude the other cases by the requirements that $x_{(i)} < x_{(j)}$ if $i < j$ and similarly for $y_{(i)}$. These conditions are identical to the $z = z_{(2)}$ case but with $p$ and $q$ reversed.

For $z = z_{(4)}$, we must have $x_{(2)} + y_{(2)} = z_{(4)}$. We therefore obtain

$$p_{x_{(2)}}q_{y_{(2)}} = \frac{1}{n}$$

In cases 1 and 2, we end up with the same set of equations:

$$ p_{x_{(i)}}q_{y_{(j)}} = \frac{1}{n} $$

for $i,j \in \{1, 2\}$. This gives us the following conditions:

$$ p_{x_{(1)}} = p_{x_{(2)}}, \;\;\; q_{y_{(i)}} = \frac{1}{n p_{x_{(1)}}}, \;\;\; i \in \{1, 2\}$$

Let us now suppose that $X$ and $Y$ are uniformly distributed on their supports, so that $p_x = \frac{1}{|S_X|}$ and $q_y = \frac{1}{|S_Y|}$. These conditions require that

$$ |S_X| |S_Y| = n $$

which means that uniformity depends on whether the cardinality of the supports both divide $n$. Hence, the probability distributions for $X$ and $Y$ aren't necessarily always uniform for cases 1 and 2.

Let us now consider case 3. In case 3, we have $x_{(2)} + y_{(2)} = z_{(3)}$ instead, with the same equation as the $z = z_{(4)}$ for cases 1 and 2. Grouping together the conditions, we have

$$ p_{x_{(1)}}q_{y_{(1)}} = \frac{1}{n}, \;\;\; p_{x_{(1)}} q_{y_{(2)}} + p_{x_{(2)}} q_{y_{(1)}} = \frac{1}{n}, \;\;\; p_{x_{(2)}}q_{y_{(2)}} = \frac{1}{n} . $$

These have no real solutions. Therefore, the probability distributions cannot exist.

$\endgroup$
  • $\begingroup$ Sorry I edited my original comment - they are not meant to be iid; just independent. $\endgroup$ – Aaron Pereira Nov 12 at 21:15
  • $\begingroup$ Alright. I'll see what I can do for the more general case. $\endgroup$ – bursneh Nov 12 at 21:17
  • $\begingroup$ It looks like it may be open based on this other (equivalent) question... mathoverflow.net/questions/339137/… $\endgroup$ – Aaron Pereira Nov 12 at 21:54
  • $\begingroup$ I have updated the answer to the X and Y independent case, at least up to a finite order. $\endgroup$ – bursneh Nov 12 at 22:53
  • $\begingroup$ Further updated the answer to include a more general support for $Z$, $S_Z$, as the proof isn't specific to $S_Z = \{1, ..., n \}$ $\endgroup$ – bursneh Nov 13 at 11:09

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.