Блог пользователя AAhaoxuan

Автор AAhaoxuan, история, 20 месяцев назад, По-английски

Given a sequence $$$( A )$$$ , where each element $$$( A_i )$$$ is a randomly chosen integer from $$$( 0 )$$$ to $$$( 2^k - 1 )$$$ , what is the probability that there exists a subsequence of $$$( A )$$$ whose XOR sum is equal to $$$0$$$ ?

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

»
20 месяцев назад, скрыть # |
 
Проголосовать: нравится +5 Проголосовать: не нравится

$$$\dfrac{1}{2^k}$$$

»
20 месяцев назад, скрыть # |
Rev. 3  
Проголосовать: нравится +9 Проголосовать: не нравится

Let $$$n$$$ be the length of $$$A$$$. Numbers from $$$0$$$ to $$$2^k-1$$$ with $$$xor$$$ is a $$$k$$$-dimensional vector space over $$$\mathbb{F}_2$$$, therefore if $$$n \gt k$$$ it is guaranteed that $$$A$$$ has $$$0$$$-sum subsequence, because $$$A$$$ is linearly dependent collection of vectors.

If $$$n\leq k$$$ we can calculate the probability by counting number of linearly independent collections of length $$$n$$$: there are $$$2^k - 1$$$ ways to choose the fisrt vector, $$$2^k-2$$$ ways for the second... $$$2^k-2^t$$$ for the $$$t+1$$$'th vector, so overall number is $$$\prod_{i=1}^{n}(2^k-2^{i-1})$$$.

Then the needed probability is $$$1- \frac{\prod_{i=1}^{n}(2^k-2^{i-1})}{2^{nk}}$$$.

Correct me if I am wrong.