Skip to main content
The title is improved.
Link
user64494
  • 3.5k
  • 14
  • 22

Linear Independence of Binary Vectors over realsrandom binary vectors

added 80 characters in body
Source Link
BenB
  • 111
  • 5

Suppose we have $Y_1, \ldots, Y_n \in \mathbb{R}^m$, $n$ independent random vectors ($m \geq n$), where the entries of each $Y_i$ are i.i.d. Bernoulli random variables taking the values $\{0, 1\}$ with equal probability. I am interested in estimates for the probability that the $Y_i$'s are linearly independent over $\mathbb{R}$. Or more generally, for $k \leq n$, what is the probability that for all subsets $S \subset [n]$ of size $k$, that $\{ Y_i : i \in S\}$ are linearly independent.

I have found some references that answer related questions. This post has references that speak on the asymptotic probability of a random square $\{0, 1\}$ matrix being invertible: Number of invertible {0,1} real matrices?

Most notably it includes this reference ( https://arxiv.org/abs/0905.0461 ) that shows the probability that a $n \times n$ random $\{0,1\}$ matrix is singular is $\mathcal{O}\left((\sqrt{\frac{1}{2}} + o(1))^n \right)$. Using this I can get some crude asymptotic estimates, but I am searching for a non-asymptotic result ideally.

Similar problems have been investigated where the independence is instead over $\mathbb{F}^2$: Expected number of random binary vectors so that the form a basis

Most notably this one: https://www.semanticscholar.org/paper/The-Number-of-Linearly-Independent-Binary-Vectors-Damelin-Michalski/15630b8ad6de8f245e5ea9c52a3a757bd98d701e

I am interested in any references that offer any tools that might help with this problem. I am most interested in the case when $m$ is a large constant multiple of $n$. Thank you.

Suppose we have $Y_1, \ldots, Y_n \in \mathbb{R}^m$, $n$ independent random vectors ($m \geq n$), where the entries of each $Y_i$ are i.i.d. Bernoulli random variables taking the values $\{0, 1\}$ with equal probability. I am interested in estimates for the probability that the $Y_i$'s are linearly independent over $\mathbb{R}$. Or more generally, for $k \leq n$, what is the probability that for all subsets $S \subset [n]$ of size $k$, that $\{ Y_i : i \in S\}$ are linearly independent.

I have found some references that answer related questions. This post has references that speak on the asymptotic probability of a random square $\{0, 1\}$ matrix being invertible: Number of invertible {0,1} real matrices?

Most notably it includes this reference ( https://arxiv.org/abs/0905.0461 ) that shows the probability that a $n \times n$ random $\{0,1\}$ matrix is singular is $\mathcal{O}\left((\sqrt{\frac{1}{2}} + o(1))^n \right)$. Using this I can get some crude asymptotic estimates, but I am searching for a non-asymptotic result ideally.

Similar problems have been investigated where the independence is instead over $\mathbb{F}^2$: Expected number of random binary vectors so that the form a basis

Most notably this one: https://www.semanticscholar.org/paper/The-Number-of-Linearly-Independent-Binary-Vectors-Damelin-Michalski/15630b8ad6de8f245e5ea9c52a3a757bd98d701e

I am interested in any references that offer any tools that might help with this problem. Thank you.

Suppose we have $Y_1, \ldots, Y_n \in \mathbb{R}^m$, $n$ independent random vectors ($m \geq n$), where the entries of each $Y_i$ are i.i.d. Bernoulli random variables taking the values $\{0, 1\}$ with equal probability. I am interested in estimates for the probability that the $Y_i$'s are linearly independent over $\mathbb{R}$. Or more generally, for $k \leq n$, what is the probability that for all subsets $S \subset [n]$ of size $k$, that $\{ Y_i : i \in S\}$ are linearly independent.

I have found some references that answer related questions. This post has references that speak on the asymptotic probability of a random square $\{0, 1\}$ matrix being invertible: Number of invertible {0,1} real matrices?

Most notably it includes this reference ( https://arxiv.org/abs/0905.0461 ) that shows the probability that a $n \times n$ random $\{0,1\}$ matrix is singular is $\mathcal{O}\left((\sqrt{\frac{1}{2}} + o(1))^n \right)$. Using this I can get some crude asymptotic estimates, but I am searching for a non-asymptotic result ideally.

Similar problems have been investigated where the independence is instead over $\mathbb{F}^2$: Expected number of random binary vectors so that the form a basis

Most notably this one: https://www.semanticscholar.org/paper/The-Number-of-Linearly-Independent-Binary-Vectors-Damelin-Michalski/15630b8ad6de8f245e5ea9c52a3a757bd98d701e

I am interested in any references that offer any tools that might help with this problem. I am most interested in the case when $m$ is a large constant multiple of $n$. Thank you.

Source Link
BenB
  • 111
  • 5

Linear Independence of Binary Vectors over reals

Suppose we have $Y_1, \ldots, Y_n \in \mathbb{R}^m$, $n$ independent random vectors ($m \geq n$), where the entries of each $Y_i$ are i.i.d. Bernoulli random variables taking the values $\{0, 1\}$ with equal probability. I am interested in estimates for the probability that the $Y_i$'s are linearly independent over $\mathbb{R}$. Or more generally, for $k \leq n$, what is the probability that for all subsets $S \subset [n]$ of size $k$, that $\{ Y_i : i \in S\}$ are linearly independent.

I have found some references that answer related questions. This post has references that speak on the asymptotic probability of a random square $\{0, 1\}$ matrix being invertible: Number of invertible {0,1} real matrices?

Most notably it includes this reference ( https://arxiv.org/abs/0905.0461 ) that shows the probability that a $n \times n$ random $\{0,1\}$ matrix is singular is $\mathcal{O}\left((\sqrt{\frac{1}{2}} + o(1))^n \right)$. Using this I can get some crude asymptotic estimates, but I am searching for a non-asymptotic result ideally.

Similar problems have been investigated where the independence is instead over $\mathbb{F}^2$: Expected number of random binary vectors so that the form a basis

Most notably this one: https://www.semanticscholar.org/paper/The-Number-of-Linearly-Independent-Binary-Vectors-Damelin-Michalski/15630b8ad6de8f245e5ea9c52a3a757bd98d701e

I am interested in any references that offer any tools that might help with this problem. Thank you.