What is the conditional distribution of two discrete random variables, one not larger than the other?

Question

Let $X$ be a random variable, such that $X \sim Uniform(1,N)$. That is, $X$ can take values $1,2,3,...,N$, all with equal probability. Then let $Y$ be a random variable, such that $Y \sim Uniform(1,X)$. That is, $Y$ can take values $1,2,3,...,X$. What, then, is the conditional distribution of $X$ given $Y=1,2,3,...$?

I was thinking the following: Say $Y=1$. Then, there are $N$ possible values that $X$ could take where $1$ is in the probability space of $Y$. If $Y=2$, there are $N-1$ possible values that $X$ could take, as $X=1$ does not include this potential for $Y$. It is then possible to abstract this out to reach the following equation:

$P(X=x|Y=y) = \begin{cases}\frac{1}{N+1-y} & \text{if } 1 \leq x \leq y \leq N \\ 0 & \text{otherwise}\end{cases}$

I think I've come to the conclusion that this equation is flawed, but for the life of me I can't figure it out. Any advice would be helpful.

Answer 1

Use Bayes' Rule: $$\mathsf P(X=x\mid Y=y) = \dfrac{\mathsf P(Y=y\mid X=x)\mathsf P(X=x)}{\sum_{k=y}^N\mathsf P(Y=y\mid X=k)\mathsf P(X=k)}= \dfrac{1/x}{\sum_{k=y}^N 1/k}\mathbf 1_{1\leq y\leq x\leq N}$$

Answer 2

The question has already been answered by @GrahamKemp. However, I think it is worth adding that the distribution of $Y$ is given by $$ F_Y(y) = \frac{y}{n}(1+H_n-H_y), $$ where $H_k$ is the $k$th harmonic number.

To show this is true we use that $\mathbb P(Y=y) = \sum\limits_{x=1}^n \mathbb P(Y=y\mid X=x) P(X=x) = \sum\limits_{x=y}^n \dfrac{1}{x} \dfrac{1}{n}$.

Then, $\mathbb P(Y \le y) = \sum\limits_{y'=1}^{y} \sum\limits_{x=y'}^n \dfrac{1}{nx} = \sum\limits_{x=y}^{n} \sum\limits_{y'=y}^{x} \dfrac{1}{x} \dfrac{1}{n} = \sum\limits_{x=y}^{n} \dfrac{x-y+1}{nx}$. Then, applying the definition of harmonic numbers along with some mathematical manipulations concludes the proof.

---

Another interesting result is that if we let $Z_n = Y/n$, then $Z_n \xrightarrow d Z$ as $n \to \infty$ and the pdf $$f_Z(z) = \ln(1/z), \quad 0 < z < 1.$$