Sum of discrete non-uniform random variable and a Bernoulli is non-uniform

Question

Let $X$ be a non-uniform discrete random variable over $\{0,1,\dots,n\}$, and $Y$ be a Bernoulli random variable, not necessarily independent of $X$.

Is this information sufficient to conclude that $X + Y$ is non-uniform over $\{0,1,\dots,n+1\}$? If not, what would be a counter-example?

Edit: And what if $Y$ is independent of $X$?

Answer 1

Let $n=1$ and suppose $P(X=0)=1/3, P(X=1)=2/3$. Suppose $P(Y=0|X=0)=1$ and $P(Y=0|X=1)=1/2$. Then $X+Y$ is uniform on $\{0,1,2\}$.

Edit after comment: Let $X$ be uniformly distributed on the even numbers $\{0,2,4\}$ and let $Y$ be uniformly distributed on $\{0,1\}$, with $X$ and $Y$ independent. Note that $X$ is not uniformly distributed on $\{0,1,\dots, 4\}$, but that $X+Y$ is uniformly distributed on $\{0,1,2,3,4,5\}$.

Answer 2

Let $Z$ be uniform on $\{0,1,\ldots, n+1\}.$ Then let $Y$ be conditionally Bernoulli with $p$ a function of $Z.$ Say $p=1$ if $Z=n+1,$ otherwise (for simplicity), $p=0.$ Since it's binary, $Y$ is still unconditionally Bernoulli with overall probability $p=\frac{1}{n+2}.$

But $X=Z-Y$ is discretely distributed with support $\{1,\ldots, n\},$ and it is nonunform since we can see it has a somewhat higher probability of being $n$ then being $0,1,\ldots n-1.$

Answer 3

I'll find all solutions to the independent case. Let $P(X=i) = p_i$ and $P(Y=1) = r$. Then consider the probability generating functions of $X$ and $Y$. These are $f_X(z) = p_0 + p_1 z + p_2 z^2 + \cdots + p_n z^n$ and $f_Y(z) = (1-r) + rz$. Then the pgf of $Z = X + Y$ is

$$ f_Z(z) = f_X(z) f_Y(z) = (p_0 + p_1 z + \cdots + p_n z^n) ((1-r) + rz). $$

For $X + Y$ to be uniform this must be $(1 + z + \cdots + z^{n+1}) / (n+2)$. So we want to know: are there nonnegative real $p_0, p_1, \cdots, p_n, r$ such that, for all $z$,

$$ (p_0 + p_1 z + \cdots + p_n z^n) ((1-r) + rz) = {1 + z + \cdots + z^{n+1}\over {n+2}}. $$

Now $1 + z + \cdots + z^{n+1} = (1-z^{n+2})/(1-z)$, so it suffices to find $p_0, p_1, \ldots, p_n, r$ such that

$$ (p_0 + p_1 z + \cdots + p_n z^n) ((1-r) + rz) (1-z) = {1 - z^{n+2} \over (n+2)}$$

To be equal as polynomials, the two sides must have the same zeroes. The zeroes of the right-hand side are the $(n+2)$ roots of unity.

If $n$ is odd, then only one of these is real. But the left-hand side has at least two real roots, coming from the factors $((1-r) + rz)$ and $1-z$, so we have no solution.

If $n$ is even then the right-hand side has two real roots $z = \pm 1$. The right-hand side has the real root $z = 1$ coming from the factor $1-z$. If $r = 1/2$, it will also have the root $z = -1$ coming from the factor $(1-r) + rz = (1/2 + z/2)$. So any solution has $r = 1/2$.

Then we get

$$ (p_0 + p_1 z + \cdots + p_n z^n) = {1-z^{n+2} \over (n+2) (1-z)(1+z)/2} $$

or after some rearrangement

$$ (p_0 + p_1 z + \cdots + p_n z^n) = {2 \over n+2} {1-z^{n+2} \over 1-z^2}. $$

Doing the division on the right-hand side we get

$$ p_0 + p_1 z + \cdots + p_n z^n = {2 \over n+2} (1 + z^2 + z^4 + \cdots + z^n) $$

and so we conclude that $X$ must be uniform on $\{ 0, 2, 4, \ldots, n \}$.

So the only solutions when $X$ and $Y$ are independent have $X$ uniform on $\{ 0, 2, 4, \ldots, n \}$ for even $n$, and $Y$ uniform on $ \{0, 1\}$. If $n = 4$ this is the example that kimchi lover gave.