Try another key

Posted: March 30, 2011 in experiments, matlab
Tags: , ,

Proposition: If we are given $n$ keys, where only $m$ of these keys can open a door, then on average we would have to try $\frac{n+1}{m+1}$ keys to open the door.

I previously discussed a similar problem in which I derived that since the probability of finding a correct key on the kth try is

$P(X = k) = \displaystyle \frac{\displaystyle \binom{n-m}{k-1}m}{\displaystyle k\binom{n}{k}}$

then in theory it would take $\frac{n+1}{m+1}$ tries to oppen the door because

$\displaystyle E[X] = \frac{n+1}{m+1}.$

I became interested in modeling this proposition so implemented a MATLAB program, try_keys(n,m), in which each key is represented by a number from 1 to n and each correct keys is represented by a number from 1 to m. And when the try_keys(n,m) is executed it outputs a random sequence that starts with any key and ends with a correct key.

Now in theory if had 15 keys, such that 3 keys are correct, then on average I would expect to open the door on the 4th try since

$\displaystyle \mu_{th} = \frac{15+1}{3+1} = 4$.

For Experiment1 I ran try_keys(15,3) a total of 10 times

try_keys(15,3)     =    13     7     4     6     5     1
try_keys(15,3)     =     4     2
try_keys(15,3)     =     3
try_keys(15,3)     =     4     5     1
try_keys(15,3)     =    14    10     5     4     2
try_keys(15,3)     =    12     4     3
try_keys(15,3)     =     7     1
try_keys(15,3)     =     2
try_keys(15,3)     =    15    10     6     1
try_keys(15,3)     =     4     9     1

and for Experiement2 I repeated the same thing

try_keys(15,3)     =    10     8     7     5     6     3
try_keys(15,3)     =    12     2
try_keys(15,3)     =    11     2
try_keys(15,3)     =     6     7     8     1
try_keys(15,3)     =    14     8     5     4     6     9     7    10     3
try_keys(15,3)     =     5     3
try_keys(15,3)     =    13     2
try_keys(15,3)     =     4     2
try_keys(15,3)     =     4     5    10     2
try_keys(15,3)     =    14    10     5     2

So from the first and second experiment, the average number of tries needed to open the door

$\mu_{e1} = \frac{1}{10}(6+2+1+3+5+3+2+1+4+3) = 3$

$\mu_{e2}=\frac{1}{10}(6+2+2+4+9+2+2+2+4+4) = 3.7$

are within 35% and 7.5% of $\mu_{th}.$

Now by the Law of large numbers we would expect that if we ran try_keys(15,3) an infinite number of times then the average would converge to 4. So, to illustrate this law I implemented  average_try_keys(N,n,m)  which runs try_keys(n,m), N times, and computes an average. And, I also implemented  plot_average_try_keys(L,n,m) which plots average_try_keys(i*round(L/30),n,m) for integer values of i from 1 to 100. So, here are the plots that I got from plot_average_try_keys(L,15,3) using L values 1e2, 1e3, 1e4, 1e5 and 1e6.

And here is the code that I used to generate these plots.

try_keys

function [ s ] = try_keys(n,m)
%There are n keys which will be
%represented by numbers 1,2,...n.
%There are m correct keys which
%will be represented by numbers 1,2,...m.
%where m is less than or equal to n.
if( m > n || n <= 0 || m <= 0)
quit;
end

%s is the sequence of keys draw will be s,
%where s(1) is the first key
%draw, s(2) the second, and so on.
%So at most we will try a total of n-m keys.
%s = zeros(1,n-m);
%We are assuming that that keys are
%uniformly distributed, so we will be
%using randi(10) but we wont be accepting
%tried.
s(1) = randi(n);

%We are done when we find a correct key so
%we check to see if first key is
%correct. If not then we get another key and so on.
if( size(find( s <= m ),2) ~= 0)
done = 1;
else
done = 0;
end
draw = 1;
while( done == 0)
isnewkey = 0;
while(isnewkey ==0)
newkey = randi(n);
if(size(find(s == newkey),2) == 0)
s(draw + 1) = newkey;
isnewkey = 1;
if( size(find( s <= m ),2) ~= 0)
done = 1;
else
draw = draw + 1;
end
end
end
end
end

average_try_keys

function mu = average_try_keys(N,n,m)
s =zeros(1,N);
for i=1:N
s(i) =  size(try_keys(n,m),2);
end
mu = mean(s);
end

plot_average_try_keys

function plot_average_try_keys(L,n,m)
Num_points = 100;
expected_value = (n+1)/(m+1);
y = zeros(1,Num_points);
x = (1:Num_points)*round(L/Num_points);
for i=1:Num_points
y(i) = average_try_keys(i*round(L/Num_points),n,m);
end
plot(x,y,'-ro',x,expected_value,'-b')
h = legend('averages','expected value',2);
set(h,'Interpreter','none')