1
$\begingroup$

Premise (the original problem): "You want to open a combination padlock by trying each of w permutations of the numbers, at x seconds per attempt." What is the probability of opening the lock before time y, given that time z has elapsed?" My question: I think the underlying probability, with respect to elapsed time z looks like a distribution "curve" that steps down a little at every ten second attempt (pulling on the lock). It is flat, then jumps down, is flat, then jumps down. My concern is that this may not be the end of the solution. For one-time events such as a machine failure, or in this case a success, we usually have an exponential probability curve that accounts for the "condition" that failure has not already occurred (is increasingly dependent on history). If I am right, this exponential curve is always falling with time, and flattens out. So, for this problem, would an exponential probability distribution need to be combined with the "falling steps", perhaps averaged together somehow? If not, why not, or how else should we handle this?

$\endgroup$
1
  • $\begingroup$ Your intuition sounds reasonable. Note that the probability of opening the padlock at the first attempt is 1/w. Given it is not correct, the probability of the next attempt is 1/(w-1), i.e. it is uniform over all possibilities (our assumption!). So if you frame "time" as "number of attempts", you should be able to write down an expression for this probability using Bayes' rule and see what that looks like. $\endgroup$
    – JKL
    Jun 12, 2022 at 15:47

2 Answers 2

1
+100
$\begingroup$

The problem that you posted is not too complicated, but details are important and often information is not carefully phrased or omitted. In this case it does for instance matter how one chooses a code to try to open the lock. The most important thing here is whether a code that has been tried before is possibly tried again or not. I.e., every permutation of possible codes is used only once vs. every time a random code is tried. In the former case the code will be found no later than the $w$th time, whereas in the later case it could take longer than that. Hence the answers in these two scenarios would be different.

I'll assume that it will be the former situation, where all possible codes are tried in some order but only once. This means that the correct code is one of the $w$ codes in the list, and since a priori we don't know which it is, each code in the list that we try has a fixed probability $1/w$ to be the correct one. So if we try up to time $y$ and it takes $x$ seconds per attempt, we have made $\lfloor y/x \rfloor$ attempts and hence we find that the probability for the code to be found before time $t=y$ is given by : $$P_\text{found}(t\leq y) = \frac{1}{w} \left \lfloor \frac{y}{x} \right \rfloor$$ But now the problem gives us more information, i.e., a time $t=z$ has passed. I will presume that this implies that the lock has not been opened, and hence that during that period $\lfloor z/x \rfloor$ unsuccessful attempts were made. For the time $t>z$ therefore only $w-\lfloor z/x \rfloor$ possible codes remain and hence we know that the probability that an untried code is correct is no longer $1/w$. During the time $z < t \leq y$ we will try $\lfloor y/x \rfloor-\lfloor z/x \rfloor$ new codes, and we find $$P_\text{found}(z < t \leq y) = \frac{1}{w-\lfloor z/x \rfloor} \left( \left \lfloor \frac{y}{x} \right \rfloor - \left \lfloor \frac{z}{x} \right \rfloor \right)$$

In view of your question, I used time $t$ as a continuous variable at the cost of introducing the floor function. Optically the problem looks much simpler and easier if we assume that $y,z$ are integer multiples of $x$ only, and set $x=1$ as the unit if time.

The exponential behaviour you refer to, actually does not show up in this problem, but it would if we would have choosen every time a random code to try on the padlock.

Dropping the continuous time and only focussing on the number of codes that are tried, we find that if you choose a code randomly, the probability to find the correct code on the $n$th attempt would be $$P(\text{found on $n$th}) = \left( 1- \frac{1}{w}\right)^{n-1} \left(\frac{1}{w}\right),$$ that is $n-1$ times a wrong code, followed by the correct one. The probability $1/w$ that a particular attempt is successful does not change in this scenario at all.

The probability not to find the code in $n$ successive attempts would be $$P(\text{not found in $n$}) =\left(1 - \frac{1}{w}\right)^n$$ and the probability to find it within $n$ attempts $$P(\text{found in $n$}) =1 - P(\text{not found in $n$})= 1 - \left(1 - \frac{1}{w}\right)^n$$

These probabilities are valid starting at any time, i.e., they do not change when preceded by an arbitrary number of unsuccessful attempts, and are valid for any $n$ and the limit $n \rightarrow \infty$ can be taken if so desired.

The probabilities do not change between attempts, so when using a continuous time the probability functions of time would be discontinuous step functions and in this case of a padlock have no real added value to the problem, they merely make the functional descriptions look more complicated. This would be different in say radioactive decay, which is closely related to the second scenario here.

Your confusion of combining exponential behaviour and step-functions seems to stem from the fact that you mix a discrete time problem of opening a lock, with a continuous time interpretation.

$\endgroup$
3
  • $\begingroup$ Thanks for your response, but I don't agree with your last point. (However, I'm not knowledgeable enough about when the exponential distribution applies, to be sure about any of this.) It seems that choosing a permutation with replacement (your second scenario) would also not involve the exponential curve. The basic question would still be asking about the future in whole, not in part. (This distinction is mine, and could be wrong, whether or not the exponential applies, since I'm not sure where and when it does apply. The reasons for the application, are what I'm trying to learn.) $\endgroup$
    – Bafs
    Jun 22, 2022 at 8:13
  • $\begingroup$ To follow up, my question now is, if "choosing with replacement" does call for using the exponential curve, is that "memorylessness" all we need to know? In other words, does the "subtle" logic in my OP (looking at the whole future, not sections of it) have any validity. Now, I'm inclined to think my logic was nonsense. $\endgroup$
    – Bafs
    Jun 22, 2022 at 8:52
  • $\begingroup$ @Bafs I have added some details, I hope this solves your questions. $\endgroup$ Jun 22, 2022 at 13:08
0
$\begingroup$

After much consideration, I believe that the falling steps do not need the addition of an exponential function. The reason for this is that the exponential curve applies to future events divided into sections of time (probability is evaluated over section(s) of time). However, in this problem we are looking for the total future probability without regard to any divisions of that time. At time z, we know that the lock is still unopened, and the condition that it hasn't already been opened is not in question. The prior is 100% not open. The time remaining for attempts may have a smaller exponential curve than before, but it is not relevant to the problem. We only need to know the total number of possible attempts before time runs out. The difference is subtle. Either we are asking about the progress of future events, or we are asking about the overall probability for the future. If anyone is sure that I'm wrong, or has more to add, please chime in.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .