Bounds on the expected position of an item in $n$ IID multinoulli experiments over $n$ categories, given that all categories are observed

26 Views Asked by At

Let $n\in\mathbb Z_{>0}$ be the number of categories and the number of trials. Using $[n]=\{1,\dots,n\}$, let $X=(X_1,\dots,X_n)\in[n]^n$ be given by iid coordinates, and let $p_x=P(X_1=x)$. Further, let $\mathcal D=\{x\in[n]^n:\{x_i:i\in[n]\}=[n]\}$ be the pairwise distinct outcomes (permutations) and let $Y\in[n]^n$ be given by $P(Y=x)=P(X=x|X\in\mathcal D)$, i.e. we draw without replacement. For $i\in[n]$ let $T_i=\min\{t\in[n]:Y_t=i\}$ be the position of $i$ in $Y$.

In this answer it was shown that $\mathbb E[T_i]\le\frac{1}{p_i}$, and that there exists an absolute constant $\alpha>0$ such that $\mathbb E[T_i]\ge\frac{\alpha}{p_i}$ if $\min_jp_j\ge\frac{1}{2n}$.

QUESTION: Let $c\le 1$. Does there exist a constant $\alpha=\alpha(c)$ such that $\mathbb E[T_i]\ge\frac{\alpha}{p_i}$ for all $i\in[n]$, $n\in\mathbb Z_{>0}$ and $(p_i)_i$ whenever $\min_ip_i\ge\frac{c}{n}$?