Finding one of 2/3 of all array elements in constant expected time

Question

How do I go about designing a constant time algorithm which satisfies the following I/O requirements:

Input: an array $A$ of length $3n$, containing $2n$ values of the symbol $X$ and $n$ of the symbol $Y$

Output: a number $i$, such that $A[i]=X$

It is clear that the naive linear scan approach is $O(n)$. Is there any good algorithm, potentially randomized, that has a constant number of expected operations $O(1)$?

Answer 1

Use rejection sampling:

do {
   i = uniform_random(0..3*n-1)
} while A[i] != X
return i

Whenever this terminates, it clearly outputs a correct $i$.

If the probability of $A[i] = X$ is $p \in (0,1]$, then the expected number of iterations is $\frac{1}{p}$ (geometric distribution). Filling in the details is an instructive exercise.

Answer 2

One approach would be to randomly pick a large constant $k$ indices and test them. The exact probability of at least one of them being $A[i] = X$ would be:

$$\begin{align} P(\text{at least }1\; X) &= 1 - P(\text{all are } Y)\\ & = 1 - \left(\frac{n/3}{n}\cdot \frac{n/3-1}{n-1}\cdot \ldots \cdot \frac{n/3 - (k-1)}{n - (k-1)}\right)\\[0.5em] & \geq 1 - 3^{-k} \end{align}$$ This inequality holds as $n$ approaches $\infty$ for some constant $k$ because: $$\lim_{n\to\infty} \frac{n/3 - k}{n - k} = \frac{1}{3}$$ Even for some small $k$ like 10, the probability of finding an index $i$ such that $A[i] = X$ is: $$\begin{align} P(\text{at least }1\; X) &\geq 1 - 3^{-10}\\ & \geq 0.99998 \end{align}$$

Answer 3

Consider $ALG$:

Pick an index $i$ at uniformly random.

If $A[i]=X$ then return $i$ else return $FAIL$

We see that $Pr[SUCCESS] = \frac{2}{3}$ i.e., $Pr[FAIL] = \frac{1}{3}$ in a single run.

Suppose we want to boost the success of finding at least one $i$ so that $A[i]=X$ to a probability of $\geq 1-\delta$

We can do so by repeating $ALG$ independently upto a sufficient number of times. This repeated algorithm fails only if all the runs return $FAIL$ otherwise we return the first run that produces an $i$ and break there.

Suppose we conduct $k$ runs, the event that this repeated version of $ALG$, namely $ALG_k$, fails is if each of the runs return $FAIL$. Thus,

$Pr[ALG_k\ fails] = \frac{1}{3} \cdot \frac{1}{3} \cdots\frac{1}{3} = \frac{1}{3^k}$ i.e., $Pr[ALG_k\ Succeeds] = 1 - \frac{1}{3^k} \geq 1 - \delta$

where the last inequality comes from our requirement on the probability of success and thus leads to the following bound on k:

$\frac{1}{3^k} \leq \delta \implies k \geq \lceil log_3(\frac{1}{\delta})\rceil$

For instance, if we want the Algorithm to find an $i$ (i.e., succeed) with probability at least $0.99999$, then our $\delta = 10^{-5}$ giving a lower bound of $\lceil log_3(10^5) \rceil = 11$. In other words, $11$ independent runs of $ALG$ ensures success with at least probability of $0.99999$

Here's the pseudocode:

(Note: $\delta$ is a parameter that is fixed and independent of $n$)

$FINDINDEX(A,\delta):\\ k \leftarrow \lceil log_3(\frac{1}{\delta})\rceil \\ N \leftarrow A.length \\ \textbf{for}\ j=1\ \textbf{to}\ k\ \textbf{do}\\ \ \ \ \ i \leftarrow RANDOM(N) \\ \ \ \ \ \textbf{if}\ A[i]=X\ \textbf{then}\\ \ \ \ \ \ \ \ \ \textbf{return}\ i\\ \textbf{return}\ NULL $

In the above, $RANDOM(N)$ is assumed to be a function that returns an integer picked uniformly at random from $1$ to $N$