How to understand the operation "choose a random subset" in combinatorics?Define a set B ⊂...

Agostarawz

Agostarawz

Answered

2022-07-03

How to understand the operation "choose a random subset" in combinatorics?
Define a set B Z + randomly by requiring the events n B (for n Z + ) to be jointly independent with probability P ( n B ) = min ( C log n n , 1 ) , 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 ( Ω , F , P ) here?
2. Relating to the first question, how could I require that events { n B } n Z + to be jointly independent?
3. Why could I require that events { n B } n Z + have the assigned probability?

Answer & Explanation

thatuglygirlyu

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 Ω = { 0 , 1 }, F = 2 Ω , P ( 0 ) = p, P ( 1 ) = 1 p with ξ ( ω ) = ω or Ω = [ 0 , 1 ], F = B [ 0 , 1 ], P-standard Lebesgue measure, with ξ ( ω ) = I x [ 0 , p ] . Both of them are correct.
In your problem we may put Ω 1 = { ( i 1 , i 2 , ) | i j { 0 ; 1 } } and F = σ-algebra containing the cylindrical sets. For example, w = ( 1 , 0 , 1 , 1 , 0 , ) means that 1 B , 2 B , 3 B , 4 B , 5 B , We also may put Ω 2 = [ 0 , 1 ] N with corresponding σ-algebra.
Step 2
2-3. Put a ( n ) = min ( C log n n , 1 ) and define P ( w Ω 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 σ-algebra. The existence of such a measure follows from Kolmogorov existence theorem.
Remark: the explicit form of Ω is not important in such problems as it doesn't give any useful information.

Do you have a similar question?

Recalculate according to your conditions!

Ask your question.
Get your answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?