2
$\begingroup$

Consider the function $f: \{0,1\}^n\rightarrow \{0,1\}^{2n}$

I want to count all the functions that have one entry where its first n bits are equal with the last n bits.

Assume we target entry number 10 and g is one of those functions that have the aforementioned property: $m=\{0,1\}^n;g(10)=m||m$

The total number of functions assuming $2^n$ rows where each row has $2n$ bits is $2^{{2^n}2n}$

I would say, if we want a specific entry of the function to have that structure we can first count the rest of the rows of the function which have: $(2^{n}-1)*2n$ bits and then since we want the first n bits to be equal with the last to the entry that we didn't take into account, we add another n bits, so total for each function: $(2^{n}-1)*2n+n$.

Total functions: $2^{(2^{n}-1)*2n+n}$

So the probability: $\frac{2^{(2^{n}-1)*2n+n}}{2^{2^n*2n}}=\frac{1}{2^n}$

Do i have it right? Is there an easier way to think about it? The result is to trivial to require that amount of effort.

Edit (added some more details):

One example (for $n=2$):

$F: \{0,1\}^2 \rightarrow \{0,1\}^{4}$ and I want to count all functions that have a specific entry, e.g 00, with a specific structure(first n bits equal with the last n bits). $F(00)=\{0000, 1010, 0101, 1111\}$ in this case

Entry 00| 0000

Entry 01| 0100

Entry 10| 0001

Entry 11| 0100

For example here $F(00)=0000$ and since $00=00$, this function should be counted


Entry 00| 0001

Entry 01| 0000

Entry 10| 0000

Entry 11| 0000

In this function since $F(00)=0001$ and $00\neq 01$, it should not be counted

$\endgroup$
  • $\begingroup$ What do you mean by a row? A row in the value table of the function? Shouldn't you have $2^{2n}$ for $\{0,1\}^n \times \{0,1\}^n$ inputs? $\endgroup$ – Elias Apr 26 '17 at 15:30
  • $\begingroup$ Visualizing the function as a table with $2^n$ rows where each row has $2n$ bits since the output of the function is $2n$ $\endgroup$ – Antonis Paragas Apr 26 '17 at 16:34
  • $\begingroup$ But don't you need as many rows as you have possible inputs which is $2^{2n}$? $\endgroup$ – Elias Apr 26 '17 at 19:25
  • $\begingroup$ Other issues, what on earth does "entry" mean? Input? Input coordinate? This is with respect to your example. $\endgroup$ – kodlu Apr 26 '17 at 21:39
  • $\begingroup$ @Elias: Does the fact that has key change the total number of possible functions? I am not sure, I would say if we line up the functions, the key would just change their order. kodlu: with entry i mean the row inside the function, for example: f(10) is the 10th entry/row $\endgroup$ – Antonis Paragas Apr 27 '17 at 9:18
2
$\begingroup$

If you want the function to have the property for one input, say $x$, which is fixed ahead of time, you just focus on that output vector $$ f(x)=f(x_1,\ldots,x_n)=(z_1,\ldots,z_{2n}) $$ and the condition $z_i=z_{i+n}$ holds with probability

$$P(given ~row ~is ~good)=\frac{2^{n}}{2^{2n}}=2^{-n},$$ since in this case you don't care what is happening in the other rows.

If you want this property to hold only for your selected input, this happens with probability

$$P(given~ row ~is ~good) (1-P(given ~row ~is ~good))^{2^n-1}=2^{-n}[1-2^{-n}]^{2^{n}-1}$$ which can be estimated for large $n$ from above and below by using $$ 1-k\varepsilon+\frac{k(k-1)}{2}<[1-\varepsilon]^k<1-k\varepsilon $$ where $\varepsilon$ is small and positive.

$\endgroup$
  • $\begingroup$ I have probably messed up the function definition, i am creating a new question about that. What i want is, assuming we have all the functions: $f(x)=(x_1,x_2,....,x_{2\cdot n})$. How many functions have $f(10)=(x_1,x_2,...,x_n, x_1, x_2, ..., x_n)$ $\endgroup$ – Antonis Paragas Apr 29 '17 at 9:10
  • $\begingroup$ You need to improve your notation. You are mixing the general with the specific. Do you mean all functions $f:\{0,1\}^{2}\rightarrow \{0,1\}^{2n}$? If not why the $f(10)$ above is confusing since it would have $n=2.$ $\endgroup$ – kodlu Apr 29 '17 at 23:21
  • $\begingroup$ Indeed, sorry abouut that, i have updated the original post $\endgroup$ – Antonis Paragas Apr 30 '17 at 8:12
  • $\begingroup$ @Antonis Paragas, Please show an example with $n=2$ in the question. Your $n=1$ example is consistent with my answer. $\endgroup$ – kodlu Apr 30 '17 at 21:48

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.