Agostarawz

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}}\left(n\in B\right)=min\left(C\sqrt{\frac{\mathrm{log}n}{n}},1\right)$, 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 $\left(\mathrm{\Omega },\mathcal{F},\mathbb{P}\right)$ here?
2. Relating to the first question, how could I require that events $\left\{n\in B{\right\}}_{n\in {\mathbb{Z}}^{+}}$ to be jointly independent?
3. Why could I require that events $\left\{n\in B{\right\}}_{n\in {\mathbb{Z}}^{+}}$ have the assigned probability?

thatuglygirlyu

Expert

Step 1
1. There may be several probability spaces. Example: when we speak about one coin toss, we may use $\mathrm{\Omega }=\left\{0,1\right\}$, $\mathcal{F}={2}^{\mathrm{\Omega }}$, $P\left(0\right)=p$, $P\left(1\right)=1-p$ with $\xi \left(\omega \right)=\omega$ or $\mathrm{\Omega }=\left[0,1\right]$, $\mathcal{F}=\mathcal{B}\left[0,1\right]$, P-standard Lebesgue measure, with $\xi \left(\omega \right)={I}_{x\in \left[0,p\right]}$. Both of them are correct.
In your problem we may put ${\mathrm{\Omega }}_{1}=\left\{\left({i}_{1},{i}_{2},\dots \right)|{i}_{j}\in \left\{0;1\right\}\right\}$ and $\mathcal{F}=\sigma$-algebra containing the cylindrical sets. For example, $w=\left(1,0,1,1,0,\dots \right)$ 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}=\left[0,1{\right]}^{\mathbb{N}}$ with corresponding $\sigma$-algebra.
Step 2
2-3. Put $a\left(n\right)=min\left(C\sqrt{\frac{\mathrm{log}n}{n}},1\right)$ and define $P\left(w\in {\mathrm{\Omega }}_{1}:{w}_{{i}_{1}}=1,{w}_{{i}_{2}}=0,{w}_{{i}_{3}}=1\right)={a}_{{i}_{1}}\left(1-{a}_{{i}_{2}}\right){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.

Do you have a similar question?