2
$\begingroup$

Suppose we have an array of $n$ integers. Suppose that we pick one of these elements uniformly at random and call it $x$. Suppose that $\log n$ elements are also sampled (uniformly at random) from the $n$-size array and we call $A$ this sampled array. What is the probability that $x$ lies in the middle third of the sorted version of the array $A$?

Initially I thought that this probability was $1/3$, but I think it's more complex than that. I believe that this probability should be $$ \text{Pr}[x \geq z]^{\frac{\log n}{3}}\cdot \text{Pr}[x \leq z]^{\frac{\log n}{3}},$$ where $z$ is an element sampled from the original size $n$ array. I don't know if this is correct or how to compute these probabilities.

$\endgroup$

1 Answer 1

1
$\begingroup$

$$ \def\P{{\mathbb P}} \def\E{{\mathbb E}} \def\I{{\mathbb I}} $$

The probability is approximately $\frac 13$. "Approximately" depends on $n$, your definition of "third" (i.e. what to do if $3$ doesn't divide $1 + \log n$), and on whether you sample without or with replacement (and in this case, how you handle multiple appearances of the same element). To give an extreme example, if $\log n = 0$, then the probability is either $0$ or $1$ depending on how you define "in the middle third".

Intuitively. Your process is equivalent to the following: sample $\log n + 1$ elements ($A$ and $x$), sort them, choose the random element among them, and ask what's the probability that its position is in the middle third. Clearly, the answer is approximately $1/3$ (the exact answer depends on the clarifications above).

Formally. Let's introduce the following notation: $A = (a_1, \ldots, a_k)$ and $a_0 = x$. I assume that $3$ divides $k+1$. I say that the element is in the middle third if the number of elements that are less than it is in range $[\frac{k+1}{3}, \frac{2k - 1}{3}]$. Let $C_i$ be an event that $a_i$ is in the middle third.

The problem asks about $\P[C_0]$. Since $a_0, \ldots, a_k$ are sampled from the same distribution, by symmetry we have $\P[C_0] = \cdots = \P[C_k]$. Let $C_i$ be the random variable denoting the number of elements less than $x$. Clearly, for any specific sample, exactly $\frac 13$ of $C_0, \ldots, C_k$ hold: namely, if $\I$ is the indicator function, then $\sum_{i=0}^k \I[C_i] = \frac{k+1}{3}$. Using $\P[C_i] = \E[\I[C_i]]$, we have: \begin{align*} \P_{a_0,\ldots,a_k}[C_0(a_0,\ldots,a_k)] &= \frac{1}{k+1}\sum_{i=0}^k \P_{a_0,\ldots,a_k}[C_i(a_0,\ldots,a_k)] \\ &= \frac{1}{k+1}\sum_{i=0}^k \E_{a_0,\ldots, a_k} \I[C_i(a_0,\ldots, a_k)] \\ &= \frac{1}{k+1} \E_{a_0,\ldots, a_k} \sum_{i=0}^k \I[C_i(a_0,\ldots, a_k)] \\ &= \frac{1}{k+1} \E_{a_0,\ldots, a_k} \frac{k+1}{3} \\ &= \frac 13 \end{align*}

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.