Probability Study Notes
To: Professor Mr. XiaoWen Zhou
Re: a couple of questions in your class.
Hi,
I am one of your student in course STAT249(Probability), and want to thank you in advance for your time to
look into my mail.
1. Regarding your question in class: P{There is the birthday of some one in the class today.(no. of
students =50 }
I gave the wrong of 50/365. I think the correct one should be that the "complement of there is no single
birthday in the class today", which is 1- (364/365)X(364/365)...==1-((364/365)power 50) == 0.1281
Is it right?
2. Regarding my question about the 3 conditions of "probability of events":
A. P(A) >=0 for any A belongs to S;
B. P(S) = 1;
C. if A1, A2, A3... is finite or infinite mutually exclusive events of S, then
P{A1UA2UA3...} = P{A1} + P{A2} + P{A3} +...
And in the class I asked you the question that is it true that A1+A2+A3+... == S, and you said not necessary,
then I have figured out following conclusion:
Suppose A1, A2, A3... are all possible mutually exclusive events in S, then
P{A1} + P{A2} + P{A3}... == P{S} = 1;
The following is my proof:
suppose event X belongs to S and does not belong to collection of {A1, A2, A3...}, then according to
assumption that {A1, A2, A3...} are all possible mutual exclusive events in S, we can get that X cannot occur
independently from any of {A1, A2, A3...} , otherwise if X occur alone means that X is another mutually
exclusive event which is not within collection of {A1, A2, A3...}. And this is contradictive to our
assumption.
So, whenever X occurs there must be one exact event from {A1, A2, A3...}, then we can say that the
probability of X is included in P{A1, A2, A3...}. As we just select X in general from "complement of {A1, A2,
A3...} ", we can say that the collection of "complement of {A1, A2, A3...}" have the same characteristics like
X. Then the probability of all elements are included in P{A1, A2, A3...} . Therefore,
P{S} = P{A1, A2, A3...} =1. proved.
Is above proof correct?
Let's define propositional function P(x) and Q(x), and a certain logic operation L which involves two
propositional function and the result is true if and only if the truth value of two propositional function have
a certain pattern, of which the sequence of two propositional function matters.
Say the all possible combination pattern of truth of two propositional function is like following:
P(x) Q(x)
T T (1)
T F (2)
F T (3)
F F (4)
The pattern of truth combination becomes a simple combination problem.
Say c(4,0)=1 , c(4,1)=4, c(4,2)=6, c(4,3)=4, c(4,4)=1 ===> There are total 16! and it is from binomial.
This is the essence of world! And I presume that God is describing and constructing world with this as language
and tool. However, human can only understand a few characters of them, that is logic----see below:
Let's define (1),(2),(3),(4) as logical results of the logical operation L
Pattern 1: (1)=T, (2),(3),(4) = F This is logic AND.
Pattern 2: (1),(2),(3) = T (4) = F This is logic OR
Pattern 3: (1),(3),(4) = T (2) = F this is IMPLY
Pattern 4: (1),(4) = F (2),(3)=T this is EXCLUSIVE OR
...
Among 16 patterns, how many of them are we giving serious study? Only about half of them, I guess.
Why? "We must know. We shall know."
Hi professor, Sorry to disturb your vacation.
I am taking comp239 now and I don't know why Mr. Rosen does not use a more practical and easy way to justify a
tree by counting the number of edges e and number of vertices v. If e = v-1 then it is a tree, if e=v, it has
a circuit,it is not a tree.
By definition, a tree is a connected undirected graph with no simple circuits. Then how to justify?
On text book, p633, there is a theorem:
An undirected graph is a tree if and only if there is a simple unique path between any two of its vertices.
However, it is not a very practical theorem, since you have to verify all pairs of vertices to see if there is a
simple path, and what's more, it is the only simple path. Is it easy? Definitely no. It is more like a definition.
I found a easier way to justify if a connected undirected graph is a tree or not. Or in other words, if there
is any simple circuit or not.
A connected undirected graph is a tree if and only if the number of vertices v and number of edges e has such
relation: e = v-1.
proof:
A connected undirected graph is a tree, if and only if there is no circuit in it. That means the total region
made by the graph is one. According to Euler formula r = e - v + 2 we get
e = v -1
Q.E.D.
A more wild thought is that a tree is simply the transitive closure of certain relation of all vertices.
Let's define each edge (u,v) is under a certain relation R, that is (u,v) in R or in other words, R is a relation
on all vertices set V={v1,v2,v3...vn}. Then the connected graph G=(V,E) is the transitive closure of R.
According to Lemma1 on p501, the path between vertex u to v is at most n and moreover, when u is different from
v, the length of path is at most n-1. That means when the path is not a circuit, the length of path cannot
exceed n-1. Of course it is quite a trivial fact, but still I think it is quite practical. And I cannot help it. Thank you for your time. Nick Huang
Hi Professor,
Sorry to disturb you again.
I went to attend a lecture in Concordia last week, given by a professor from "Rice University". His topic was
related to logic. It is said that the three foundations of logic---"consistency, completeness and decidable"
was overthrown. For "inconsistency" of logic, he gave an example of self-contradictive proposition:
"There is no universal truth."
He explained about this paradox as that if it is true, then there is no universal truth implies it is false.
And if it is false, then there is universal truth, it must be true.
I tried very hard to disbelieve him by attempting to prove it is not self-contradictive. I think the biggest
problem is the definition of "Universal Truth", which must be strictly defined before all. The following is my
understanding:
First I define "universal truth" as a propositional function U(x) such that for all x, U(x) is true. Then the
proposition "there is no universal truth" becomes "for all propositional functions, it is not the case that
there exists a propositional function U(x) such that for all x U(x) is always true." And we know this proposition
is false because we actually can find such proposition like "for all x that x=x" etc.
Since the proposition "there is no universal truth" is a false proposition, we won't bother ourselves with
so-called "self-contradictive", right? Because "there indeed exists universal truth, however, not this one."
I simply cannot believe that logic is inconsistency as declared by that professor, but sometimes I think I am
clear, however, sometimes my mind is mixed up. Can you justify this?
Thank you for your time.
Qingzhe Huang
Question: Find the recursive relation of number of strictly increasing of positive integers that has 1 as
its first term and n as its last term where n is a positive integer.
Original solution (from author):
Let S(n) be the number of such sequences. A sequence ending with n must consist all
sequences that end in something less than n followed by n as its last term. So,
S(n) = S(1) + S(2) + ...+ S(n-1) where S(1) = 1 and n>=2 (1)
My solution:
Let S(n) be the number of such sequences. Then S(n) = 2xS(n-1) where S(1)=1 and n>=2 (2)
proof: Let P(n) be the set of all sequences of strictly increasing that has 1 as its first term and n as
last term. Then every element in P(n+1) can have number n as one of its term or not.
Case 1: Suppose elements in P(n+1) do have n as one of its term, then the sequences are all the sequences
in P(n) followed with n+1 as its last term. So the number is |P(n)|= S(n).
Case 2: Suppose elements in P(n+1) do not have "n" as one of its term, then the sequences are all the
sequences in P(n) without n and followed with n+1 as its last term. And the number of sequences is
still |P(n)|=S(n). Because we get the sequence by removing the last term which is "n".
So, |P(n)| = 2x|P(n-1)| or in term of S(n) = 2xS(n-1)
You can verify that (1) and (2) are equal.