8
$\begingroup$

Let us consider

$$Z = X_1 + X_1 X_2 + X_1 X_2 X_3 + \cdots.$$

Here the $X_i$'s can only take on two different values: either $X_i=a$ or $X_i=b$, with $0 < a < b < 1$ and $a+b = 1$. The $n$-th digit of $Z$ is said to be equal to one if $X_n = b$, and to zero if $X_n =a$. All real numbers in $[\frac{a}{1-a}, \frac{b}{1-b}]$ can be uniquely represented in this form (uniquely is to be understood in the same sense that the traditional binary representation of a number is "unique".)

A simple algorithm can be used to compute the digits of $Z$. See below its coded version (in Perl). Note that $a, b$ are represented by $alpha, $beta in the program. The variable $sum is used to double check that the computations were successful, and give you some idea of how many digits can be accurately computed: it converges to $Z$, and represents the successive approximations of $Z$ using an increasing number of terms in the formula at the very beginning of this article.

open(OUT,">att.txt");  

$beta=sqrt(2)/2;   
$alpha=1-$beta;

$min=$alpha/(1-$alpha);
$max=$beta/(1-$beta);

$z=log(2);  

$prod=1;
$upper=$beta/(1-$alpha);
$lower=$alpha/(1-$beta);

if ($z > $upper) { 
  $sum=$beta;
  $digit=1;
} else {
  $sum=$alpha;
  $digit=0;
}
$prod=$sum;
print OUT "z = $z (b = $beta | min = $min | max = $max)\n";
print OUT "$digit\n";

for ($k=0; $k<60; $k++) {

  $upper = $sum+ $prod *$beta/(1-$alpha);  
  $lower = $sum+ $prod *$alpha/(1-$beta);

  if ($lower  < $z) {
    $prod = $prod * $beta;
    $digit=1;
  } else { 
    $prod=$prod * $alpha;
    $digit=0;
  }
  $sum+=$prod;
  print OUT "$digit\n";  
}
print OUT "sum = $sum\n";
close(OUT);

My Question:

Is there a simple expression or recursion that maps the digit of $Z$ in base two, to its digits in the system discussed here? Of course there is a one-to-one mapping: if you know the digits in one system, then compute $Z$, then compute the digits back into the other system. But I am looking at something smarter than that, also hoping to find patterns between the two representations (digits) of a number $Z$ in both systems.

Fun facts

In the case $a=-0.5, b=0.5$ (not covered here) the one-to-one mapping between the two digit systems (mine versus standard binary) is described in section 5 in this article.

Also, if you pick up a number at random in $[\frac{a}{1-a}, \frac{b}{1-b}]$, then in my system, the proportion of digits equal to 1, is $b$. By contrast, in the standard binary system, that proportion is 50%. In both systems, successive digits are not auto-correlated (true for the immense majority of numbers, called normal numbers.)

Finally, consider the $X_i$'s as independent random variables with distribution $P(X_i = b) = b, P(X_i = a) =a$. Remember that $a+b =1$ and $0< a < b < 1$. Then $Z$ has a uniform distribution on $[\frac{a}{1-a}, \frac{b}{1-b}]$. If $a+b < 1$, then the support domain for $Z$ is full of wholes, and $Z$'s distribution is nowhere differentiable; it does not have a density. Yet it has a distribution and you can compute all its moments. See here for more on this topic. The case $P(X_i = b) = p,P(X_i = a) = 1-p$, with $p \neq b$ can also lead to a very wild distribution for $Z$. See chart below, picturing the empirical percentile distribution of $Z$, if $a=0.4, b=0.6, p =0.8$. It corresponds to a no-where differentiable distribution. If instead $p=0.6$, the curve becomes a straight line, corresponding to a uniform distribution.

enter image description here

Potential application

You can encode a message using the new numeration system proposed here. However, if you use (say) $b=0.6$, it will be very obvious to the hacker that you used $0.6$ since about 60% of the digits will be equal to one. The hacker will then easily decode your message. But you could pepper the encoded message with a number of digits equal to zero, at specific locations, to reduce the proportion of digits equal to one, from 60% to 50%. Then the hacker won't know which $b$ you used, and won't be able to easily decrypt your message. You need to make sure that when adding zero's, you do it in such a way that the correlation between successive digits remains equal to zero.

I am also curious to see what happens when $b\rightarrow 0.5$ or $b\rightarrow 1$. I also plan on investigating the case $b=3/4$, or more generally, $b$ a rational number, in more details, and I will provide an update if I find something interesting.

$\endgroup$
3
  • $\begingroup$ I will publish a version of my program based on high precision arithmetic, so that you can correctly compute far more than 60 digits. $\endgroup$ – Vincent Granville Dec 16 '19 at 5:23
  • $\begingroup$ What do you mean when you say that uniquely is to be understood in the same sense that the traditional binary representation of a number is "unique".? $0.11111...=1.00000...=1$ in binary $\endgroup$ – Angela Pretorius Dec 20 '19 at 8:31
  • 1
    $\begingroup$ @Angela: I mean unique up to the fact that (in standard base 2) $0.11111\cdots = 1.0000\cdots$. We have the same kind of thing going on here in this new system. Of course if you use my algorithm to compute the digits, then digits are uniquely defined. $\endgroup$ – Vincent Granville Dec 20 '19 at 14:12

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.