The crumbling stairs

So we are in Tibet at the Holy Temple of Gangwolf and two novices are eagerly awaiting their final test before entering the order. Unfortunately the monastery is almost fully booked; there being only one vacancy.

In time honoured tradition they are given a challenge. Who can get highest up the temple stairway without stumbling?

The novices can stop at any stage. The one who has taken the most steps without stumbling is the winner. If it is known that there is a 10% chance of any step crumbling what is the best strategy? To attempt 10 steps and stop? Less? More?

(Yes this is a more complicated version of "Heads you win" problem)

A draw is NOT a win and they cannot see how their opponent has done.

Can you formulate a solution for P% chance of steps crumbling?

Originally posted by wolfgang59
So we are in Tibet at the Holy Temple of Gangwolf and two novices are eagerly awaiting their final test before entering the order. Unfortunately the monastery is almost fully booked; there being only one vacancy.

In time honoured tradition they are given a challenge. Who can get highest up the temple stairway without stumbling?

The novices can stop ...[text shortened]... how their opponent has done.

Can you formulate a solution for P% chance of steps crumbling?

To a Tibetan, what is winning?

But, seriously. You need to know how many steps (N) there are, to make your chances 50/50 against an equally gifted opponent, which is the best you can expect to do.

Then, saying there are N steps, give a weight of .9 to step 1, .9*.9 to step 2, .9*.9*.9 to step 3, and so on, up to .9*.9... N times, to step N. Increment the sum as you go along, identifying each increment with its step number (e.g., step 1 is all numbers >0 to .9, step 2 is all numbers >.9 to 1.71, etc.) Add the N results together to obtain M. Randomly select a number R, >0 to M inclusive of M. Find at which step R is contained, in the range of sums arrived at between that step and the next step. Try to get to that step, and if you do, stop.

This way, against your equally rational opponent, your predicted chances of stopping while still in the game, are the same as your actual predicted chances of getting to that step. The optimal strategy will be the same for your opponent.

If you have no idea how many steps there are, look around and think about it and guess at N.

Do not count on your opponent knowing anything about Nash equilibria.🙂

I think that there is a more intuitive way to approach this.

Both players have a 10% chance of stumbling at any point. They are stepping together (even though they cannot see each other - it doesn't matter). They have to take at least one step, with a 10% chance of stumbling.

The first novice expects the second novice to keep stepping up to the 50% chance. Less than 50% makes no sense. At 50% (5 steps), it gets tricky. Will the other novice take the 6th step because to only take 5 steps is a draw and equal to a loss? Or, does the other novice expect you to take the 6th step and increase your chances of stumbling and thereby essentially winning at 5 steps?

The best strategy is to take only one (1) step with only a 10% chance of stumbling. The other novice can make any calculations of how many steps are needed, but the chances of stumbling increase by 10% with each step.

Originally posted by coquette
I think that there is a more intuitive way to approach this.

Both players have a 10% chance of stumbling at any point. They are stepping together (even though they cannot see each other - it doesn't matter). They have to take at least one step, with a 10% chance of stumbling.

The first novice expects the second novice to keep stepping up to the 50% ch ...[text shortened]... ions of how many steps are needed, but the chances of stumbling increase by 10% with each step.

OK your strategy is to stop after 1 step.
Lets call you NoviceA.
NoviceB's strategy is to stop after 2 steps.
Lets run that ...

If you survive (0.9) then
1. 0.9 * 0.1 = 0.09 that B stumbles on step 1.
2. 0.9 * 0.9 * 0.1 = 0.081 that B stumbles on step 2
So your chance of winning is 0.171 (0.09 + 0.081)

If you do not survive then
1. 0.1 * 0.1 = 0.01 that B stumbles on step 1.
2. 0.1 * 0.9 * 0.1 = 0.009 that B stumbles on step 2
So your chance of drawing is 0.019 (0.01+ 0.009)

That leaves NoviceB a whopping 0.81 chance of winning!!!

Originally posted by JS357
To a Tibetan, what is winning?

But, seriously. You need to know how many steps (N) there are, to make your chances 50/50 against an equally gifted opponent, which is the best you can expect to do.

Then, saying there are N steps, give a weight of .9 to step 1, .9*.9 to step 2, .9*.9*.9 to step 3, and so on, up to .9*.9... N times, to step N. Increment th ...[text shortened]... ut it and guess at N.

Do not count on your opponent knowing anything about Nash equilibria.🙂

I thought about this and decided that the number of steps was only relevant against opponents working together.

... am willing to proven wrong ... 🙂

Originally posted by wolfgang59
So we are in Tibet at the Holy Temple of Gangwolf and two novices are eagerly awaiting their final test before entering the order. Unfortunately the monastery is almost fully booked; there being only one vacancy.

In time honoured tradition they are given a challenge. Who can get highest up the temple stairway without stumbling?

The novices can stop ...[text shortened]... how their opponent has done.

Can you formulate a solution for P% chance of steps crumbling?

I have a simpler way to decide when to stop, that I believe gives the same result as my first post, and it does not require knowing the number of steps N and does not even require that N be a finite number. Of course this could mean that I am wrong twice.

Devise a technique that reduces the probability P of continuing, as you go up. At Step n, the reduction has to be the same as the reduction in the probability of getting from step 0 to step n. This way your technique is risk-neutral; you are not counting on there being a best step at which to stop.

So before the first step, take the P of successfully getting from step 0 to step n=1, which is 0.9. Select a random number r, between 0 and 1, and take one step if r<P, otherwise stop. You have a 90% chance of stepping and a 90% chance of not crumbling. Now if you have stepped, recalculate P = 0.9*0.9 = 0.81. Select another random number r and take one step if r<P. Then P for the next step is 0.9*0.9*0.9 = 0.729, and so on.

You can calculate these beforehand and select r enough times so that you already know which step at which you will stop.

What does happen if there is a draw??

if they both lose, then they are best off agreeing a cooperative strategy where they both win 50% of the time

However I'm not sure that there is a stable cooperative strategy, i.e. a cheat will always benefit. If so they must each forge their own way, and they will have a less than 50% chance of winning...

Originally posted by iamatiger
What does happen if there is a draw??

if they both lose, then they are best off agreeing a cooperative strategy where they both win 50% of the time

However I'm not sure that there is a stable cooperative strategy, i.e. a cheat will always benefit. If so they must each forge their own way, and they will have a less than 50% chance of winning...

If its a draw both novices are put in a barrel with a bell and a chicken and rolled down the hill.

Then they have to climb the stairs again.

Are they allowed to take two stair steps in each climb? That would considerably change things.

The two climbers are independent of eachother (so I don't think you multiply one climbers probability against the other) and I would assume each climber has the same probability of stumbling (or not stumbling) and I'm assuming you must take one step at a time.

There are a few ways of looking at this.

Firstly, assuming the monks (assuming the temple was built by monks) are not silly enough to have crumbling steps leading to their temple, then one option is to climb all the way to the top safe in the knowledge there are no crumbling steps. {Besides, how did that get past the health and safety committee???}

Secondly, assuming this is a real challenge and the monks gave each climber identical conditions, then you can expect both to stumble on the same step. Anything else is not a fair challenge (assuming the challenge is fair). So this is a battle of wills between the two climbers. Here is where you assess your opponent before the challenge begins. Against a headstrong opponent you take one step. Against a meek opponent you take 2 steps.

Thirdly, in the absence of being able to assess your opponent, you take n steps where probability(not stumble) exceeds probability(stumble). P(stumble) = 1 - P(not stumble). P(not stumble) = 0.9^n where n is the number of steps. 0.9^6 = 0.53 and 0.97^7 = 0.48. At 6 steps the probability of not stumbling is >50% and at 7 steps is <50%. So stop at 6 steps.

However (fourth option), assuming your opponent is equally versed in the art of probabilities, take 7 (to beat him) or 8 steps (to counter his counter) and be damned!

But given human nature (of not taking a backward step) and knowing that n+1 is an ever-increasing function (per my previous paragraph), and in the absence of any immediate feedback in your winning, then stop at 1 step safe in the knowledge your opponent will keep going until he stumbles. I'm assuming that on stumbling you are immediately eliminated.

Or, you keep pondering the situation (as all good monks should) and not take a step at all until you have fully analysed the problem. In the absence of time controls, your opponent will eliminate himself. For after taking 1 step and not having any positive affirmation, he will continue taking one step at a time until he eliminates himself. After taking n steps and not having any affirmation he will assume you both are on the same number of steps and will continue to take more and more steps. Until you have stopped stepping the challenge is incomplete, and given you have not yet started you cannot be said to have stopped, so you continue to ponder ad infinitum.

A few options there and there may be more......interesting concept nonetheless!

Andrew

P(stumble in n steps) = 1 - 0,9^n

Originally posted by Thomaster
P(stumble in n steps) = 1 - 0,9^n

Do you know the name of the probability distribution?

No, I don't.


BTW: I would't chose 10 or higher.