Math Is Fun Forum

sam123

Guest

probability/group theory

Hi guys, just a question from an old crpytography exam im having troubles with, thanks for the help=)

Let G be a finite cyclic group and let g be a generator for G. Suppose |G|=12.

Six elements of G are chosen at random (with replacement). (i)Find the probability that at least one is a generator.
(ii)Show that the probability that two or more are the same is at least 0.77

(i) P(at least 1 generator) = 1 - P(not getting a generator)
                                      = 1-(2/3)^6
                                      = 0.912

(ii) Really need help with this thanks!

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: probability/group theory

Hi sam123;

(i) Is correct.

(ii) The generators are {1,5,7,11} so they are 1 / 3. Just as you figured above. So I am getting

as the chance when picking 6 with replacement that 2 or more generators are among them.
This is about 65% which is what I am getting with a computer simulation. This does not prove that
it is at least .77 Where am I going wrong?

---

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.

sam123

Guest

Re: probability/group theory

Hey, the answer is actually quite simple(i think)

Prob that 6 elements are different = 11/12 * 10/12 * 9/12 * 8/12 * 7/12 = 0.2228009
Prob. that 2 or more are same = 1-0.2228009
                                             = 0.7771991 (which is atleast 0.77)

I hope this is right?!

cheers

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: probability/group theory

H i sam123;

First of all it appears I am solving the wrong problem for ii). I thought you wanted 2 or more generators among the six. For example one pick might be {1,5,9,9,9,10}. You just wanted 2 of the same. Sorry for the confusion.

Your method

1-0.2228009 = 0.7771991

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.

sam123

Guest

Re: probability/group theory

Yeah, me and you alike bobby, oh well =/

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: probability/group theory

Hi;

Yes, every once in awhile I do not read the problem and try to solve it anyway.
It sure is exhilarating to do all the work on the wrong problem.
Sort of like driving in the wrong direction.

---

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.