Try our Free Online Math Solver!

Fundamental Computer Concepts of Informatics
Today:
Probabilistic Analysis
Geometric and Binomial Distributions
The Simplified Hiring Problem assumes:
• You are running a company and want to hire a better office assistant
• You don’t want to fire your current assistant until you know you have a better
assistant
• You ask an employment agency to send one candidate each day (n total
candidates)
• You make the decision whether or not to hire the new assistant and fire the
old assistant
immediately after interviewing the new candidate
• The cost to interview a candidate is c_{i}, and the cost to hire a new candidate
is c_{h} (where c_{h} >> c_{i})
Task: You want to know the expected cost of the process if you interview n candidates
Hire_Assistant(n)
Here, n is the # of candidates interviewed and m is the # of candidates hired
Total Cost:
(since is the the cost to interview n
candidates, we are more interested in which
varies
according to how many people are hired)
Worstcase:
(every new candidate is better than previous assistant )
We want to analyze the expected m ( number of candidates hired)
• Assume the candidates arrive in random order
• Define a random variable X which indicates the number of assistants hired
during the process
(but this is somewhat difficult to calculate since the order of candidates must be known apriori)
So, let’s define an indicator random variable Xi
associated with the event in which the ith
candidate is hired
X_{i} = I {candidate i is hired} =
and
taking the expectation of both sides we have,
we also know
so
(i.e. sum of a harmonic series)
Therefore the expected cost of hiring a candidate is :
The Birthday Paradox
Task: Anticipate how many people must there be in a
room such that the expected number of pairs of
people that have the same birth month and day is at least 1
Assumptions:
• Ignore leap years for simplicity
• Index the people in the room from 1 to k
• Assume people are equally likely to have their birthdays on any day of the
year
• Let b_{i} be the birthday of the ith person
Since birthdays are assumed to be independent of each
other, the probability that two people (i and j) have
birthdays is:
where
therefore
We will define the indicator random variable X_{ij}:
so
let X be the random variable that counts the pairs of people with the same birthday
Taking the expectation of both sides
using the quadratic formula
When, so
Geometric and Binomial Distributions
Bernouli Trial  an experiment with only 2 possible
outcomes
• P(success): p
• P(failure): q = 1  p
We want to consider multiple Bernouli trials, and we
assume that each repeat of the trial is independent
from the previous trial .
For example: roll a die, where only a 6 is considered a success
Geometric Distribution : what is the probability that the first success occurs in the kth trial?
So,
To find the expectation of distribution, assuming q < 1
Sample geometric distribution
Binomial Distribution : how many successes occur during n Bernouli trials?
P(success) = p
P(failure) = q = 1  p
So,
and
and
Sample binomial distribution
Prev  Next 