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

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)$$?

• Design a probabilistic algorithm in constant time? return random(0, 3n). Probability = 2/3. What are the constraints on the probability? If it is required to be correct, then constant time might not be possible. Clarification on this probability would be helpful. Also, look into Las Vegas algorithms and Monte Carlo algorithms. Specifically this section: en.wikipedia.org/wiki/…
– ryan
Nov 12 '17 at 6:28
• @ryan Probabilistic algorithms are usually not always correct. Indeed, if they are always correct then we can arbitrarily choose the random bits and make them deterministic. We are usually interested either in an algorithm succeeding with high probability, or (as in this case) in an algorithm succeeding with constant probability. The constant doesn't really matter since we can always boost it by repeating the algorithm enough times. Nov 12 '17 at 11:40
• @Lola1984, what you could do is analyze the expected time of linear scan using combinatorics. For every combination possible of the $3n$ elements, what is the expected location of the first $A[i] = X$. Start with finding all probabilities $P(A[i] = \text{ first } X) = P(A[0 \ldots i-1] = Y \land A[i] = X)$. This shouldn't be too difficult for all $i \in [0, n/3]$. Then use these probabilities to find the expected value of the first $X$.
– ryan
Nov 13 '17 at 23:23

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.

• @Lola1984 Calculate the probability for the loop to execute $k$ iterations. Note the form of the probability weights, or use the definition of the expected value. (I won't do the details for you since I'm fairly certain this is homework of some kind, and I've helped you enough.)
– Raphael
Nov 14 '17 at 6:26

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}

• how did you get deduce 3^-k from the equation? Nov 13 '17 at 17:58
• @nomanpouigt, $$\frac{n/3}{n} \cdot \frac{n/3 - 1}{n - 1} \cdot \ldots \cdot \frac{n/3 - (k-1)}{n - (k-1)} \leq \frac{1}{3^k}$$
– ryan
Nov 13 '17 at 18:06
• sorry can't understand decipher your response. Would you mind updating the answer with the details? Nov 13 '17 at 18:08
• @nomanpouigt, take $n = 9$ and $k = 3$. Then you have: $$\frac{3}{9}\cdot \frac{2}{8}\cdot \frac{1}{7} \leq \frac{1}{27}$$ Therefore $1$ minus that will be greater than $1$ minus $1/3^k$: $$1 - \frac{1}{84} \geq 1 - \frac{1}{27}$$
– ryan
Nov 13 '17 at 18:11
• So basically if I just pick a number at random until I reach A[i]=X, that will work because of the above? I am not, however sure as to how the expected number of operations in this case would be constant. Nov 13 '17 at 23:04

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$

• Thanks! so would my algorithm basically be something like WHILE (A[i]!= X) return (random number in this array)? I kind of figured that out, however Im having trouble still proving how this would be O(1), since previously we were taught to kind of prove it using geometric sequences, which at the end summed to some constant... Nov 13 '17 at 4:04
• @Lola1984 having it in a while (A[i] != X) loop would not guarantee $O(1)$ worst-case, but should guarantee $O(1)$ expected. You would still need to go through and prove it.
– ryan
Nov 13 '17 at 4:38
• @Lola1984 This is a ripe opportunity to distinguish types of randomised algorithms: I have described a Monte Carlo Algorithm while you have converted it into a Las Vegas Algorithm. While the former type(the one i describe) can fail(i.e., incorrectly return null) with some probability, its running time is deterministic and in this case, independent of the input size $n$. Contrast this to your formulation which guarantees success but has probabilistic running time. Hope this helps. Nov 13 '17 at 4:59
• Thanks for the clarification, I am not really familiar with either of these methods or their differences. My algorithm should have an Expected O(1), So does this mean that its correct? I am having trouble proving it, however, is there a proof you know of that I could use an example? Thanks again! Nov 13 '17 at 5:30
• @Lola1984 I've added the pseudocode for the algorithm that i've described and analysed. If you are happy with my answer consider upvoting and accepting it. Thanks. Nov 13 '17 at 8:18