MA2102

Probability and Statistics

Lecture-6

Say there is a school with $n$ students and you are asked to write a (database)software to maintain student records, and one should be able to retrieve student record quickly(almost in constant time) using your software. To achieve that fast access you should be using data structure called Hash table to store student records. Hash tables are array like data structures in which particular record gets stored in at particular index which is determined through hashing using some hash function. Here is process of getting index of record. Fist we feed key of the record to hash function which spits the number called hash code then this hash code may be converted to index(by taking modulo of size of array so that index fall in the range of array indices).

Suppose our keys are tuple (FullName,DOB). Say the following hash functions is in your mind;

(Name,DOB)$\overset{hash function}{\rightarrow}$ $d$ where $d$ is day of the years i.e $d\in\{1,2,3,...365\}$(Assuming nobody born in leap year)


So our hash function maps student keys to {1,2,...,365}. This hash code can be used as index to store records in hash table. One problem with hashing is collisions (two students may have born on the same day of the year), one way to deal with collisions is chaining(keeping the linked list of records(instead of single record) who have born on same day of the year at their corresponding index). Let us assume that our hash function uniformly distribute keys over set of index values{1,2,...,365} so that we will not have clusters. Still we would like to have less collisions to reduce the average time to retrieve a record. For that we can't use too many students records to store in the hash table as we have only 365 slots in this set up. And less than 365 students doesn't mean that we will not have any collisions though our hash function uniformly distribute the keys over indices, But we can feel that more students we have more chances of collisions (so more number of collisions) that will increase average time to retrieve a record. But What is the trade-off between the number of students that we can store and probability of collision in the hash table?

Birthday Problem(Paradox):

If $n$ people are present in a room. What is the probability at least two of them celebrate birthday on the same day of the year

solution : Let us assume nobody born on leap year.
case i: $n>365$
In this case the probability at least two people having same birthday is 1 ($\because$ Pigeon hole principle)
case ii: $n\le 365$
Let us assume that a person could be born any day of the year with same probability( It is not true as there are seasonal effects, that means in some seasons more marriages takes place,so after nine months of that season more babies are born) But with this equally likely assumption the problem will become easy and the answer we get also very reasonable to reality.
Let us observe birthdays (DD/MM only) of a random class with n people.
Sample space $\Omega=\{b_{1}b_{2}b_{3}...b_{n}:b_{i}\in \{1,2,3...365\}\}$
(Here 1:= 0/1/01, 2:= 02/01,.....365:=31/12)
$|\Omega|=365^{n}$ ($\because$ outcomes in $\Omega$ are n-permutation of 365 objects with repetition )
Let $E$ denote the event that at least two people in class having same birthday, and $P(E)=1-P(E^{c})$
where $E^{c}$ will denote the event that no two people in the class having same birthday
$|E^{c}|=~^{365}P_{n}$ ($\because$ outcomes in $E^{c}$ are n-permutation of 365 objects without repetition )
now, $P(E^{c})=\frac{|E^{c}|}{|\Omega|}=\frac{^{365}P_{n}}{365^{n}}$ ($\because$ we assumed outcomes are equally likely )
$\therefore P(E)= 1- \frac{^{365}P_{n}}{365^{n}}$

Table:

n	p
23	0.5073
30	0.7063
40	0.8912
50	0.9704
60	0.9941
70	0.9992