A question related to cardinality and probability.

baiyang11

New member
Joined
Jul 9, 2013
Messages
15
A question related to cardinality and probability(repost).

Dear all,

I have a question below related to both probability and cardinality. Let me know if my formulation of the problem is non-rigorous or confusing. Any proof or suggestions are appreciated. Thank you all.
The question follows.


Consider a set \(\displaystyle I\) consists of \(\displaystyle N\) incidents.
\[I=\{i_{1},i_{2},...,i_{k},...i_{N}\}\]
Each incident has a probability to happen, i.e. incident \(\displaystyle i_{k}\) happens with the probability \(\displaystyle r_{k}\). Without loss of generality, we assume \(\displaystyle r_{1}\geq r_{2}\geq ... \geq r_{k}\geq ... \geq r_{N}\)
Given a constant \(\displaystyle n<N\), we can have set \(\displaystyle I_{1}=\{i_{1},i_{2},...,i_{n}\}\). Apparently, \(\displaystyle |I_{1}|=n\) and \(\displaystyle I_{1}\subset I\).
Define a mapping \(\displaystyle I\to S\) with \(\displaystyle S=\{s_{1},s_{2},...,s_{k},...s_{N}\}\) subject to
\[
s_{k} = \left\{ \begin{array}{ccc}
1 &\mbox{ (Pr=$r_{k}$)} \\
0 &\mbox{ (Pr=$1-r_{k}$)} \\
\end{array} \right.
\]
Pick out the incidents with correspond \(\displaystyle s\) being 1 to form the set \(\displaystyle I_{2}\) , i.e.
\[I_{2}=\{i_{m_{1}},i_{m_{2}},...,i_{m_{M}}\} \quad \mbox{and} \quad s_{m_{k}}=1 \quad k=1,2,...,M \]
Apparently, \(\displaystyle |I_{2}|=M\) and \(\displaystyle I_{2}\subset I\). Note that there could be \(\displaystyle I_{2}\ne I_{1}\) and \(\displaystyle |I_{2}| \ne |I_{1}|\).

The question is,
If we have two set \(\displaystyle A\) and \(\displaystyle B\) with \(\displaystyle |A|=|B|=n\) and assume
\[ |A \cap I_{1}| \geq |B \cap I_{1}| \]
Is the following statement true?
\[ E(|A \cap I_{2}|) \geq E(|B \cap I_{2}|) \]
where \(\displaystyle E\) means expected value.
If this is true, how to prove it? If not, how to prove it’s not true?
 
Last edited:
Is there a reason why you are attaching a zip file? Exactly how long is this question?
Many people will be reluctant to open any file for fear of computer viruses. And, it is harder to tell with a "zipped" file.
 
Is there a reason why you are attaching a zip file? Exactly how long is this question?
Many people will be reluctant to open any file for fear of computer viruses. And, it is harder to tell with a "zipped" file.

Thank you. I will try to edit my thread to make things more convenient for people.
 
Just rambling but if A has at least as many elements of I1 as B has, then I would expect that, on average, A would contain at least as many elements of I2 as B has since I2 \(\displaystyle \subset\) I1. Certainly it is true at the extremes, rk = 1; k = 1, 2, 3, ... and rk = 0; k = 1, 2, 3, ...
 
Just rambling but if A has at least as many elements of I1 as B has, then I would expect that, on average, A would contain at least as many elements of I2 as B has since I2 \(\displaystyle \subset\) I1. Certainly it is true at the extremes, rk = 1; k = 1, 2, 3, ... and rk = 0; k = 1, 2, 3, ...

Thank you!
Note that it is NOT I2 \(\displaystyle \subset\) I1. , otherwise it would be trivial. It is I2 \(\displaystyle \subset\) I. There is no guarantee about the 'bigger or smaller' relationship between I2 and I1.
The extreme case would be easy as well.
 
Thank you!
Note that it is NOT I2 \(\displaystyle \subset\) I1. , otherwise it would be trivial. It is I2 \(\displaystyle \subset\) I. There is no guarantee about the 'bigger or smaller' relationship between I2 and I1.
The extreme case would be easy as well.

Sorry, got contused. I read 'Define a mapping [FONT=MathJax_Math]I1[/FONT][FONT=MathJax_Main]→[/FONT][FONT=MathJax_Math]S[/FONT]...' which, on re-reading, is not what it said at all. If I'm understanding it correctly now, let the following be ordered sets and
I = {1, 2, 3, 4, ...}
r = {0, 1, 1, 1, ...}
I1 = {1}
A = {1}
B = I
then
S = {0, 1, 1, 1, ...}
I2 ={2, 3, 4, 5, ...}

\(\displaystyle |A\space \bigcap\space I_1| = |\{1\}| = 1 \ge |B\space \bigcap\space I_1| = |\{1\}| = 1\)

\(\displaystyle |A\space \bigcap\space I_2| = |\{\}| = 0 \lt |B\space \bigcap\space I_2| = \aleph_0 \)

EDIT: Oh, and the expected value of a constant is the constant.
 
Last edited:
Sorry, got contused. I read 'Define a mapping [FONT=MathJax_Math]I1[/FONT][FONT=MathJax_Main]→[/FONT][FONT=MathJax_Math]S[/FONT]...' which, on re-reading, is not what it said at all. If I'm understanding it correctly now, let the following be ordered sets and
I = {1, 2, 3, 4, ...}
r = {0, 1, 1, 1, ...}
I1 = {1}
A = {1}
B = I
then
S = {0, 1, 1, 1, ...}
I2 ={2, 3, 4, 5, ...}

\(\displaystyle |A\space \bigcap\space I_1| = |\{1\}| = 1 \ge |B\space \bigcap\space I_1| = |\{1\}| = 1\)

\(\displaystyle |A\space \bigcap\space I_2| = |\{\}| = 0 \lt |B\space \bigcap\space I_2| = \aleph_0 \)

EDIT: Oh, and the expected value of a constant is the constant.


Thanks for the reply. But I think in your example you ignore two of my assumptions, which is (1) \(\displaystyle r_{1}\geq r_{2} \geq ... \geq r_{k} \geq ... \geq r_{N}\) ;(2) \(\displaystyle |A|=|B|=n\).
 
Last edited:
Thanks for the reply. But I think in your example you ignore two of my assumptions, which is (1) \(\displaystyle r_{1}\geq r_{2} \geq ... \geq r_{k} \geq ... \geq r_{N}\) ;(2) \(\displaystyle |A|=|B|=n\).

You are right about the |A|=|B|=n but the other is artificial since you started with a "without loss of generality" to get the non-increasing order so you just lost the generality or there is a 1 to 1 map mapping any set of the r's to your set of r's in non-increasing order and it doesn't make a difference whether they are non decreasing or non-increasing or scattered all over the place.
 
Last edited:
Does this work?
I = {2, 4, 1, 3}
r ={1, 1, 0, 0}
I1 = {1, 3}
A = {1, 3}
B = {2, 4}
 
Does this work?
I = {2, 4, 1, 3}
r ={1, 1, 0, 0}
I1 = {1, 3}
A = {1, 3}
B = {2, 4}

I'm sorry If my statement of the problem is not rigorous cause I'm not a math major. I will appreciate if you can improve it.
Let's say we forget about the 'loss of generality'. Let's assume the elements in \(\displaystyle I\) are indeed in a non-increasing probability order. The reason is that essentially I want to assume \(\displaystyle A\) has no less incidents of high probability than \(\displaystyle B\), then I want to see if \(\displaystyle A\) has no less incidents than \(\displaystyle B\) when those incidents 'realize' based on its Bernoulli law. Of course, in a expected value.
 
Additional assumption

I should also add \(\displaystyle A \subset I\) and \(\displaystyle B \subset I\) as one of the assumptions.
 
Could you please provide an example based on the assumptions I made? I mean the non-increasing assumption.

Are you referring to r ={1, 1, 0, 0} as not non-increasing. Well I did think that 1\(\displaystyle \space \ge\space \)1\(\displaystyle \space \ge\space \)0\(\displaystyle \space \ge\space \)0. It does make me feel a little better;)

Oh, and I also think [FONT=MathJax_Math]A[/FONT][FONT=MathJax_Main]⊂[/FONT][FONT=MathJax_Math]I[/FONT] and [FONT=MathJax_Math]B[/FONT][FONT=MathJax_Main]⊂[/FONT][FONT=MathJax_Math]I[/FONT] with the given example
I = {2, 4, 1, 3}
r ={1, 1, 0, 0}
I1 = {1, 3}
A = {1, 3}
B = {2, 4}
 
Are you referring to r ={1, 1, 0, 0} as not non-increasing. Well I did think that 1\(\displaystyle \space \ge\space \)1\(\displaystyle \space \ge\space \)0\(\displaystyle \space \ge\space \)0. It does make me feel a little better;)

Oh, and I also think [FONT=MathJax_Math]A[/FONT][FONT=MathJax_Main]⊂[/FONT][FONT=MathJax_Math]I[/FONT] and [FONT=MathJax_Math]B[/FONT][FONT=MathJax_Main]⊂[/FONT][FONT=MathJax_Math]I[/FONT] with the given example
I = {2, 4, 1, 3}
r ={1, 1, 0, 0}
I1 = {1, 3}
A = {1, 3}
B = {2, 4}

If you look at the problem in the original post, you can find acutally \(\displaystyle I_{1}\) contains the first \(\displaystyle n\) elements of \(\displaystyle I\) with larger probabilities. However in your exmple this is not the case.
I am sorry my poor formulation makes you hard to understand. To avoid more confusion, let me start over and reformulate my problem like the following, which is more succinct I believe.

【Start】
Consider \(\displaystyle N\) random variables \(\displaystyle X_{n}\) each following a Bernoulli distribution \(\displaystyle B(r_{n})\) with \(\displaystyle 1 \geq r_{1} \geq r_{2} \geq ... \geq r_{N} \geq 0\). If we make following assumptions of sets \(\displaystyle A\) and \(\displaystyle B\):

(1) \(\displaystyle A \subset I \) and \(\displaystyle B \subset I\) with \(\displaystyle I=\{1,2,3,...,N\}\)

(2) \(\displaystyle |A \cap I_{1}| \geq |B \cap I_{1}|\) with \(\displaystyle I_{1}=\{1,2,3,...,n\}, n<N\)

(3) \(\displaystyle |A|=|B|=n\)

Do we have \(\displaystyle \mathbb{E}(\Sigma_{a\in A} X_{a}) \geq\mathbb{E}(\Sigma_{b\in B} X_{b})\)?

To avoid confusion, \(\displaystyle \mathbb{E}\) means expected value.
【End】

I truly appreciate your effort if you could answer the reformulated problem. Thank you!
 
If you look at the problem in the original post, ...
Although it might not be true, seems like the problem has been changing so I'm quitting. It certainly seems strange that I wouldn't have noticed that I1 had to be the first n elements of I AND that the r's could be re-arranged in any way wanted without changing the problem. But then I did miss those other conditions.
 
Top