wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> Hotel Key Card
        
(Message started by: pedronunezmd on May 26th, 2004, 7:46pm)
Title: Hotel Key Card
Post by pedronunezmd on May 26th, 2004, 7:46pm

Quote:
A certain hotel room lock is opened by scanning a key card. In theory, one enters the room by inserting and removing the key card once. In practice, however, the key card is ambiguously labeled, so that either of two orientations might be the correct orientation of the card. In theory, of course, one could just try one orientation, and if it didn't work try the other. In practice, however, the card reader sometimes fails, so that after trying each orientation once, one may still not have gained access to the room.

A few more details:

(a) Either of the two orientations is equally likely to be cor- rect.

(b) The success rate of a correctly oriented card is p with 0 < p < 1.

(c) Failure on either side of the card is indistinguishable, so it does not give any information about whether the orientation of the card was correct.

(d) An attempted scan takes 1 second to succeed or fail; reversing the orientation also takes 1 second.

The last property means that in 3 seconds one could try one orientation 3 times or each orientation once (using the middle second to flip it over). In either case, of course, one might still be standing in the hall and need to decide what to do next.

So what attempt strategy would you use to enter the room? Why?

Feel free to consider fixed values of p (p = .5 or p = .9, for example) as special cases. What if p is fixed but unknown?

Obviously, if p=1, then if you try the card one way, and it doesn't work, you know the other way is correct.

If p<1, then if you try the card one way, and it fails, you know that the probability that this card orientation is still correct is (1-p). If you try the card one way, 2 times in a row, all with failure, then the probability that this card orientation is still correct is (1-p)2. If you try the card one way, n times in a row, all with failure, then the probability that this card orientation is still correct is (1-p)n.

Therefore, if p is fixed and known, you would try the card in one orientation until, after the nth try, the value of (1-p)n is under 50%, at which point you would flip the card over to the other orientation and start all over.
Title: Re: Hotel Key Card
Post by THUDandBLUNDER on May 26th, 2004, 9:47pm
Let P(S) = probability of Successfully opening the door in one attempt
Let P(OC) = probability that Orientation is initially correct = 1/2
Let 1 - p = x

GIVEN: P(S|OC) = p
[hide]
Hence by Bayes p = P(S) * P(OC|S) / P(OC)
=  P(S) * 1 / (1/2)

Therefore P(S) = p/2


Quote:
If p<1, then if you try the card one way, and it fails, you know that the probability that this card orientation is still correct is (1-p).

I presume 'fails' means 'fails to open the door'.

Similarly, P(OC)|S') = P(OC) * P(S'|OC) / P(S')
= (1/2)(1 - p) / (1 - (p/2))
= (1 - p) / (2 - p)
= x / (1 + x)

For n attempts P(S') becomes P(S'(n)) =  (1 - p/2)n = [(1 + x) / 2]n
and P(S'|OC) becomes P(S'(n)|OC) = (1 - p)n = xn
where P(S'(n)) is the probability of not opening the door in n attempts or less.

[/hide]
Title: Re: Hotel Key Card
Post by pedronunezmd on May 27th, 2004, 5:13am
A correction to my previous post. What I should have written is that the probability that the orientation I choose is still correct after n failed attempts is 0.5(1-p)n, not (1-p)n.

So if p is fixed and known, you would change card orientations once 0.5(1-p)n goes under 50%.

Here is my reasoning:

P(orientation is correct after 0 failed attempts) = 0.5
P(orientation is correct after 1 failed attempts) = 0.5(1-p)
P(orientation is correct after 2 failed attempts) = 0.5(1-p)2
P(orientation is correct after n failed attempts) = 0.5(1-p)n

Sorry, ThudandBlunder, I have not had a chance this morning to process your theory yet. I'll look at it later today.
Title: Re: Hotel Key Card
Post by THUDandBLUNDER on May 27th, 2004, 5:21am
Maybe I have been making it more complicated than necessary....

....but, using my notation, we are given P(S|OC) = p

while you are calculating P(OC|S')

And you seem to have these two quantities summing to 1   ???
Title: Re: Hotel Key Card
Post by pedronunezmd on May 27th, 2004, 5:44am
Uh oh, I think I now realize that the probability that my orientation is correct, after 1 failed attempt, is actually not .5(1-p) but actually (1-p)/(2-p).

I need to avoid looking at these puzzles close to midnight (my first post) and early morning (this post) from now on. I'm just confusing myself.
Title: Re: Hotel Key Card
Post by pedronunezmd on May 27th, 2004, 5:26pm
Alright, now that is neither early morning or late night here, I am going to rephrase my earlier post and the reasoning behind it. I'll try to keep your terminology as best as I can.

First, to simplify the equations, I define a new variable x:
x = probability that a correct orientation does not work = 1-p

Correct me if I'm wrong, but I interpret your S'(n) to mean that after n tries, the door did not open...

I am interested in finding out what is P(Oc|S'(n)) which tells me "what is the probability that the orientation I have chosen is the correct orientation, given that I've tried this orientation n times without success already." Once this probability goes under 50%, I am better off switching to the other orientation.

Therefore, by Bayes Theorem:
P(Oc|S'(n)) = P(S'(n)|Oc) * P(Oc) / P(S'(n))

We know that:
P(Oc) = 0.5
P(S'(n)) = 0.5 + 0.5 (xn)
P(S'(n)|Oc) = xn

Therefore,
P(Oc|S'(n)) = xn * 0.5 / (0.5 + 0.5 (xn))

This simplifies to
P(Oc|S'(n)) = xn / (1 + xn)
Title: Re: Hotel Key Card
Post by THUDandBLUNDER on May 27th, 2004, 11:28pm

Quote:
I am interested in finding out what is P(Oc|S'(n)) which tells me "what is the probability that the orientation I have chosen is the correct orientation, given that I've tried this orientation n times without success already." Once this probability goes under 50%, I am better off switching to the other orientation.

We know that P(OC) = 1/2

So P(OC|S'(n)) < 1/2 for ALL n (if p > 0)

Hence, if there were no time penalty, we should always switch after the 1st failed attempt.
I think the 1 sec time penalty implies that we should switch after the 2nd failed attempt.


Quote:
We know that:  
P(OC = 0.5
P(S'(n)) = 0.5 + 0.5 (xn)
P(S'(n)|Oc) = xn

I get

P(S) = p/2
P(S') = (1 - p/2)
P(S'(n) = (1 - p/2)n
= [(1 + x)/2]n

P(S'(n)|Oc) = xn

P(Oc|S'(n)) = (1/2) * xn / [(1 + x)/2]n
= 2n-1 * [x / (1 + x)]n

For P(S(n)) and P(S'(n)), aren't you forgetting about a factor of 1/2 every time we make an attempt?
After all, we don't know if it's the right orientation.
That's why I have P(S) = p/2
Title: Re: Hotel Key Card
Post by pedronunezmd on May 28th, 2004, 3:38pm
I agree that:


Quote:
So P(OC|S'(n)) < 1/2 for ALL n (if p > 0)

Instead, I should probably pick an arbitrarily small percent that, when P(OC|S'(n)) goes under that value, then I make the change in orientation.

However, I do not agree with last part of the following statement:


Quote:
P(S) = p/2
P(S') = (1 - p/2)
P(S'(n) = (1 - p/2)n  
= [(1 + x)/2]n

I will post why in a little bit, I have to go eat dinner first.
Title: Re: Hotel Key Card
Post by pedronunezmd on May 28th, 2004, 4:17pm
Okay here is why I disagree. First of all, we never really defined explicity what S'(n) means, but I assummed you meant "The event that a given orientation is tried n times, and 0 times does the door open." If this is not correct, please read no further.

Otherwise, consider the following:

If A and B are independent events,
then it is true that P(A and B) = P(A) * P(B)

and if P(A) = P(B),
then it is true that P(A and B) = P(A) ^ 2

However when you calculate P(S'(2)) using your equation, you appear to by stating that P(S'(2)) = P(S'(1)) ^ 2, which seems to imply that you mean that the probability of "not opening the door on the first try" and "not opening the door on the second try" are independent events (which they are not, since they are both dependent on a third event, namely OC) and therefore can by multiplied together, and also that the two event are equal, thus that is the same as raising to the 2nd power.

You can see that the equation "P(S'(n)) = (1 - p/2)n" is not true by assuming that first, p<1; if you do not change orientations, then as n approaches infinity, P(S'(n)) with this equation approaches 0; you should know that, since the chance the chosen orientation is correct is 0.5, that given an infinite number of trials with the given orientation, P(S'(n)) should approach 0.5 not zero.

The correct way to determine P(S'(n)) is to realize that what you really need to do if calculate it as:

P(S'(n)) =
( P(OC) * P(S'(n)|OC) ) + P(O'C) * P(S'(n)|O'C) ) =
(0.5 * (1-p)n) + (0.5 * 1) =
0.5(xn) + 0.5
Title: Re: Hotel Key Card
Post by pedronunezmd on May 28th, 2004, 4:33pm
Now, if my calculations are all correct, what I would do, if p were fixed and known, is try one orientation, if it fails, than calculate what is probability that the orientation is still correct given 1 failure of door to open with this orientation. I would keep doing this n times until the probability became arbitrarily small that my chosen orientation was correct, at which point I would switch orientations.

I would use, after each n tries that did not work:
P(Oc|S'(n)) = xn / (1 + xn)

And when this goes under some small percent, I would change. What is the optimal percent? And also note that, when I change orientations, the new P(Oc) is no longer 0.5 but is instead (1 - the above probablity that my old orientation was correct) which will change my equation a bit, but is simple to calculate given the above.

Of course, all this assumes that p is known and fixed, but the problem asks for the algorithm for "What if p is fixed but unknown?" I won't tackle that until we agree on the the "known and fixed" part first.
Title: Re: Hotel Key Card
Post by grimbal on May 28th, 2004, 5:20pm
My idea is that when you have tried both sides an equal number of times, then you are back to the starting situation.  Both sides are equally likely to be correct.

From there, the only question is: what is the optimal number (k) of times you shoud try the first side before you switch?  If you know k, you try k times and you switch.  Then, until you have tried the second side k times, the second side is more likely to be correct.  After k tries, you are back to an even situation, so that you should do k more tries on the second side, switch, and so on.  The pattern is: try k times, switch, try 2k times, switch, try 2k times, etc.

We need to find out what is the optimal k to minimize the expected time (tries + switches) with the pattern above.

The result of my calculations is that if q is the probability of failing (1-p), then the expected time is

E = 1/(1-q) + (k+1)*(1+q2k)/(1-q2k)

To minimize E, depending on p, I find the best k is:
p=1.00-0.74, q=0.00-0.26 => k=1
p=0.73-0.46, q=0.27-0.54 => k=2
p=0.45-0.31, q=0.55-0.69 => k=3
p=0.30-0.23, q=0.70-0.77 => k=4
p=0.8, q=0.2 => k=5
p=0.9, q=0.1 => k=8
p=0.95, q=0.95 => k=13
p=0.99, q=0.99 => k=39

Obviously, unless there is a high probability of failing, >0.25, you should try one time and flip.  But then, you should try 2 times before you flip again.
Title: Re: Hotel Key Card
Post by pedronunezmd on May 28th, 2004, 5:45pm
Well, I wanted to try the "p is fixed and known" first, but my idea for fixed and unknown would be try 2 times, then change orientations, try 4 times, then change orientations, try 8 times, etc...

We may need to run experiments...
Title: Re: Hotel Key Card
Post by THUDandBLUNDER on May 29th, 2004, 3:19am
Yes, you are right, pedronunezmd.

Putting p = 1 makes it even clearer that my formula for P(S'(n)) is incorrect.   ::)
Title: Re: Hotel Key Card
Post by pedronunezmd on May 29th, 2004, 8:38pm
Okay, I've created my Visual Basic program to test out some different algorithms for comparison.

I've set up p to be a nonzero integer from 1-99 inclusive, to represent the percent chance that, given the correct orientation, using the key card will work.

I then set up the program to go with 1,000,000 trials using whatever algorithm for deciding when to flip orientations you would like. The program will spit out the average time it takes to open the door, over the 1,000,000 tries.

Here are some comparison numbers to look at:

Flip orientations of the card after every single try that is unsuccessful: average time to open door is 18.83 seconds.

Flip orientations of the card after every 2 unsuccessful tries with any given orientation: average time is 14.55 seconds.

Flip orientations of card after 2 initial tries, then every 6 thereafter: average time is 12.05 seconds. This last method is an incomplete variation on my method described above.
Title: Re: Hotel Key Card
Post by pedronunezmd on May 30th, 2004, 10:40am
Pretty much the best I can get is for the following:

Flip orientations of card after 2 initial tries, then every 8 thereafter: average time is 11.88 seconds.
Title: Re: Hotel Key Card
Post by towr on May 30th, 2004, 1:12pm
that's for any p?

If p is from a uniform distribution, then you can integrate the expected value from q=0 to 1, and optimize for k, which gives about 4.4.. (so 8 or 9 is what's you'd expect after the initial few tries)

Of course the longer it takes before the door opens the lower you'd expect p to be, so k should increase.
Title: Re: Hotel Key Card
Post by pedronunezmd on Jun 1st, 2004, 4:26am
That is for any p of the subset of the real numbers 0<p<1 such that p is equal to some integer n times .01

The reason I chose the .01 interval is that choosing the set instead of all real numbers 0<p<1 has no effect on my calculations for any p>.01  However, if p was significantly less than 0.01 then you could, with any given trial, have p infinitely close to zero, which would lead to "never" opening the door.

I could try running the program again, this time letting p = Random() rather than p=.01 * (Int( 99*Random()+1 ))

I don't think it will change the outcome really, since I did my calculations based on the math in my previous post, choosing the number of tries with the given orientation such that I minimize the chance that the current orientation is correct (to a 1% chance) for a given assummed p before switching, then using a lower assummed p once the switch was made.
Title: Re: Hotel Key Card
Post by pedronunezmd on Jun 1st, 2004, 5:28am
Okay, I changed the line in my trial-testing program to calculate p as follows:

while (p<.01) p=rnd()

This gives a random uniform distribution over .01<p<1 which is closer to what the program is asking for. This had no effect on my calculations of average times to open the door.

The reason I am setting a lower limit on p is that if you allow p to be smaller and smaller, approaching zero, then the number of times you would have to use the correct orientation before opening the door approaches infinity. And getting one of the "infinite time" results during my trials would throw off the average, to say the least.

My assumption is that the key card should have some reasonable probability of working given the right orientation, not infinitely close to zero. I chose .01 but perhaps it could be .001 or .0001? I do not believe this would affect the prime method of deciding when to flip orientations once a given trial is underway, however it will skew all the average calculated times up by a certain amount.

Maybe a better assumption is that there is a certain time after which, using whatever method of changing orientations and using the key card, that you would be forced to give up and either kick down the door or go to the hotel lobby and demand a new key card.

Perhaps, then, in my simulation I should be setting an upper limit on the time for any particular trial, rather than setting a lower limit on the p of the key card in your possession. However,
Title: Re: Hotel Key Card
Post by pedronunezmd on Jun 4th, 2004, 5:36pm
Towr, I've gotten rid of the assumptions I made about the lower limit of p (in order to make p closer to a random uniform distribution over the reals from 0 to 1) and the restriction on the upper limit of time for any given trial.

To be honest, I have no math training other than a few required math courses over 10 years ago in college, so I have no hope of trying to integrate the expected value from p equals 0 to 1.

I have used my calculations for a known p to come up with a strategy on when to flip the orientations, and then I am testing the strategy in an excel spreadsheet with some simple visual basic backup, and running 1,000,000 trials.

Using p = Random() which gives some sort of distribution of p from 0 to 1, my strategy of "flip orientations at 2, and then every 8 thereafter" seems to be the best method for deciding when to slip, with an average time to open, over 1 million trials, of 40.10 seconds.

But of course, I cannot ever prove this is the best method, since it is merely the best method of those I've tried.
Title: Re: Hotel Key Card
Post by towr on Jun 5th, 2004, 2:22pm

on 06/04/04 at 17:36:44, pedronunezmd wrote:
To be honest, I have no math training other than a few required math courses over 10 years ago in college, so I have no hope of trying to integrate the expected value from p equals 0 to 1.
I used a math program to integrate it numerically, I don't think there is a neat wait to do it by hand in this case..
I haven't yet really taken the time to look at this problem properly to be honest, maybe if I have some time in the coming week.
Title: Re: Hotel Key Card
Post by jonderry on Aug 19th, 2004, 11:42am
Is there a way to do this problem that is both not painful and not numerical?

Assuming the optimal strategy is of the form:
"n tests, flip, 2n tests, flip, 2n tests, flip, 2n tests, flip,..."
the best way I can think of to do this with paper and pencil is to compute, conditional on the correct orientation and dependent on n, the expected number of failed iterations (where a failed iteration is a sequence of 2n failed tests) times the cost of each iteration (4n + 2) plus the expected cost of an iteration given that it is successful, plus the cost of the initial n tests times the probability that they were unsuccessful plus the probability that the initial tests were successful times the expected cost of the initial n tests given that they were successful.

Adding each of these conditional expections and multiplying by 1/2 should give a formula for the expected cost of a
"n tests, flip, 2n tests, flip, 2n tests, flip, 2n tests, flip,..."
schedule in terms of n.

Then it is all a matter of simply minimizing this formula with respect to n and if it is not integral, trying the floor and ceiling of that number!

Anyone know of a better non-programmatic way, assuming this is correct?
Title: Re: Hotel Key Card
Post by Grimbal on Aug 21st, 2004, 3:34pm
;D  I just imagine the guy spending the night with his laptop computer in front of a hotel door trying to figure out wether he should retry the same direction or turn the card around.
And of course, he does this because he is in a hurry.  He doesn't want to loose too much time.


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board