Bayes’ Rule

First, I will state the rule with an applied example.

Problem Definition:  Computing the probability that a message containing a given word is spam.

probability Terminologies:

  1. p(S|W): is the probability that a message is a spam, knowing that the word “replica” is in it.
  2. p(S):  is the probability that any given message is spam.
  3. p(W|S): is the probability that the word “replica” appears in spam messages.
  4. p(H): is the overall probability that any given message is not spam.
  5. p(W|H): is the probability that the word “replica” appears in not spam messages.

The formula used by the software derived from Bayes’ theorem.

p(S|W) = p(W|S) . p(S)    OVER    p(W|S) . p(S) + p(W|H) . p(H)

Q: The Question is: How did you get to this Conclusion ?

A: Let’s check the conditional Probability rule with an example, First.

Example:  we have two fair coins the probability of tossing theses coins is distributed like this

First Coin Second Coin Probability
H H 1/4
H T 1/4
T H 1/4
T T 1/4

1- p(Two Heads) = p(HH).

2- p(at Least one Head) = p(HH) + p(HT) + p(TH).

Now this Question is the conditional Probability:

what is the probability of getting a Head given we already have one of the two coins is head. this question has changed the sample Space.

Note:  in the previous two questions the sample space was the whole possible set of events, but now i’m telling you your new sample space is formed only from the combinations with at least coin with one head. the Count of the sample space is {HH, HT, TH}.

Then  p(H| we already have a head) = 1/3  only one possible way which is HH.

The Conditional Probability Rule:

p(A|B) =  p(A and B) OVER   p(B)

Let’s prove it using simple combinatories

  • p(A and B) = number of occurences of Both Events A and B / The Sample space.
  • p(B) =  number of occurences of Event B / The Sample Space.

 

Remeber  Conditional probability Calculates the number of occurences of event A given that Event B is also occured which is the intersection of the Two events [number of occurences of Both A and B] over the changing of the sample space to the number of occurences of event B.

Calculating  Our rule above gives the desired results.

The End, Math is Fun and Pure the moment you try hard to get what it wants to it will always accept you will never be dishonest to you. It’s only impossible when you decides to.

Advertisements

Walking the Grid

A famous problem in Combinatorics and Programming contests ICPC style is the given problem.

Problem:
Given a grid with dimensions N x N show how many ways can we move
from point A to point B.

(Hint: only possible moves is to the East and North).


solution:
we will try to enumerate all possible paths, but this method will
prove it’s no worthy when N gets Large so it can be solved by using
Dynamic programming technique where sub-states are saved in two
dimension array representing the grid positions in order O(N^2).

but the challenge here is how to solve it faster and how to employee the
techniques of combinatorics ?.

A closer Look:
let’s look at our graph for example, we know that at maximum
there is N moves to the North and N to the East. so we can represent
our moves in form of string of length (N+N) for example a possible move:

N-N-E-E-N-N-E-E : move to the north two times then two times east
then two for the north and last two moves to
the east.

now we can solve the problem by choosing from 2*N possible positions
N for the East and the rest for the north using the law of combinations

C(2*N, N) * C(N, N) = total possible ways.

Note:
If it isn’t a square grid, then result = C(n + m, n)*C(m, m),
where n and m are the size of height and width.

Reference:
-AoPs Video Lecture (chapter 5: Counting Paths on a Grid).

Telescoping series in Algorithm analysis

Telescoping Series is famous kind of series occurring in mathematics,
here it will be used to get an algorithm bounds analysis of a recursion defined algorithms( i.e. merge-sort, quick-sort,…).

Example 1:

given recurrence equation : T( N ) = 2.T( N/2 ) + N

solution :
T( N ) = 2.T( N/2 ) + N “divide equation by N”
T( N ) / N = T( N/2 ) / ( N/2 ) + 1

“Next call”
T( N/2 ) = 2.T( N/4 ) + N/2 “divide by N/2”
T( N/2 ) / ( N/2 ) = T( N/4 ) / ( N/4 ) + 1

at last we will have the given picture below.

Then Last Step, summing all these equations we will find that each
term on left hand of the preceding equation neglects the next term
on the right hand side of the next recursive call equation giving in the
end the equation.

T( N )/( N ) = T(1) + log N
T( N ) = N.T(1) + N.logN = O(N.log N).

Reference :
Data Structures and Problem Solving Using C++ by Mark A. Weiss

Pascal’s Triangle

After looking at the Binomial Theorem we will introduce Pascal’s important rule.

Pascal’s Triangle :
He stated that if we choose a certain row  ‘k’  we can get the next row
‘k+1’ by making the two boundaries of this new row equals ‘1’ and
for each item between two items of the upper row the new row item
equals their addition.

Rule :
n here is the new row and n-1 the previous one.

[image from wikipedia]

Usage :
Transferring heavy multiplication operations into simple
addition ones.

Prove :

you can use a simple algebra one but we will state pascal’s way to prove it.

“given a set T that contains the element ‘a’ we will define a new
set S = {T} – ‘a’,then, to choose k elements we have two ways
now either to take the k elements from S or to choose element
‘a’ with k-1 elements from S.  which concludes the upper rule”.

That’s all we know, hope it’s simple and straight forward one.

Thanks for Reading 🙂

Binomial Theorem

*Starting the topic with a very simple Question :


Example 1:
Given : (a*x + b*y) ^ 67
what is the Coefficient of the term (x^5)*(y^62) in the power expansion ?.

To solve this problem we will start with a simpler one to get an idea of the solution.

Example 2:
Given : ( x + y )^3
what is the Coefficient of the all possible terms of the expansion ?.

Solution :

( x + y )^3 = ( x + y ).( x + y ).( x + y )
= x^3 + 3.( x^2 ).( y ) + 3.( x ).( y^2 ) + y^3

‘Notice the pattern in our solution’.
1- to get x^3 =’ How many Ways can I choose x three times ? ‘ so that I can get x^3
the answer is the Binomial Coefficient(combination) C(3, 3) = 1

2- (x^2) . y  = ‘ How many ways can I choose x two times ?’
= C(3, 2)
=3

3- (x) . ( y^2) = ‘How many ways can I choose x one time only ?’
= C(3, 1)
=3

4- y^3  = ‘How many ways not to choose x ?’
= ‘How many ways to choose only y ?’
= exactly one way
= C(3, 0)

Since we have in our expansion ‘3’ candidates to choose a variable from them ( either x or y ) the total sum of the powers each variable of our expansion must equals to 3.

The no. of ways to choose each time our variables is solved using Combination since each time we choose the order of choice is considered the same (I.e choosing the first x from the first bracket and then the second bracket is the same as choosing the first x from the second bracket and then the first) our ways of choosing is independent to position.

Theorem 1:
(x + y) ^ n = Summation from j = 0 → n
C( n, n-j) . ( x ^ (n-j) ) . ( y ^ j )

The End, here we will end our talking for now, but I haven’t answered the first Question. Why don’t you try to 😀 ?.

We’re back with a conjecture :D!

Hellooooo :D,

It’s been a very looong time of course :),

In this post we’ll talk about the meaning of a conjecture, and will give an example on it,

Of course our reference is the discrete text for Rosen,

Ok, let’s begin,

A conjecture is a statement that is being proposed to be a true statement, usually on the basis of some partial evidence, a heuristic argument, or the intuition of an expert.

When a proof of a conjecture is found, the conjecture becomes a theorem. Many times conjectures are shown to be false, so they are not theorems.

No matter how a conjecture was made, once it has been formulated, the goal is to prove or disprove it.

When mathematicians believe that a conjecture may be true, they try to find a proof. If they can’t find a proof, they may look for a counterexample(substitution of variables in the mathematical argument with some values that proves that the conjecture is not true). When they cannot find a counterexample, they may switch gears and once again try to prove the conjecture.

Although many conjectures are quickly settled, a few conjectures resist attack for hundreds of years and lead to the development of new parts of mathematics(What :D??!!!).

An example :),

Formulate a conjecture about the decimal digits that occur as the final digit of the square of an integer and prove your result.

Solution:

The smallest perfect squares are 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 255, and so on.

We notice that the digits that occur as the final digit of a square are 0, 1, 4, 5, 6, and 9, with 2, 3, 7, and 8 never appearing as the final digit of a square.

We conjecture this theorem: The final decimal digit of a perfect square is 0, 1, 4, 5, 6, or 9. How can we prove this theorem?

We first note that we can express an integer n as 10a + b(the bullet is shot from here :D), where a and b are positive integers and b is 0, 1, 2, 3, 4, 5, 6, 7, 8, or 9. Here a is the integer obtained by subtracting the final decimal digit of n from n and dividing by 10. Next, note that (10a + b)^2 = 100(a^2) + 20ab + b^2 = 10(10(a^2) + 2ab) + b^2, so that the final decimal digit of n^2 is the same as the final decimal digit of b^2.

Furthermore, note that the final decimal digit of b^2 is the same as the final decimal digit of (10 – b)^2(as the reader can verify ;)).

Consequently, we can reduce our poof to the consideration of six cases.

Case (1). The final digit of n is 1 or 9. Then the final decimal digit of n^2 is the final decimal digit of 1^2 = 1 or 9^2 = 81, namely, 1.

Case (2). The final digit of n is 2 or 8. Then the final decimal digit of n^2 is the final decimal digit of 2^2 = 4 or 8^2 = 64, namely, 4.

Case (3). The final digit of n is 3 or 7. Then the final decimal digit of n^2 is the final decimal digit of 3^2 = 9 or 7^2 = 49, namely, 9.

Case (4). The final digit of n is 4 or 6. Then the final decimal digit of n^2 is the final decimal digit of 4^2 = 16 or 6^2 = 36, namely, 6.

Case (5). The final decimal digit of n is 5. Then the final decimal digit of n^2 is the final decimal digit of 5^2 = 25, namely, 5.

Case (6). The final decimal digit of n is 0. Then the final decimal digit of n^2 is the final decimal digit of 0^2 = 0, namely, 0.

Because we have considered all six cases, we can conclude that the final decimal digit of n^2, where n is an integer is either 0, 1, 4, 5, 6, or 9.

I hope it was a useful post, if anything is not clear, just ask :)!

Get the primes [SOLVED]

السلام عليكم و رحمه الله و بركاته

Solution to First Problem :

http://mathschallenge.net/index.php?section=problems&show=true&titleid=fourth_power_plus_four_prime&full=true#solution

hope all of you enjoyed it 🙂 .

والله الموفق و المستعان

والسلام عليكم و رحمه الله و بركاته

Get the primes

السلا م عليكم و رحمه الله و بركاته

first problem post is taken from “mathschallenge” problem copyrights all reserved to the site.

ok let’s start with the problem :

given equation  n^4 +4 , get all natural numbers of  N that will give prime numbers.

Solution with prove will be posted after some days 😀 , Have Fun All wish you Luck.

والله الموفق و المستعان

والسلام عليكم ورحمه الله و بركاته

Hello world from SC Channel !!

السلام عليكم ورحمه الله و بركاته,

Hello everybody! :D,

Hope that everything is fine :),

This blog is owned by two SC Students (Scientific Computing Department If you don’t know what SC stands for :P),

#1 Feras Ahmed,

#2 Amr Saqr,

The idea behind creating this blog is the ultimate love to all things in the world that are related to Mathematics,

And our desire to learn as much as we can to enhance our thinking and problem solving abilities,

I and Feras will be studying from the book “Discrete Mathematics and Its Applications” by Kenneth H. Rosen,

And we are intending to share what we will learn with all of you,

InshaAllaah the plan is to pick some good problems from the book and write posts for them here in the blog with the solutions, mmmmm, what else ?!!,

maybe the problems we pick will also be from any site that contains problems, as long as it’s related to Maths,

Finally we hope that you will find our blog useful and educative,

Any suggestions are welcomed :).