1
$\begingroup$

For a random permutation $P$ and $q$ distinct inputs $x_1,\ldots,x_q\in\{0,1\}^n$, what's the probability of the event that there exists at least one collision among $\{P(x_1)\oplus x_1,\ldots,P(x_q)\oplus x_q\}$?

Note: I have tried to compute this probability, but it is quite hard for me to obtain the result, either for the exact probability or the lower bound of this probability. The following is my attempt to solve this problem when $q=2,3$.

Denote by $\mathsf{E}$ the event that there exists at least one collision among $\{P(x_1)\oplus x_1,\ldots,P(x_q)\oplus x_q\}$.

  • If $q=2$, it is easily seen that $\Pr[\mathsf{E}]=\Pr[P(x_1)\oplus x_1=P(x_2)\oplus x_2]=\frac{1}{2^n-1}$
  • If $q=3$, we have 3 random elements $P(x_1)\oplus x_1,P(x_2)\oplus x_2,P(x_3)\oplus x_3$. We focus on computing $\overline{\mathsf{E}}$ the complementary event of $\mathsf{E}$: \begin{align}\Pr[\overline{\mathsf{E}}]=&\Pr[P(x_1)\oplus x_1\neq P(x_2)\oplus x_2 \wedge P(x_1)\oplus x_1 \neq P(x_3)\oplus x_3 \wedge P(x_2)\oplus x_2 \neq P(x_3)\oplus x_3]\\ =&\Pr[P(x_1)\oplus x_1 \neq P(x_3)\oplus x_3 \wedge P(x_2)\oplus x_2 \neq P(x_3)\oplus x_3\mid P(x_1)\oplus x_1\neq P(x_2)\oplus x_2]\cdot\Pr[P(x_1)\oplus x_1\neq P(x_2)\oplus x_2] \end{align} Without loss of generality, assume that the value of $P(x_1)$ is fixed. There are $2^n-1$ possibilites for $P(x_2)$. Conditioned on the event $P(x_1)\oplus x_1\neq P(x_2)\oplus x_2$ happening, the probability of the event $P(x_1)\oplus x_1\neq P(x_3)\oplus x_3\wedge P(x_2)\oplus x_2\neq P(x_3)\oplus x_3$ may change according to the choices of $P(x_2)$:
    • If $P(x_2)=P(x_1)\oplus x_1\oplus x_3$ or $P(x_2)=P(x_1)\oplus x_2\oplus x_3$, then the probability of the event $P(x_1)\oplus x_1\neq P(x_3)\oplus x_3\wedge P(x_2)\oplus x_2\neq P(x_3)\oplus x_3$ is $\frac{2^n-2-1}{2^n-2}$.
    • If $P(x_2)\neq P(x_1)\oplus x_1\oplus x_3$, $P(x_2)\neq P(x_1)\oplus x_2 \oplus x_3$ and further $P(x_2)\neq P(x_1)\oplus x_1\oplus x_2$, then the probability of the event $P(x_1)\oplus x_1\neq P(x_3)\oplus x_3\wedge P(x_2)\oplus x_2\neq P(x_3)\oplus x_3$ is $\frac{2^n-2-2}{2^n-2}$.
    Hence, \begin{align} \Pr[\overline{\mathsf{E}}]=&\frac{2}{2^n-1}\cdot\frac{2^n-3}{2^n-2}+\frac{2^n-1-3}{2^n-1}\cdot\frac{2^n-4}{2^n-2}\\ =&\frac{2^{2n}-6\cdot 2^n+10}{(2^n-1)(2^n-2)}, \end{align} and $\Pr[\mathsf{E}]=1-\Pr[\overline{\mathsf{E}}]=1-\frac{2^{2n}-6\cdot 2^n+10}{(2^n-1)(2^n-2)}$.
  • For $q\ge4$, the computation is complicated and I haven't found a good method to tackle it.
$\endgroup$
  • $\begingroup$ What is $\oplus$ here? "XOR", i.e., $a\oplus 0=a$ and $a\oplus 1=a\pm1$ with $\lfloor( a\oplus 1)/2\rfloor =\lfloor a/2\rfloor$? $\endgroup$ – Hagen von Eitzen May 26 '18 at 8:18
  • $\begingroup$ @HagenvonEitzen: $\oplus$ (bitwise XOR) takes two bit patterns of equal length and performs the logical exclusive OR operation on each pair of corresponding bits. For example, $00\oplus 01=01$, $11\oplus 01=10$. $\endgroup$ – bird May 28 '18 at 3:38
0
$\begingroup$

I've solved your problem in case when inputs are not distinct. The obtained result may be used as an approximation or a bound in your case.

Fix $q, n \in \mathbb{N}$. Let $x_1, x_2, \ldots, x_q \in \mathbb{Z}_2^n$ be random vectors, and let $P$ be a random permutation of set $\{1, 2, \ldots, n\}$.

Let $P = \sigma_1 \sigma_2 \ldots \sigma_k$ be a decomposition of $P$ into cycles. Note that there are exactly $c(n, k)$ permutations for given value of $k$, where $c(n, k)$ is a Stirling number of the 1st kind.

Lemma. Let $\varphi$ be a cycle of length $m$, and $v, w \in \mathbb{Z}_2^m$.

Then $\varphi(v)\oplus v = \varphi(w)\oplus w \Leftrightarrow v = \pm w$.

Proof.

$(\Rightarrow)$ Let $\varphi(v)\oplus v = \varphi(w)\oplus w$.

Then $v_i + v_{i+1} = w_i + w_{i+1}, \quad i = 1, 2, \ldots, m$.

$v_i - w_i = w_{i+1} - v_{i+1} = v_{i+1} - w_{i+1}\,$ in $\mathbb{Z}_2$.

Therefore $v - w = (1, 1, \ldots, 1)$ or $(0, 0, \ldots, 0)$.

Hence $v = -w$ or $v = w$.

$(\Leftarrow)$ The inverse is evident.

$\square$

Let $\Gamma(v) = P(v) \oplus v$ be an operator on $\mathbb{Z}_2^n$.

Now, consider any vector $v$ from $\mathbb{Z}_2^n$. By Lemma, there are exactly $2^k$ vectors (including $v$) in $\mathbb{Z}_2^n$, which have the same value w. r. t. action of $\Gamma$.

Then, $\mathbb{Z}_2^n$ splitted into $2^{n - k}$ subsets, each has $2^k$ elements, and

$\forall x, y$ are in the same subset $\Leftrightarrow \Gamma(x) = \Gamma(y)$.

So, if we want count number of ways to choose vectors $x_1, x_2, \ldots, x_q$, s. t. $(\forall i\neq j)\,\Gamma(i) \neq \Gamma(j)$, we have to choose them from different $q$ subsets (of $2^{n - k}$ subsets).

Therefore, we have exactly $2^{kq} \times \binom{2^{n-k}}{q} \times q!$ to choose them with given $n, q, k$.

Considering all possible numbers $k$ of cycles in the decomposition of $P$, we obtain that the number of events without collisions is

$$\sum_{k=1}^{n}c(n, k)\cdot 2^{kq} \cdot \binom{2^{n-k}}{q} \cdot q!$$

A common number of events is

$$n! \cdot 2^{nq}.$$

Hence the probability of having a collision is

$$\Pr[\overline{\mathsf{E}}] = \dfrac{\sum_{k=1}^{n}c(n, k)\cdot 2^{kq} \cdot \binom{2^{n-k}}{q} \cdot q!}{n! \cdot 2^{nq}}$$

Then $\Pr[\mathsf{E}] = 1 - \Pr[\overline{\mathsf{E}}]$.

You can verify this result by modeling, here's Python function:

def perform_try(n, q):
    # Generate random sample and permutation
    sample = np.random.randint(2, size=(q, n))
    permut = np.random.permutation(n)
    unique_rows = np.unique((sample[:, permut] + sample) % 2, axis=0)

    # If there are repeating rows then there's a collision
    return unique_rows.shape[0] < sample.shape[0]

To perform an experiment:

print(np.sum([perform_try(4, 7) for _ in range(100000)]) / 100000)

To calculate result by the formula:

import numpy as np  
import sympy  
from scipy.special import factorial  

n = 4; q = 7  
print(1 - np.sum([sympy.combinatorial.numbers.stirling(n, k, kind=1) *  
    (2**(k * q)) * comb(2**(n-k), q) * factorial(q) for k in range(1, n + 1)])/   
    (factorial(n) * 2**(n * q)))  
$\endgroup$

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.