Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

AAhaoxuan's blog

I have a problem
By AAhaoxuan, history, 2 years ago, In English

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$$$ ?

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
2 years ago, hide # |
 
Vote: I like it +5 Vote: I do not like it

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

→ Reply
  • »
    »
    2 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Can you please explain how?

    → Reply
    • »
      »
      »
      2 years ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      Here's what I think: we notice that the each binary bit are independent, so we only need to calculate the probability of each bit.

      To make a bit's xor sum to $$$0$$$, you have to choose an even number of positions to be $$$0$$$ and the rest to be $$$1$$$, and the probability of such a number is $$$\dfrac{1}{2}$$$. Multiply the probabilities of all the bits together to give the answer: $$$\dfrac{1}{2^k}$$$

      → Reply
  • »
    »
    2 years ago, hide # ^ |
    ← Rev. 2  
    Vote: I like it 0 Vote: I do not like it

    If $$$n=1$$$ ，It's right.

    → Reply
»
2 years ago, hide # |
← Rev. 3  
Vote: I like it +9 Vote: I do not like it

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.

→ Reply
  • »
    »
    2 years ago, hide # ^ |
     
    Vote: I like it +3 Vote: I do not like it

    Thank you! It help me prove the probability of the Problem 799F randomization algorithm being correct.

    → Reply
  • »
    »
    2 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    But the if $$$n\le k$$$，$$$2^k-2^{i-1}$$$ may be less than $$$0$$$.

    → Reply
    • »
      »
      »
      2 years ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      Minimum of $$$2^k - 2^{i-1}$$$ reached when $$$i=n$$$ and $$$n = k$$$, so it's $$$2^k-2^{k-1} = 2^{k-1} \gt 0$$$.

      → Reply