Question

Question about probability

Answer 1

Consider the below event :
A : Not getting called by teacher for all "n" questions

Answer 2

And look at a prticular student,
whats P(A) for a particular student ?

Answer 3

uhm, (1/n)^n ?

Answer 4

nope, thats the probability for getting called in all questions
try again

Answer 5

hmm, (1-(1/n))^n?

Answer 6

yes, you could also work it like this :

when the teacher asks a question, n-1 students are not getting called
so number of ways in which a student is not called = n-1
total students = n

so probability for not getting called for a particular question = (n-1)/n

Answer 7

probability for not getting called for all n questions = ((n-1)/n)^n

Answer 8

that is same as the answer you got

Answer 9

but we want to find the expected number of students not getting called

not the probability

Answer 10

simply multiply above probability by "n" to get the expected value

Answer 11

wait, so that means we're multiplying the probability that a student never gets called on, by the number of students to get teh expected # of students that never get called?

Answer 12

not quite

Answer 13

and how does that incorporate linearity of expectations?

Answer 14

for a particular student, the probability that he is never called in all n questions is ((n-1)/n)^n

the expected value is simply 1* ((n-1)/n)^n


by lnearity, the overalll expected value equals the sum of the individual expected values :

1* ((n-1)/n)^n + 1* ((n-1)/n)^n + .... + 1* ((n-1)/n)^n

Answer 15

there are "n" terms in above sum

Answer 16

therefore the expected value is n*((n-1)/n)^n

Answer 17

if that makes any sense...
i got that by a quick read from
http://www.cse.iitd.ac.in/~mohanty/col106/Resources/linearity_expectation.pdf

Answer 18

OOO! yes yes that makes sense!

Answer 19

look at Theorem2.5 in above link

Answer 20

You're adding up the individual probaility of each student.

Answer 21

I am adding up the individual expected values, not probability

Answer 22

they both turn out to be same in our case though

Answer 23

Is there a way to write our answer in that format given in that link?

Answer 24

Theorem2.5 is identical to our problem
just put \(m=n\)

Answer 25

ball = question

bin = student

Answer 26

OO! yes yes, didnt ctach the bottom part.

Answer 27

and for part b, i'm thinking that

Answer 28

wouldn't it just be that n/2 vertices in R, so there is 1 / (n/2) possibilities that a vertex in R is connected to one in L?

Answer 29

I think the expected number of edges should be m/4

Answer 30

we're given that the graph has "m" edges

consider the vertices of one edge

Answer 31

Just wanted to ask if that's what you'd expect.

Answer 32

that is a surprising result indeed! id like to double check... after this..

Answer 33

mhmm, ok, so we have 2 vertices, and they'd both be in L or R.

Answer 34

thank yU!

Answer 35

whats the probability for those two vertices to be in different bins ?

Answer 36

1/2

Answer 37

both vertices cannot be in L
both vertices cannot be in R

Answer 38

if one vertex is in L, then other vertex must be in R

Answer 39

wait isn't that only defined to be a cut? not the actual edge?

Answer 40

cause an edge can be formed between ANY two vertices and only a cut is defined as the edges between L and R right?

Answer 41

there are "m" edges in the graph
it is a given

Answer 42

we're not creating any "new" edges between L and R

Answer 43

we're only checking if an edge already exists between L and R

Answer 44

if it exists, then we put that edge in "cut"

Answer 45

If it helps, consider an analogy

Answer 46

Mhmm, and how owuld I proceed with that?

Answer 47

take the graph of students in your class

Answer 48

each student is a vertex

an edge exists between two students if they are friends

Answer 49

Now, partition the students randomly : L , R

Answer 50

next look at the partition and pick students in L who have friends in R

Answer 51

that is only an analogy