# Probability of this random selection

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.

$$\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*}