2
$\begingroup$

Let $s$ be an unknown bit string of length $n$. Let $p(i, b)$ be the probability that $i$-th bit of $s$ is equal to $b \in \{0,1\}$. What's the fastest method to find $s$, given the distribution $p()$? "Fastest" meaning using the least (in the expected value sense) number of queries to an oracle $O(x)$, such that $O(x)=1$ iff $x=SECRET$.

I'm interested in all observations about this problem, not only the optimal solution.

  • 0
    Does $p(i,b) = p(j,b)$ for all $i$ and $j$? Are the events "$i$-th bit of $s$ is $1$" and "$j$-th bit of $s$ is $1$" independent for all $i \neq j$?2012-06-27
  • 0
    @DilipSarwate: The first equation does not hold (p can be anything). Events are independent. I think it's sufficient to start looking from the most probable bitstring to the least probable one, but I don't know how to show that.2012-06-27
  • 0
    @zxcv: The optimal search pattern is _always_ in descending order of probability; the challenge is in finding an algorithm to enumerate the strings in this order. If the bits are independent, you may want to look at enumerating the strings in descending order of the log-likelihood $\lambda(s) = \log p(s) = \log \prod_{i=1}^n p(i,s_i) = \sum_{i=1}^n \log p(i,s_i)$, which is a linear map from $\{0,1\}^n$ to $\mathbb R^- \cup \{-\infty\}$; by the monotonicity of the logarithm, $p(a) < p(b)$ iff $\lambda(a) < \lambda(b)$.2012-06-27

1 Answers 1

2

Since the metric is the number of queries to the oracle, how the words are represented doesn't matter so we can simply say that the secrets are words $w_1,\dots,w_n$, with probability $p_1\ge\dots\ge p_n$ (satisfying $\sum_i p_i=1$).

Now the probability of success of any algorithm after $k$ queries to the oracle is at most $\sum_{i=1}^k p_i$. Since the algorithm that simply queries $w_1,\dots,w_n$ in that order achieves this upper bound, that algorithm is optimal in every reasonable sense of the word (in particular, it has minimum expected number of queries, median number of queries, and so on).

So now, back to the original problem: to generate $w_1,\dots,w_n$ with decreasing probability, let's assume (up to flipping and sorting of the bits) that $p(i,0)\ge p(i,1)$, and $p(1,0)\ge p(2,0)\ge\dots\ge p(n,0)$.

Initially, let the candidate set be $\{0^n\}$. Then, generate a new word by selecting the most probable word $w$ from the candidate set (and removing it), and update the candidate set by adding all words $w'$ equal to $w$ except for one bit that is changed from 0 to 1. There are at most $np$ words in the candidate set (where $p$ is the number of words already generated) and computing the probability of a given word is $O(n)$, so the algorithm is polynomial in the number of requests to the oracle (and in $n$).

  • 0
    By "secrets are words ..." do you mean $P(w_i = SECRET) = p_i$?2012-06-27
  • 0
    Exactly. Here "word" is synonymous with "bit string", since the alphabet is $\{0,1\}$.2012-06-27
  • 0
    There's only one secret, so "secrets" is a bit misleading.2012-06-27
  • 0
    How much does the skewed distribution help? For example, what's the expected number of queries for $p(.,.)$ such that $p(i,0)=1-\epsilon$ for all $i$?2012-06-27
  • 0
    Oh. I meant, the space of all possible secrets (in all possible instances of the problem), which is a subset of the space of words $\{0,1\}^*$. At that point I was just looking at the formulation of the problem, not fixing a particular instance of it.2012-06-27
  • 0
    If $p(i,0)=1-\varepsilon$, then $$\mathsf E[X]=1 + n\varepsilon(n+1)/2 + O(\varepsilon^2)$$2012-06-27
  • 0
    can you explain the EX?2012-06-27
  • 0
    In the $w_1,\dots,w_n$ framework, we have $p_1=(1-\varepsilon)^n$, $p_2=\dots=p_{n+1}=\varepsilon(1-\varepsilon)^{n-1}$, and $p_k=O(\varepsilon^2)$ for $k>n+1$. Since the expected number of tries $X$ is $$\mathsf E[X] = \sum_{i=1}^n i p_i$$ a calculation leads to the above expression.2012-06-27
  • 0
    Also, the algorithm isn't polynomial in n -- worst case number of queries is always $2^n$.2012-06-27
  • 0
    It's not polynomial in just $n$, it's polynomial in $p$ and $n$ where $p$ is the number of queries to the algorithm. See [output-sensitive algorithm](http://en.wikipedia.org/wiki/Output-sensitive_algorithm)2012-06-27
  • 0
    oh, I see. One more question: in the calculation of EX, why is the upper bound of the sum $n$? Shouldn't it be $2^n$? Or does $i>n$ terms vanish?2012-06-27
  • 0
    Good remark, there is actually a clash between the two notations, as I used $n$ for the number of words in $w_1,\dots,w_n$. Of course the sum should go up to $N=2^n$, the number of words. And the terms never vanish, since $\epsilon\ne 0$.2012-06-27
  • 0
    Note that $O_\varepsilon(\varepsilon^2)$ is only valid for fixed $n$ and variable $\varepsilon$, so you can't deduce an asymptotic bound as $n$ varies. If you want to do that, then you can use $O_{n,\varepsilon}(2^n n^2\varepsilon^2)$, which comes from the fact that the probability that $X>n+1$ is $O_{n,\varepsilon}(n^2\varepsilon^2)$ and that $X$ is at most $2^n$.2012-06-27
  • 0
    so the $O(\epsilon^2)$ term in $E[X]=1+n\epsilon (n+1)/2 + O(\epsilon^2)$ "hides" the fixed $2^n$? Thanks for a detailed answer, I accepted it :)2012-06-27
  • 0
    Exactly. Don't forget to upvote when accepting :)2012-06-27