Thanks a lot for your answer! I am reading it carefully. But was I right with the finite probability space $(\Omega, \text{Pr})$?

So I defined the finite probability space $(\Omega,\text{Pr})$ as follows: $\Omega$ - the family of all tournaments on $n$ players. Hence $|\Omega|=2^{\binom{n}{2}}$ and $\text{Pr}[\omega]=2^{-\binom{n}{2}}$ for each $\omega\in \Omega$. Suppose that $V=\{p_1,\dots,p_n\}$ be the set of players. WLOG assume that $S=\{p_1,\dots,p_k\}$. Define $A_S:=\{\omega\in \Omega: \text{no}\ y\notin S \ \text{beats all of}\ S\}$.

One can see that $A_S=\bigcap\limits_{j=1}^{n-k}A_S^{(j)}$ where $A_S^{(j)}:=\{\omega\in \Omega: \ p_{j+k}\notin S \ \text{does not beat all of}\ S\}$ for $1\leq j\leq n-k$. I know that $\text{Pr}[A_S^{(j)}]=1-2^{-k}$. But how it follows that $\text{Pr}[A_S]=(1-2^{-k})^{n-k}$? I am not so familiar with probability theory except basic definitions. Can you explaim that moment please?

@PlayGame Your probability space is right. If $A$ and $B$ are two independent events, then $\Pr(A\bigcap B) = Pr(A)Pr(B)$. Two events are independent if the issue of one event have no correlation on the other. Here, the sets of edges from $y\notin S$ to $S$ are disjoint for all $y$, so the corresponding probabilities will be independent.

I was wondering can you give a more detailed explananation for that, please? I really have issues to understand that. I have never seen this before and I'd be grateful if I can see this for the first time in details

@PlayGame Suppose you have two urns, the first with $n_1$ balls, $k_1$ white and $n_1-k_1$ black, and second one with $n_2$ balls, $k_2$ white and $n_2-k_2$ black. We take one ball in each urn. Let $W_i$ be the event "we get a white ball in urn i", $Pr(W_1) = \frac{k_1}{n_1}$, $Pr(W_2) = \frac{k_2}{n_2}$. The ball we get in urn 1 does not influence the result in urn 2, so $W_1$ and $W_2$ are independent. From the $n1n_2$ possible ways to draw balls, we have $k_1k_2$ possibilities to get to white balls, so $Pr(W_1\bigcap W_2) = \frac{k_1k_2}{n_1n_2} = Pr(W_1)Pr(W_2)$.

I still cannot get why $P(W_1\cap W_2)=\frac{k_1k_2}{n_1n_2}$. I am still very confused. I guess the question why those events are independent should be proved in a rigorous way with details, I think. Can we do that?

How you can take the intersection of $W_1$ and $W_2$ if they have different structure? Can you give a detailed answer to my question, please?

@PlayGame If you want more in depth definitions, you should probably take a book of probabilities, it's hard to explain these kind of things in a 500 characters comments. $W_1\bigcap W_2$ means both $W_1$ and $W_2$ are realized, so we got a white ball in urn 1 and a white ball in urn 2. The total number of outcomes is $n_1n_2$ ($n_1$ possible outcomes in the first urn, $n_2$ in the second). The total number of outcome for $W_1\bigcap W_2$ is $k_1k_2$ ($k_1$ possibilities of getting a white ball in urn 1, $k_2$ in urn 2), so the probability is $\frac{k_1k_2}{n_1n_2}$.

This is not a definition, more an example which should give intuition about independence of events. The definition of $A$ and $B$ are independent is $P(A\bigcap B) = P(A)P(B)$, so the "rigorous way" of proving independence is by computing the probability as I did, by enumerating the possible outcomes.

To be honest yesterday all day long I was reading book on probability theory and learnt some new stuff but let's be more precise: I defined the finite probability space $(\Omega, P)$ with uniform probability distribution. We considered the event $A_S$ which can be written as the intersection of finitely many events, i.e. $A_S=A_S^1\cap\dots \cap A_S^m$. In almost every book which I read the definition of independence is as follows: The events $A,B$ are independent, if $P(A\cap B)=P(A)P(B)$.

So look we have the following situation: We have events $A_S,,A_S^1,\dots,A_S^m$ such that $A_S=A_S^1\cap \dots\cap A_S^m$. You cannot claim in words that they are independent and then write $P(A_S)=P(A_S^1)\dots P(A_S^m)$. You need to calculate $P(A_S)$ and show that it is equal to $P(A_S^1)\dots P(A_S^m)$ and only after that you can claim that they are independent. I hope I was clear.

@PlayGame Ok, lets take this rigorously. Lets fix an canonical orientation for each edge, let $A_e$ the event: $e$ is oriented in its canonical orientation. Your defined your probability space uniformly over all possible orientation of all edges. It's easy to see that half of the orientations have $e$ oriented in canonical orientation, and half have $e$ oriented in reverse orientation, so $P(A_e)=1/2$. Similarly, we can show that for two distinct edges $e_1$ and $e_2$, $P(A_{e_1}\bigcap A_{e_2})=1/4$ by enumerating the possibilities, so $A_{e_1}$ and $A_{e_2}$ are independent.

what do you mean by canonical orientation? It is not clear at all to be honest. Can you give some clarifying examples?

Hello!

How are you? I hope you are doing well!

Can we start from scratch?

I mean that we just take some orientation, no matter what the orientation is, this is just a way to distinguish an orientation from the other

TO be honest I am totally lost but I understood every moment of Erdos theorem except independence

Can we start from scratch

Lets use a simpler example

If you say so

We throw a coin two times, the possible outcomes are hh, ht, th, tt

of course

the probability of the first coin being head is 1/2, because the possible outcomes are ht and hh, over the four possible outcomes

of course

Similarly, probably that second coin is head is 1/2

yes

Probability that both coins are head is 1/4, because the only possible outcome is hh

yes. I know this

So the events are independent

which events namely? the first is head and the second is head

Yes

due to the definition yes they are independent because P(A\cap B)=P(A)P(B)

In fact, if we take all the possible ways to write head and tails uniformly, this is the same as tossing the coins one by one

because you computed probability explicitly for each of them, i.e. for A,B and A\cap B

yes

ok

In your example, your uniform distribution is the same as affecting an orientation for each edge one by one

each edge orientation is like a coin toss

not so clear

wording is really confusing

can we just concentrare our attention to the original problem and the original notations?

I think using some fancy words does not make it easy

We have finite probability space which is a pair of finite set and probability distribution

Lets number the vertices from one to n. We will say that an edge is in direct orientation if it goes from a label to a greater label, and in reverse orientation otherwise

Does this definition makes sense for you?

you mean from i to j, where i<j

?

Yes

Now, we write D if and edge is oriented in direct orientation, and R if in reverse orientation

ok

So choosing an edge orientation on the whole graph is like writing a sequence of D and R of length $n \choose 2$

So this is the same as tossing $n \choose 2$ coins

yes but you need firstly to define an order right?

Yes, we define an arbitrary order on the edges

if you write smth like DDRD... you need to define to which edge the first letter is assigned

yes, just number the edges in any order you want

ok

Now, suppose that the label of $S$ are smaller than every other labels.

so in some sense we tossing $\binom{n}{2}$ coins simultaneously, right?

Yes, and it is the same as tossing the coins one by one

Because each coin toss is independent of the other, as we shown

yes suppose that the label of $S$ are smaller than every other labels.

Now, a vertex $v$ outside of $s$ win against all of $S$ if the edges from $v$ to $s$ are all in Reverse.

a vertex outside of $s$ don't win against all of $S$ if at least one of the edges from $v$ to $s$ is in Direct orientation

Can we continue this discussion a bit later, I will be occupied for a moment?

yes sure! just text me here I'll join you immediately

I spent some time trying to understand what you wrote and I see that there are some inconsistency here

you claim that an egge is assigned D if it goes from i to j, where i<j

I really suggest to restrict to the previous notation which we had.

Hello

I think that you were right. Can we continue diwcussion?

Ok, so let $D_e$ the event that edge $e$ is in direct orientation. (and $R_e$ defined similarly). Let $A_v$ be the event for which $v \notin S$ is beating all of $S$. $A_v$ is the intersection of all $A_e$, for all edges $e$ going from $v$ to $S$.

P(A_s) = (1/2)^k, because each the events $A_e$ are mutually independent

A set of events is mutually independent if no matter what subset of events we take, the probability of the intersection is equal to the product of the probabilities.

This is a stronger requirement than having pairwise independence

We didn't prove that there are mutually independent, but this can be shown the same way as before

$A_v^c$ (the complementary of $A_v$) is the event that $v$ do not beat all of $S$. We have $A_v^c$ the union of $D_e$ for all edges $e$ from $v$ to $S$.

P(A_v^c) = 1 - (1/2)^k because of complement

If A, B, and C are mutually independant events, then this is rather easy to prove that $A$ and $B \cup C$ are independent (this is a good exercise)

Give me some time to grasp all this

ok

Thank you for your time! I really appreciate your help

"Now, suppose that the label of $S$ are smaller than every other labels." - thisbis what you wrote above.

S is the set of k numbers. Wgat do you mean by label of S?

the label is the name of the vertices

We suppose all vertices are numbered from 1 to n

labels*

the labels of the vertices of $S$ will be the k smallest integers

Label is some number from 1 to n?

Smth is wrong with your wording. What is "will be the k smallest integers"?

Yes, when you told i to j with i < j, the i and j you were referring are labels

The k smallest integers are 1, 2, ..., k

But S could be smth different from 1,2,...,k

Excuse me but what you wrote is clear. I knew this already

If not, we just relabel the vertices

You did not answer my question. You just repeatrd your reasoning and did not prove anything

Sorry but i am really confused.

Everything you wrote is very sketchy and not rigorous at all

I reread it 5 times. Sorry but you did not prove anything

You did not exolain my main question. Why you need to take a product

My goal is to prove that $A_v$ for all $v$ not in $S$ are mutually independent, to jsutify that the probability of their intersection is the product of their probability

For this, we need to decompose $A_v$ in the intersection of the smaller events on the edges

So what?

You are computing some basic probabilities which I knew already. I do not know what you are doing

I think you cannot help me since you did not understand my question

The fact that the $A_v$ are mutually independent is somewhat intuitive, because the edges between the $A_v$ are all different, which explain why these events are mutually independent

It is not intuitive

That should be proven you know)

I didn't ended my demonstration, as you told me you neeeded some time to grasp what I wrote

Then you started to change label of S.

I know this is not intuitive when we are first learning probabilities, this is why we are trying to prove it rigorously

Excuse me but nothing is rigorous in your proof

But you did not prove.

You cannot change labels of vertices. They should be fixed

The labels are not very important. I needed labels to get a canonical orientation for edges. We can set another labeling if we want, we just have to be consistent with labeling we use in the reasoning. But let simplify this is this context.We will say that an edge is in Direct orientation if the edge go from a vertex of $S$ to a vertex outside of $S$ (other edges are not considered because they will not appear in the proof)

*with which labeling

You know I am math undergradaute and I have some small experience in math

I think smth is really wrong with your reasoning

If you are ready to discuss we can do that but we need to introduce definitions

Since you changing them in the course of proof

I really suggest you to us definition which are already in the text

Are you here?

There is no change in definition, we are just defining a new labeling to the vertices to define the canonical orientation. Sometimes, to prove a result, you need to introduce concepts that are not in the original statement. But let put labels aside, and focus on the definition of oriented edge I gave in the previous message, this will be siple

*simpler

Ok lets start from scratch

So what is our first step?

Do we agree that P(A_v) = (1/2)^k ? We have already shown that. This is a consequence of the fact that $A_e$ are all independents for the $k^$ edges from $v$ to $S$.

I know that using my definitions. But i told you that your definitions are really difficult to ubderstand

You again claiming that A_e independent

I am saying it 100 times. You do not know that

Do you understand me?

$A_e$ are pairwise independent, we proved it by calculating the probabilities

We can also show that they are mutually independent, we just need to show that the probability of tossing all heads on a set of $k$ fixed coins is $(1/2)^k$

What head?

Are you kidding me?)

We said that fixing an orientation is the same as tossing a coin

I think you do not understand what i am trying to say

Where are you confused about the reasoning?

Are you student?

I am in Phd

Wow

You are trying to prove smth. But in the proof you claim that it is intuitive

You need to declare some definitions

I have never seen such approachs in proof

Yes, this is intuitive in the following sense. Let $v$ and $v'$ be two distinct vertices not in $S$. the set of edges from $v$ to $S$ and from $v's$ to $S$ are not in $S$ are disjoint. So the probabilities associated of $A_v$ and $A_v'$ will be independent, because the outcome of $A_v$ will have no influence on the outcome of $A_v'$. But if you want a very rigorous proof, you need to go down the rabbit hole of breaking these events in the intersection or union of smaller events

This is what i am asking

I declared many definitions since we started. All of the reasoning I used are quite common, but I agree there can be some time to grasp some of them when we first encounter them.

It ia not intuitive for me

But you chabged those defibition during the proof and started going back to the old one

What exactly did I change? We didn't change labels, we just defined a new labeling. For the remaining, I always kept consistent with the definitions

Ok. Let's do the following

forget about confusing definitions

our goal is to prove that $Pr[A_S]=(1-2^{-k})^{n-k}$

right

do you agree with that?

yes

A_S=\{omega\in \Omega: no y\notin S beats all of S\}, where S-the set of k players

right?

I just want to make sure that we understand ech other

yes

Suppose that $V=\{p_1,..,p_n\}$ the set of n players. Since S-the set of k players then WLOG we can assume that S={p_1,...p_k} (the set of first k players).

ok

Define new sets B_{k+1},\dots,B_n, where B_j={\omega\in \Omega: p_{j} does not beat all of S} for j=k+1,\dots,n. Let me remind you that $\Omega$-the set of all tournaments (btw $|\Omega|=2^{\binom{n}{2}}$).

so we defined $n-k$ sets $B_j$

ok

It is easy to see that A_S=B_{k+1}\cap \dots\cap B_n

Yes

I can compute the probability of event B_j for any j. Indeed Pr(B_j)=1-2^{-k} for each j=k+1,..,n

yes

our goal to show that $Pr[A_S]=(1-2^{-k})^{n-k}$. This is the only step which I cannor grasp.

I would be really really really thankful if someone can explain it to me in details

Please

This is equivalent to show that the $B_{i}$ are mutually independent.

do you agree?

not to be honest my friend.

is there any definition for that?

The $B_i$ are mutually independent if for any $E \subseteq \{k+1, ..., n\}$, P(\bigcap_{i\in E} B_i) = \Pi_{i\in E} P(B_i)$. In other word, for every set of $B_i$, the probability of their intersection is the product of their probabilities

ok.

it sounds like a circular reasoning

$A$ and $B$ are independent if $P(A\bigcap B) = P(A)P(B)$.

Now, if we have more than two events, they are two kinds of independence :

One where we just need A,B independent for every pair of events

But there are cases where this is not satisfactory, because we can have $P(A\bigcap B\bigcap C) \neq P(A)P(B)P(C)$

i have seen this yesterday in my probability book

i agree with you

So here we want the stronger definition of independence, which is mutual independence.

The $C_{(i,j)}$ are mutually independent, do you agree?

are we considering family of events C_{(i,j)}?

which index is fixed and which vary?

Yes, both indices vary

I guess we have $\binom{n}{2}$ such indices

no, only $k(n-k)$, because $i\notin S, j\inS$

sure you are right. and we claim that they mutuall independent right?

Yes

can you give 3 minutes to understand that please

I found out that Pr[C_{(i,j)}]=1-1/2=1/2

Yes

Thank you for your patient. I am so dumb

it implies that Pr[C_{i_1,j_1}]\times \dots \times Pr[C_{i_t,j_t}]=1/2\times \dots\times 1/2=1/2^t.

We need to show that probability of their intersection is also 1/2^t

For your information, we just taking t such events

Yes

Fistr of all we need tounderstand that the descrition of event C_{(i_1,j_1)}\cap \dots\cap C_{(i_t,j_t)}. It is the following event: \{\omega \in \Omega: i_1 does beat j_1, .. i_t does not beat j_t\}. which is the same as \{\omega \in \Omega: j_1 beats i_1, .. j_t beats i_t\} because if i dos not beat j, then j beats i be definition of tournament. Hence this probability is (1/2)^t because edges are distinct and we fix t of them

perfect

ok.

Now, can you prove that if A,B and C are mutually disjoint, then $A$ and $B\bigcup C$ are disjoint?

not disjoint, independent, sorry

only for three sets right?

For the moment, we will generalize progressively

You wrote B union C. is that correct?

should be intersection or not?

no, its union

let me think. btw, are you in US also? otherwise we have a big time difference

No, I'm in Europe, its 23 pm for me

Do you agree that $B_i = \bigcup_{j \in S} C_{i,j}$?

perfect

OF course I agree that $B_i = \bigcup_{j \in S} C_{i,j}

follows from definition of those sets

Now, Let $\{A_i, i=1,...n\}\bigcup \{B_i, i=1,...m\} be a set of mutually independent events. Can you show that $\bigcup_i A_i$ and $\bigcup_i B_i$ are independent ?

I guess the B_i in your last sentence is not the same as my B_i, right?

Yes, different B

hmm. let me think

It can help to use the complement.

is it somehow related with your previous question with 3 sets?

Yes, same idea, though your proof is not that easily extendable to this case (but we can make it work)

some kind of induction probably

we can do that without induction, especially when taking the complement

not so clear to me

looks like inclusion exclusion principle

Let $E = \bigcup_i A_i \bigcap\bigcup_i B_i$. On one hand, calculate $P(E) = 1-P(E^c)$. On the other hand, calculate $P(\bigcup_i A_i )P(\bigcup_i B_i )$ also taking the complement.

let me read your proof

Incusion exclusion can probably work here, but it will be more complex.

let me understand your proof. not so easy

This is not the whole proof, you still need to simplify both sides

i know

if we have information about independence of A_i and B_j can we say smth about their complements?

Ah, yes, If A and B are independent, then A and B^c also are, can you show that?

let's do this! I will think on this. this is a nice problem which I want to solve myself

can we move on?

suppose I can prove that

Do you admit just my last message or also the result about union of numerous events?

both of them. I will think on them

nice questions especially for one who start leaning probability

Ok, the next step is to generalize further, if we group our set of mutually independent events in multiple disjoint union of events, then these events are mutually independent

disjoint?

Yes, if we group like this :AUB and AUC, this will not work

Each union of events must be on distinct events

how you gonna make them disjoint? can you write it explicitly, I mean your proposition?

Be the union of independent events are not necessarily disjoint, I badly worded my phrase

can you write explicitly please.

Let $E = \{A_i, i=1, ...,n\}$ be a set of mutually independent events. Lets $S_1, S_2, ..., S_k$ be a partition of $E$. Then we want to show that $\{ \bigcup_{i\in S_j} A_i, j=1, ..., k\}$ are mutually independent events.

Sorry, $\{ \bigcup_{A \in S_j} A, j=1, ..., k\}$

hmm. is it related with your previous statement? I mean this

Now, Let $\{A_i, i=1,...n\}\bigcup \{B_i, i=1,...m\} be a set of mutually independent events. Can you show that $\bigcup_i A_i$ and $\bigcup_i B_i$ are independent ?

Yes, my previous statement is equivalent when $k=2$

i do not know how to prove but any hint?

is it complicated?

I think we can do it as an induction using the proof of the previous statement (that you admitted)

what you mean by previous statement? we had a lot of them)

I'll think on this ok?

ok

what is the next step?

Then all you need to realize is that the B_i are built as unions upon a partition of the $C_{i,j}$

I which means that all B_i's are mutually independent?

exactly

but in order to conclude that those B_i's should be disjoint right?

But are they disjoint?

I mean can some common C_{(i,j)} be in both say B_k and B_l

No, because C_{i,j} only appear in B_i

So the B_i partition the C_{i,j}

I think that I understand the general idea but I really need to prove those statements in order to understand it perfectly

If I have any questions related with this topic can I ask you here in the chat?

but it wont happen today

Yes, but I will not be here tomorrow

But later yes

Great!

in each problem do we need to do it again and again?

No, once you understand the intuition of independent events, you can directly state that the B_i are independent (The only thing your really need to show is that the B_i do not share common edges)

you are good, really good

in math

i need to admit that

Thanks, thank you for you patience with me and your assiduity

Thanks a lot! I will solve all that! If smth happend I will let you know ok?

I hightly appreciate it!

Take care! Good night!