Agostarawz

Answered

2022-07-03

How to understand the operation "choose a random subset" in combinatorics?

Define a set $B\subset {\mathbb{Z}}^{+}$ randomly by requiring the events $n\in B$ (for $n\in {\mathbb{Z}}^{+}$) to be jointly independent with probability $\mathbf{\text{P}}(n\in B)=min{\textstyle (}C\sqrt{\frac{\mathrm{log}n}{n}},1{\textstyle )}$, where C is a large constant to be chosen later.

Since I've not seen such a method before, I have several questions:

1. If one talks about randomness, then there should be a probability space. In the proof they choose a set B randomly, what is the probability space $(\mathrm{\Omega},\mathcal{F},\mathbb{P})$ here?

2. Relating to the first question, how could I require that events $\{n\in B{\}}_{n\in {\mathbb{Z}}^{+}}$ to be jointly independent?

3. Why could I require that events $\{n\in B{\}}_{n\in {\mathbb{Z}}^{+}}$ have the assigned probability?

Define a set $B\subset {\mathbb{Z}}^{+}$ randomly by requiring the events $n\in B$ (for $n\in {\mathbb{Z}}^{+}$) to be jointly independent with probability $\mathbf{\text{P}}(n\in B)=min{\textstyle (}C\sqrt{\frac{\mathrm{log}n}{n}},1{\textstyle )}$, where C is a large constant to be chosen later.

Since I've not seen such a method before, I have several questions:

1. If one talks about randomness, then there should be a probability space. In the proof they choose a set B randomly, what is the probability space $(\mathrm{\Omega},\mathcal{F},\mathbb{P})$ here?

2. Relating to the first question, how could I require that events $\{n\in B{\}}_{n\in {\mathbb{Z}}^{+}}$ to be jointly independent?

3. Why could I require that events $\{n\in B{\}}_{n\in {\mathbb{Z}}^{+}}$ have the assigned probability?

Answer & Explanation

thatuglygirlyu

Expert

2022-07-04Added 14 answers

Step 1

1. There may be several probability spaces. Example: when we speak about one coin toss, we may use $\mathrm{\Omega}=\{0,1\}$, $\mathcal{F}={2}^{\mathrm{\Omega}}$, $P(0)=p$, $P(1)=1-p$ with $\xi (\omega )=\omega $ or $\mathrm{\Omega}=[0,1]$, $\mathcal{F}=\mathcal{B}[0,1]$, P-standard Lebesgue measure, with $\xi (\omega )={I}_{x\in [0,p]}$. Both of them are correct.

In your problem we may put ${\mathrm{\Omega}}_{1}=\{({i}_{1},{i}_{2},\dots )|{i}_{j}\in \{0;1\}\}$ and $\mathcal{F}=\sigma $-algebra containing the cylindrical sets. For example, $w=(1,0,1,1,0,\dots )$ means that $1\in B,2\notin B,3\in B,4\in B,5\notin B,\dots $ We also may put ${\mathrm{\Omega}}_{2}=[0,1{]}^{\mathbb{N}}$ with corresponding $\sigma $-algebra.

Step 2

2-3. Put $a(n)=min{\textstyle (}C\sqrt{\frac{\mathrm{log}n}{n}},1{\textstyle )}$ and define $P(w\in {\mathrm{\Omega}}_{1}:{w}_{{i}_{1}}=1,{w}_{{i}_{2}}=0,{w}_{{i}_{3}}=1)={a}_{{i}_{1}}(1-{a}_{{i}_{2}}){a}_{{i}_{3}}$ allows us to define a measure on cylindrical $\sigma $-algebra. The existence of such a measure follows from Kolmogorov existence theorem.

Remark: the explicit form of $\mathrm{\Omega}$ is not important in such problems as it doesn't give any useful information.

1. There may be several probability spaces. Example: when we speak about one coin toss, we may use $\mathrm{\Omega}=\{0,1\}$, $\mathcal{F}={2}^{\mathrm{\Omega}}$, $P(0)=p$, $P(1)=1-p$ with $\xi (\omega )=\omega $ or $\mathrm{\Omega}=[0,1]$, $\mathcal{F}=\mathcal{B}[0,1]$, P-standard Lebesgue measure, with $\xi (\omega )={I}_{x\in [0,p]}$. Both of them are correct.

In your problem we may put ${\mathrm{\Omega}}_{1}=\{({i}_{1},{i}_{2},\dots )|{i}_{j}\in \{0;1\}\}$ and $\mathcal{F}=\sigma $-algebra containing the cylindrical sets. For example, $w=(1,0,1,1,0,\dots )$ means that $1\in B,2\notin B,3\in B,4\in B,5\notin B,\dots $ We also may put ${\mathrm{\Omega}}_{2}=[0,1{]}^{\mathbb{N}}$ with corresponding $\sigma $-algebra.

Step 2

2-3. Put $a(n)=min{\textstyle (}C\sqrt{\frac{\mathrm{log}n}{n}},1{\textstyle )}$ and define $P(w\in {\mathrm{\Omega}}_{1}:{w}_{{i}_{1}}=1,{w}_{{i}_{2}}=0,{w}_{{i}_{3}}=1)={a}_{{i}_{1}}(1-{a}_{{i}_{2}}){a}_{{i}_{3}}$ allows us to define a measure on cylindrical $\sigma $-algebra. The existence of such a measure follows from Kolmogorov existence theorem.

Remark: the explicit form of $\mathrm{\Omega}$ is not important in such problems as it doesn't give any useful information.

Most Popular Questions