Probability that $a$ and $b$ are in some subset of $\{0, \cdots, n-1\}$, where $a$ and $b$ are not independent? Let $X = \{0, \cdots, n-1\}$, and fix some $z \in X$. A subset $S \subseteq X$ of size $\alpha n$ for $0 < \alpha < 1$ is chosen. It's not clear how this subset is chosen, it may or may not be random. I then choose a number $a \in \{0, \cdots, n-1\}$ uniformly at random. I am trying to compute the probability that both $a$ and $b = z - a\ (\text{mod}\ n)$ are not in $S$.
It's clear that $P(a \not\in S) = 1 - \alpha$, but the events $a \not\in S$ and $b \not\in S$ are not independent; as soon as $a$ is chosen, $b$ is determined. To compute $P(a,b \not\in S)$, I can try to condition on the event $a \not\in S$, but that doesn't seem to help much since I don't know $P(b \not\in S | a \not\in S)$.
It seems like this scenario should be equivalent to first fixing $a$ and $b$, and then choosing a subset of size $\alpha n$ uniformly at random. The latter is easier to analyze by counting subsets, but I'm not sure how to prove formally that the two are equivalent.
Edit: It seems like this problem can't really be solved unless we know something about how $S$ is sampled (thanks @KennyWong). For my purposes all I need is a lower bound on this probability. I think the following might work:
Suppose $S \subseteq X$ and $|S| \leq \alpha|X|$ where $\alpha < \frac{1}{2}$. For each $a \in X$, there is a unique $b \in X$ for which $a + b = z\ \text{mod}\ n$, which is $b = z - a\ \text{mod}\ n$. I can extend $S$ by adding in all of these elements, $$S'= S \cup \{b \in X : z - b\ \text{mod}\ n \in S \}.$$
For each $a \in S$, we have exactly one $b = z - a\ \text{mod}\ n$ which may or may not be in $S$ already. This means that $|S'| \leq 2|S| \leq 2\alpha|X|$. For any $a \not\in S'$, $a \not\in S$ and $z - a\ \text{mod}\ n \not\in S$. Then the probability we're looking for is at most the proportion of elements outside of $|S'|$ which is at most $1 - 2\alpha$.
 A: Let me restate your question with a little different notation:

Suppose $M=\{0,1,\dots,n-1\}$ and let $S\subset M$ as well as $z\in M$. What is the probability of $$X\in S \text{ and }(z-X)\mod n\in S,$$ where $X$ is uniformly distributed over $M$ ?

Remark. Notice that it doesn't matter whether we take $\not\in S$ or $\in S$, because one problem can be transformed to the other by letting $\widetilde S$ be the complement of $S$ in $M$.
Answer, upper bound. The probability is by definition equal to the number of numbers $a\in M$ such that $a\in S$ and $(z-a)\mod n\in S$ divided by $n$. This happens at most $\lvert S\rvert$ times, so the probability is at most
$$\frac{|S|}n.$$ Equality is achieved for all sets $S$ of the type $S=T\cup (z-T)\mod n$ for any $T\subset M$.
Answer, lower bound. WLOG take $z=0$ (otherwise just "shift" the numbers $a$ that I am now considering by $z$).
Lemma. Let $n\geq 3$ be an odd integer and $S\subset\{1,2,\dots,n-1\}$. Then there are at least $2\lvert S\rvert-n+1$ numbers $a\in\{1,\dots,n-1\}$ such that $a\in S$ and $n-a\in S$.
Proof. I will proceed by induction. The start $n=3$ can be checked manually. Now let the statement be true for some odd $n-2\geq3$. Then take a $S\subset\{1,2,\dots,n-1\}$. If there is no $a$ with the desired property, then the pigeonhole principle implies $\lvert S\rvert\le\frac{n-1}2$ so there is nothing to prove. If there is such an $a$, then by considering the set $\widetilde S$ that you get by "removing" $a$ and $n-a$ from $S$ (and by subtracting $1$ from each number in $S$ larger than $\min(a,n-a)$ and $2$ from each number in $S$ larger than $\max(a,n-a)$, for instance $S=\{1,2,3,6\}\subset\{1,2,3,4,5,6\}$ turns into $\widetilde S=\{2-1,3-1\}\subset\{1,2,3,4\}$), you get a problem of size $n-2$. By the induction hypothesis, we thus have that the number of desired $a$ is greater or equal than $$2+2(\underbrace{\lvert S\rvert -2}_{\lvert\widetilde S\rvert})-(n-2)+1=2\lvert S\rvert-n+1.\ \square $$
This result implies that there are at least $2\lvert S\rvert -n$ such $a$ if you take $\{0,1,\dots,n-1\}$ everywhere in the above Lemma instead of $\{1,2,\dots,n-1\}$.
Hence, the probability for odd $n$ is at least $2\frac{\lvert S\rvert}n-1$. I think that you can get the same bound (or a slightly worse bound like $2\frac{\lvert S\rvert-1}n-1$) for even $n$.
Indeed this gives your desired result: If we pass to complements (i.e. take $\not\in S$ instead of $\in S$) and set $\alpha\overset{\text{Def.}}=\frac{\lvert S\rvert}n$, then the lower bound of the transformed problem is $$\frac{2(n-\lvert S\rvert)}n-1=1-2\alpha.$$
