Math Is Fun Forum

Festisio1

Guest

[Discrete Math] Finals review problems in Probability

There are a couple of problems which even the discussion board on our University website has not answered:

A variation of the birthday problem:
Find the smallest number of people you need to choose at random so that the probability that at least two of them were both born on April 1 exceeds 1/2.

Suppose that the probability that x is in a list of n distinct integers is 2/3 and that it is equally likely that x equals any element in the list. Find the average number of comparisons used by the linear search algorithm to find x or to determine that it is not in the list.

Times like this, I wish i had the student solutions guide

anonimnystefy

Real Member

From: Harlan's World

Registered: 2011-05-23

Posts: 16,049

Re: [Discrete Math] Finals review problems in Probability

Hi

I am getting

for the first problem and

for the second problem.

Last edited by anonimnystefy (2012-12-13 09:01:01)

---

“Here lies the reader who will never open this book. He is forever dead.
“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment
The knowledge of some things as a function of age is a delta function.

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: [Discrete Math] Finals review problems in Probability

Hi Festisio1;

A variation of the birthday problem:
Find the smallest number of people you need to choose at random so that the probability that at least two of them were both born on April 1 exceeds 1/2.

Assuming 365 days ( a non leap year ) you would need 253 people.

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

anonimnystefy

Real Member

From: Harlan's World

Registered: 2011-05-23

Posts: 16,049

Re: [Discrete Math] Finals review problems in Probability

Hi bobbym

They would need 613.

Last edited by anonimnystefy (2012-12-13 09:00:39)

---

“Here lies the reader who will never open this book. He is forever dead.
“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment
The knowledge of some things as a function of age is a delta function.

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: [Discrete Math] Finals review problems in Probability

Hi;

Not for a 365 day year.

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

anonimnystefy

Real Member

From: Harlan's World

Registered: 2011-05-23

Posts: 16,049

Re: [Discrete Math] Finals review problems in Probability

The probability that less than 2 people have their birthdays on April 1st is (364/365)^n+n*1/365*(364/365)^(n-1). This probability needs to be less than or equal to 1/2.

---

“Here lies the reader who will never open this book. He is forever dead.
“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment
The knowledge of some things as a function of age is a delta function.

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: [Discrete Math] Finals review problems in Probability

The probability of having the birthday April 1 is 1 / 365. The probability than n people do not have that birthday is

So solve:

n = 252.65 which is rounded to 253.

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

anonimnystefy

Real Member

From: Harlan's World

Registered: 2011-05-23

Posts: 16,049

Re: [Discrete Math] Finals review problems in Probability

You are not reading the question!

---

“Here lies the reader who will never open this book. He is forever dead.
“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment
The knowledge of some things as a function of age is a delta function.

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: [Discrete Math] Finals review problems in Probability

Hi;

You are not reading the question!

You are right we are both not reading the question. The answer is 613.

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

anonimnystefy

Real Member

From: Harlan's World

Registered: 2011-05-23

Posts: 16,049

Re: [Discrete Math] Finals review problems in Probability

Well, the expected number of people for two birthdays on the 1st of April cannot be less than for one birthday.

---

“Here lies the reader who will never open this book. He is forever dead.
“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment
The knowledge of some things as a function of age is a delta function.

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: [Discrete Math] Finals review problems in Probability

Hi;

You changed your answer to 613. So did I! That is correct.

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

anonimnystefy

Real Member

From: Harlan's World

Registered: 2011-05-23

Posts: 16,049

Re: [Discrete Math] Finals review problems in Probability

Now it's okay. Though I changed it 25 minutes ago, and you didn't notice...

---

“Here lies the reader who will never open this book. He is forever dead.
“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment
The knowledge of some things as a function of age is a delta function.

Festisio

Member

Registered: 2012-12-13

Posts: 5

Re: [Discrete Math] Finals review problems in Probability

For the birthday problem -- the book answer is 614 (book assumes 366 days a year)

I want to understand how to complete the problem.. the basic birthday concept, no prob -- but this variation is a little tough.

For the other problem, the book answer is

I have sheets and sheets of paper -- but I am not getting close -- I hate looking at the answer first, because I try to understand the concepts of obtaining them.. in these cases I could not find them

There again, I have been studying for 3 finals, which are tonight, and two more tomorrow, so I may be a little tired and missing things.

Last edited by Festisio (2012-12-13 09:29:02)

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: [Discrete Math] Finals review problems in Probability

Hi;

Yes, it is 614 for a leap year. It is not a birthday problem it is a binomial distribution problem.

That equation must be solved.

Hi anonimnystefy;

I was working on the problem so I did not notice.

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

anonimnystefy

Real Member

From: Harlan's World

Registered: 2011-05-23

Posts: 16,049

Re: [Discrete Math] Finals review problems in Probability

Well, for the second problem, the book is wrong.

---

“Here lies the reader who will never open this book. He is forever dead.
“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment
The knowledge of some things as a function of age is a delta function.

Festisio

Member

Registered: 2012-12-13

Posts: 5

Re: [Discrete Math] Finals review problems in Probability

Well, for the second problem, the book is wrong.

It would not be the first time -- it is Prob 7.4 #9 from Discrete Math (rosen 7th ed)

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: [Discrete Math] Finals review problems in Probability

Hi Festisio;

Discrete Math and its Applications?

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Festisio

Member

Registered: 2012-12-13

Posts: 5

Re: [Discrete Math] Finals review problems in Probability

Hi Festisio;

Discrete Math and its Applications?

Yes, that's correct.

McGraw has the 6th ed online here: http://highered.mcgraw-hill.com/sites/dl/free/0070648247/510610/Chapter_06_Discrete_Probability.pdf

It is page 440 #9 on there  I don't know if they have the matching solutions.. but I am using the 7th edition..

Last edited by Festisio (2012-12-13 10:05:16)

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: [Discrete Math] Finals review problems in Probability

Hi;

For the 2nd problem I am getting

also.

I have sheets and sheets of paper -- but I am not getting close

I do not know about the 7th edition but the 6th edition has the answer to this problem just a few pages away!

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Festisio

Member

Registered: 2012-12-13

Posts: 5

Re: [Discrete Math] Finals review problems in Probability

Hi;

For the 2nd problem I am getting

also.

I have sheets and sheets of paper -- but I am not getting close

I do not know about the 7th edition but the 6th edition has the answer to this problem just a few pages away!

I'm not understanding their examples.. I had to find help on Bayes' from youtube -- book does not even mention using a tree to simplify things..

Final is cumulative - no notes/calc anything .. there is just a vast amount of material. This last chaper (7) was basically assigned to us for finals week.. which means that we didn't really cover it.

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: [Discrete Math] Finals review problems in Probability

Hi;

Do you see example 8, entitled average case complexity of the linear search algorithm?

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Festisio

Member

Registered: 2012-12-13

Posts: 5

Re: [Discrete Math] Finals review problems in Probability

Hi;

Do you see example 8, entitled average case complexity of the linear search algorithm?

Yes,

The calculation they use.. it makes a bunch of assumptions.. they are based on prior proofs..

anonimnystefy

Real Member

From: Harlan's World

Registered: 2011-05-23

Posts: 16,049

Re: [Discrete Math] Finals review problems in Probability

Hi;

For the 2nd problem I am getting

also.

I have sheets and sheets of paper -- but I am not getting close

I do not know about the 7th edition but the 6th edition has the answer to this problem just a few pages away!

How are you getting (4n+6)/3?

---

“Here lies the reader who will never open this book. He is forever dead.
“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment
The knowledge of some things as a function of age is a delta function.

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: [Discrete Math] Finals review problems in Probability

Hi;

I am sorry, I am involved in forum matters and can not get to all the posts as quickly.

He has a derivation just 8 pages away from the question and it gives a formula.

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

anonimnystefy

Real Member

From: Harlan's World

Registered: 2011-05-23

Posts: 16,049

Re: [Discrete Math] Finals review problems in Probability

On which page is that?

---

“Here lies the reader who will never open this book. He is forever dead.
“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment
The knowledge of some things as a function of age is a delta function.