1
$\begingroup$

Let's define a binary string random variable of length $n$, i.e., $X\in \left\{0,1\right\}^n$. Let us define $D$ as the random variable obtained as the Hamming distance between two samples of $X$ $x_1$, $x_2$, i.e. $d = \mathrm{d}_{\mathcal{H}}\left(x_1,x_2\right)$, where $x_1 \sim X$, $x_2 \sim X$.

My question is: How to compute the entropy of $X$ if $D$ follows a beta-binomial distribution with known parameters $\alpha = \beta$? For instance, $n = 127$, $\alpha = \beta = 6$.

This question concerns distances between binary strings where there exist correlations among the different bits in the string. I tried to find stochastic processes that can fit this definition, but I didn't manage to get any useful insight so far.

In the following example, there is a set of 15 randomly generated binary strings. They are generated as: $$X = \frac{\mathrm{sign}\left(A\mathbf{x}\right) + 1}{2}$$, where $\mathbf{x} = [x_1,\ldots,x_5]$, $x_i \sim \mathcal{N}(0,1)$, and $A = \left(a_{ij}\right)$, $1\le i \le 15$, $1 \le j \le 5$, and $a_{ij}$ are sampled from a $\mathcal{N}\left(0,1\right)$. In this toy experiment, I generated 15000 binary vectors, and I analyzed their entropy, Hamming distances distribution, the $\beta$-binomial distribution fit to the Hamming distance. The entropy in one realization of the experiment is $H = 7.90 \textrm{ bits}$, the parameters of the $\beta$-binomial distribution are: $\alpha = 2.82$, $\beta = 2.81$, and of course $n = 15$, the length of the binary strings.

I attached a plot Histogram of Hamming distances, binomial and $\beta$-binomial fits showing the histograms. It can be seen that the $\beta$-binomial distribution provides an excellent fit.

$\endgroup$
  • $\begingroup$ Thank you for your suggestion. I will try some empirical evaluations (I will create some artificial binary string variables with correlated bits) that may help to provide some insight. However, I am interested in a general answer, beyond empirical trials. $\endgroup$ – eargones Jun 21 '18 at 13:17

Your Answer

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

Browse other questions tagged or ask your own question.