in Programming in C
523 views
3 votes
3 votes

in Programming in C
523 views

1 comment

0
0

3 Answers

3 votes
3 votes
Best answer

There are 2 possibilities :

a) We have 2 chains ; one of length 3 and another of length 1 ..

For this we select 1 slot out of the 8 slots for the 3 keys and the one key remaining can be placed in one of remaining 7 blocks..But the keys which are being chosen to form a chain of 3 also matters..

So probability of doing so  : 8C1 * 4C1 * (1/8)3 * (7/8)

                                    =   8 * 4 * 7 / (84)

                                    =   28 / 83

b) We have only one chain of length 4 :

So probability of doing so :  8 * (1/8)4  [As we can have 4 keys into any of the 8 slots , so we are multiplying by 8]

                                   =    1 / 83

Therefore P(at least a chain of size 3)  =  28 / 83 + 1 / 83

                                                          =   29 / 83

                                                                             =   29 / 512

                                                          =   0.057 (correct to 3 decimal places)

edited by

4 Comments

i think it should be 8c3 for the three keys and 8c4 for the four keys so it should be this  

8c3*(1/83)*(7/8)+ 8c3*(1/84) right?

0
0
No it is not like that.. There are 8 slots and we can choose anyone one slot for 3 keys and 1 key can be placed in one of remaining 7 slots..

And second possibility is to select one of 8 slots and place all the 4 keys there..
0
0
1
1
@habib mistake done by you is,
there are 4 possibilities of forming a chain of length 3.
1,2,3 in same slot, 4 in diff slot,
1,3,4 in same slot 2 in diff slot
2,3,4 in same slot, 1 in diff slot
1,2,4 in same slot 3 in diff slot.
it means 4C1 * 8C1 * (1/8)^3*(7/8) shud be the possibility of forming chain of length 3
1
1
2 votes
2 votes

Two cases are there: 

case 1: probability of exactly 3 length chain
$P(X=3) =$ pick a slot $\times$ place 3 keys in that slot
$= 8 \times. ^{4}\textrm{C}_1 \left ( \frac{1}{8} \right )^3 \left ( \frac{7}{8} \right )$ 
$= 8 \times 4 \times \left ( \frac{1}{8} \right )^3 \left ( \frac{7}{8} \right )$
$= \frac{28}{8^3}$

case 2: probability of exactly 4 length chain
$P(X=4) =$ pick a slot $\times$ place 4 keys in that slot
$= 8 \times \left ( \frac{1}{8} \right )^4$ 
$= \frac{1}{8^3}$

so req. probability $= \frac{28}{8^3} + \frac{1}{8^3} = \frac{29}{8^3}$  = 0.0566

0 votes
0 votes
the probability that exactly k keys hash to a particular slot is given by 
= (1/n)^k (1 -1/n)^(n-k) (n choose k)

reference: https://www.ics.uci.edu/~eppstein/261/f11-hw2-soln.txt 2.a

so it will be for three keys hash to a particular slot will be  8C3*(1/8)* (7/8)5 +8C4*(1/8)4 *(7/8)4

edited by
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true