0
$\begingroup$

I have the following problem :

I generate n-bits long binaries (0|1), where every bit is 0 OR 1 with probability 50%. So, say I generate 'm' such binaries.

The question is what is the probability when generating the next one that it will be still ~50% away (by hamming distance) from all the generated vectors i.e. almost orthogonal.

OR

said differently, how many binaries I can generate before I generate one that is closer than ~50% away.

Normally if 'n' is big it is almost guaranteed the binary vector is orthogonal to all previously generated. I want to find the threshold 'm' of number of vectors I can safely generate for defined 'n'.

I have hard time coming up with formulation on solution to the problem. So even if you don't have a solution, but just idea on how to mathematically formulate the problem, please comment out.


I was thinking along the lines of single bit logical operations (match i.e. XOR) extended somehow over multiple n-bits. Then probabilistically treating m-count of vectors in pairs... via at-least one match ..

$\endgroup$
  • $\begingroup$ I'd start by going at it numerically (which isn't difficult at all for this, even for arbitrary n and m), then see what kind of patterns emerge, and then try to construct a model for this. Then again, I'm a physicist, not a mathematician. $\endgroup$ – Nominal Animal May 23 '18 at 20:20
  • $\begingroup$ thats what i'm doing ... programing it... but i want to get definite answer $\endgroup$ – sten May 23 '18 at 20:39
  • $\begingroup$ Do you have any mathematical model yet, then? $\endgroup$ – Nominal Animal May 23 '18 at 20:41
1
$\begingroup$

If you have $N$ uniform random $k$-bit numbers, between $0$ and $2^k-1$, inclusive, the probability of at least two of them being the same is $$P(n, k) = 1 - \frac{n! {2^k \choose n}}{2^{k n}} = 1 - \frac{(2^k)!}{(2^k - n)! 2^{k n}} \tag{1}\label{NA1}$$ because this is essentially the well-known birthday problem but with $2^k$ "days". You are looking for the smallest $n$ where $P(n, k) \ge 0.5$.

Some tabulated values of smallest $n$ that fulfills $P(n, k) \ge 0.5$: $$\begin{array}{l|r} k & n \\ \hline 4 & 5 \\ 8 & 20 \\ 12 & 76 \\ 16 & 302 \\ 20 & 1206 \\ 24 & 4823 \\ 28 & 19291 \\ 32 & 77164 \\ \end{array}$$ To calculate $P(n, k)$ for larger values of $k$, you'll need to approximate $\eqref{NA1}$ somehow, perhaps starting with $P(n, k) = 0.5$ or $2 P(n, k) - 1 = 0$.


It turns out there is a very simple approximation: $$P(n, k) = 1 - e^\frac{-n(n-1)}{2^{k+1}}$$ I encountered it here.

At the limit $P(n, k) = 0.5$, with large enough $k$, say $k \ge 16$, we can approximate $$n \approx 0.833 \times 2^\frac{k+1}{2}$$

$\endgroup$
  • $\begingroup$ thanks, but something looks off because I get approx match (i.e. less than 42% away) around ~500 generated items with 100bit binary vectors ! $\endgroup$ – sten May 24 '18 at 15:50
  • $\begingroup$ @user1019129: So? You could be using a poor PRNG, like the standard C rand(), which is a pretty poor LCG; if you used that, your numbers will not be uniformly random. Also, $P(n,k)$ is a probability, not any kind of quarantee. $\endgroup$ – Nominal Animal May 24 '18 at 17:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.