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$$$ ?
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3603 |
| 4 | jiangly | 3583 |
| 5 | turmax | 3559 |
| 6 | tourist | 3541 |
| 7 | strapple | 3515 |
| 8 | ksun48 | 3461 |
| 9 | dXqwq | 3436 |
| 10 | Otomachi_Una | 3413 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 157 |
| 2 | adamant | 153 |
| 3 | Um_nik | 147 |
| 3 | Proof_by_QED | 147 |
| 5 | Dominater069 | 145 |
| 6 | errorgorn | 142 |
| 7 | cry | 139 |
| 8 | YuukiS | 135 |
| 9 | TheScrasse | 134 |
| 10 | chromate00 | 133 |
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$$$ ?
| Название |
|---|



$$$\dfrac{1}{2^k}$$$
Can you please explain how?
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}$$$
If $$$n=1$$$ ,It's right.
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.
Thank you! It help me prove the probability of the Problem 799F randomization algorithm being correct.
But the if $$$n\le k$$$,$$$2^k-2^{i-1}$$$ may be less than $$$0$$$.
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$$$.