Computing the probability of this event Consider an array of natural numbers (including 0) $[x_1, x_2, \dots, x_n]$ of size $n$. Choose uniformly at random an element $x^*$ from this array. Also sample uniformly at random $\log_2 n$ elements from this array an call it $S$. What is the probability that $x^*$ lies in the middle third of the sorted version of the array $S$?
This is my attempt. Let $y_1, y_2, \dots, y_{\log_2 n}$ be the elements of $S$. Let $A$ be the event in which $x^*$ lies in the middle third of the sorted version of $S$. Suppose $n$ is a power of $2$ and $\log_2 n$ is divisible  by 3. Then,
\begin{align*}
\mathbb P(A) &= \mathbb P(x^* \geq y_1 \wedge x^* \geq y_2 \wedge \dots \wedge x^* \geq y_{\frac{\log_2 n}{3}} \wedge x^*\leq y_{\log_2 n} \wedge x^* \leq y_{\log_2 (n)-1}\wedge \dots \wedge x \leq y_{\frac{2\log_2 n}{3}}), 
\end{align*}
I think that here I could apply independence and get
$$ \mathbb P(A) = \mathbb P(x^* \geq y_1)^{\frac{\log_2 n}{3}} \cdot \mathbb P(x^* \leq y_n)^{\frac{\log_2 n}{3}}$$
Am I on the right track? What else can I do? Also how can consider the cases when $n$ is not a power of 2 and $\log_2 n$ is not divisible by 3?
 A: Not a full solution but maybe will lead you somewhere (too long for a comment). Assume that $\log_2 n = 3k$ is divisible by 3 and turn this into a counting problem. How many ways are there to choose the set $S$ that has $3k$ elements from $X = [1, 2, 3, \ldots, n]$ and one element $x^*$, also from $X$?
$${n \choose 3k} · n$$
How many ways are there to choose them so $x$ is in the middle third of $S$? To make things easier to imagine, assume that $k = 3$ and $n = 2^9 = 512$. We can split our problem into cases: counting positions where $x^*$ is 4th, 5th or 6th element of $S$ and (separately) positions where $x^*$ lies between 4th and 5th or between 5th and 6th element of $S$. And the answer will be
$$\sum_{m=k+1}^{2k} {x^* - 1 \choose m - 1} {3k-x^*\choose 3k-x^*} + \sum_{m=k+1}^{2k-1} {x^* - 1 \choose m} {3k-x^*\choose 3k-x^*}.$$
Instead of trying to find a closed-form solution, I turned above into a Python code:
def factorial(n):
    if n < 2:
        return 1
    return n*factorial(n-1)

def binomial(n, k):
    if n < 0 or k > n:
        return 0
    return factorial(n) // (factorial(k) * factorial(n-k))

def count(x_star, exponent):
    # assuming that 3 divides exponent
    n = 2 ** exponent
    successes = 0
    for x_star_position in range(1 + exponent // 3, 2 * exponent // 3 + 1):
        # for example, if exponent = 9, then x* can occur on 4th, 5th or 6th place of S
        # x* will occur on 4th place of S if
        # we choose 3 elements from [1, 2, ..., x*-1]
        # and 9-3-1 = 5 elements from [x*+1, ..., n]

        # x* will occur on 5th place of S if
        # we choose 4 elements from [1, 2, ..., x*-1]
        # and 9-4-1 = 4 elements from [x*+1, ..., n]
        
        # x* will occur on 6th place of S if
        # we choose 5 elements from [1, 2, ..., x*-1]
        # and 9-5-1 = 3 elements from [x*+1, ..., n]
        successes += binomial(x_star - 1, x_star_position - 1) * binomial(n - x_star, exponent - x_star_position)
    for x_star_position in range(1 + exponent // 3, 2 * exponent // 3):
        # for example, if exponent = 9, then
        # x* can occur between 4th and 5th place of S,
        # or between 5th and 6th place of S

        # x* will occur between 4th and 5th place of S
        # if we choose 4 elements from [1, 2, ..., x*-1]
        # and 9-4 = 5 elements from [x*+1, ..., n]

        # x* will occur between 5th and 6th place of S
        # if we choose 5 elements from [1, 2, ..., x*-1]
        # and 9-5 = 4 elements from [x*+1, ..., n]
        successes += binomial(x_star - 1, x_star_position) * binomial(n - x_star, exponent - x_star_position)
    return successes

import fractions

def count_all(k):
    log_2_n = 3 * k
    n = 2 ** log_2_n
    return(fractions.Fraction(sum([count(x_star, log_2_n) for x_star in range(1, n+1)]), binomial(n, log_2_n) * n))

Results (probability):
k n   p(x* in middle third of S)
1 8   1/8
2 64  9/56
3 512 259/1280
4 ... 769/3328
5 ... 32773/131072
6 ... 163843/622592

