[Sorry - been a long time without posting. Illness has made it hard to find the impetus.]
Anyway, a probability problem I found interesting:
What's the distribution of the number of random uniform[0,1) random variables that you need to generate so that the sum is greater than 1?
There's a nifty little trick to it.
Update:
Well, the trick is to compute the survivor function, 1-F(n).
Let N be the number of uniform RVs needed to exceed 1.
P(N>n) = P(U(1) + U(2) + ... + U(n) <= 1)
That RHS probability is relatively easy to get in a variety of ways to be 1/n!
From there, the probability function for N is simple...
Showing posts with label probability. Show all posts
Showing posts with label probability. Show all posts
Monday, May 18, 2009
Friday, January 2, 2009
"Hit the target space" probability
Back to the problem of finding the probability of hitting a desirable space when rolling a six sided die (d6). Let's look at the easy way to compute the probabilities, then we can talk about them.
First, let's compute a couple of easy probabilities - we'll use them to check our work in a moment. If I was one space from the target, I only hit the target on a roll of 1. Any other roll takes me past it and I miss it.
So the probability I hit the target from one space away is 1/6.
If I was two spaces away, I hit the target with a roll of 2 (probability 1/6); but I can also hit the target by moving one space (1/6) and then hitting the target from there (times the 1/6 we already worked out a second ago). Total probability = 7/36.
Let's say P(i) is the probability of hitting the target space, T, from space i.
From the current space, i, the probability you hit the target is the probability you roll 1 times the probability you hit the target from one space further ahead, plus the probability you roll 2 and hit the target from 2 spaces further ahead, and so on up to 6 spaces.
That is, we get the recursive formula
P(i) = 1/6 [P(i+1)+P(i+2)+...+P(i+6)].
Let's look at that for a second. If I know the six probabilities immediately ahead of the current space, I can work out the probability from this space.
Now, let's look at the target space, T. Obviously, we're there already, so P(T)=1.
How would I work out the probability for the previous space?
P(T-1) = 1/6 [P(T) + P(T+1) + ... + P(T+5)].
Wait. What's P(T+1)? Well, from past the space I have no chance. It's 0. Same with P(T+2), etc.
P(T-1) = 1/6 [ 1 + 0 + 0 + 0 + 0 + 0 ] = 1/6 (checks out)
P(T-2) = 1/6 [1/6+ 1 + 0 + 0 + 0 + 0 ] = 7/36 (checks out)
[It's not hard from this to show that, for the 5 spaces immediately before the target, the hit-the-target probability for the NEXT space further away is 7/6 of the probability for the current space. Consequently, for those spaces, P(T-i) = 7i-1/6i. So from 6 spaces away, the probability is 75/66 = 16,807/46,656. However, I'm going to take a lazier-but-more general approach for computing probabilities.]
We can compute all the probabilities numerically, working one by one back from the target. Indeed, with a neat recursive formula like that one above, a spreadhseet is a handy tool (I happened to use Excel). Write the probabilities for P(T) to P(T+5) in a column (1 and 5 0's), and write the formula for P(T-1) in terms of those values:
Okay, instead of 1/6*sum(B5:B10) I lazily used the average function, but you see the idea. Copy that formula and paste it down as many rows as you like.
While the probability at 6 spaces away is 36%, the probability at 7 spaces away is 25%!
At large distances, the number converges to 2/7 ~= 28.57% (if the average roll is 3.5 spaces, it's perhaps not so surprising that the average probability you hit a space is 1/3.5).
In Excel, you can do neat plots to see what's going on:
In short, if you have some influence on where you try to land on the target from (such as the ability to change your roll by one, for example), the best spots (in order) are 6 spaces away, 5 spaces away and 11 spaces away, and of those, 6 is by far the best. Try to avoid being fewer than 4 spaces away, and 7 isn't much good either.
I used the approach outlined here to look at rolling two and three dice (2d6 and 3d6) as well; the direct calculation approach here adapts quite easily to these situations, yielding probabilities with a minute or so of effort.
First, let's compute a couple of easy probabilities - we'll use them to check our work in a moment. If I was one space from the target, I only hit the target on a roll of 1. Any other roll takes me past it and I miss it.
So the probability I hit the target from one space away is 1/6.
If I was two spaces away, I hit the target with a roll of 2 (probability 1/6); but I can also hit the target by moving one space (1/6) and then hitting the target from there (times the 1/6 we already worked out a second ago). Total probability = 7/36.
Let's say P(i) is the probability of hitting the target space, T, from space i.
From the current space, i, the probability you hit the target is the probability you roll 1 times the probability you hit the target from one space further ahead, plus the probability you roll 2 and hit the target from 2 spaces further ahead, and so on up to 6 spaces.
That is, we get the recursive formula
P(i) = 1/6 [P(i+1)+P(i+2)+...+P(i+6)].
Let's look at that for a second. If I know the six probabilities immediately ahead of the current space, I can work out the probability from this space.
Now, let's look at the target space, T. Obviously, we're there already, so P(T)=1.
How would I work out the probability for the previous space?
P(T-1) = 1/6 [P(T) + P(T+1) + ... + P(T+5)].
Wait. What's P(T+1)? Well, from past the space I have no chance. It's 0. Same with P(T+2), etc.
P(T-1) = 1/6 [ 1 + 0 + 0 + 0 + 0 + 0 ] = 1/6 (checks out)
P(T-2) = 1/6 [1/6+ 1 + 0 + 0 + 0 + 0 ] = 7/36 (checks out)
[It's not hard from this to show that, for the 5 spaces immediately before the target, the hit-the-target probability for the NEXT space further away is 7/6 of the probability for the current space. Consequently, for those spaces, P(T-i) = 7i-1/6i. So from 6 spaces away, the probability is 75/66 = 16,807/46,656. However, I'm going to take a lazier-but-more general approach for computing probabilities.]
We can compute all the probabilities numerically, working one by one back from the target. Indeed, with a neat recursive formula like that one above, a spreadhseet is a handy tool (I happened to use Excel). Write the probabilities for P(T) to P(T+5) in a column (1 and 5 0's), and write the formula for P(T-1) in terms of those values:
| | A | B |
| : | ||
| 4 | T-() | prob |
| 5 | -5 | 0 |
| 6 | -4 | 0 |
| 7 | -3 | 0 |
| 8 | -2 | 0 |
| 9 | -1 | 0 |
| 10 | 0 | 1 |
| 11 | 1 | =AVERAGE(B5:B10) |
| 12 | 2 | |
| 13 | | |
| : | |
Okay, instead of 1/6*sum(B5:B10) I lazily used the average function, but you see the idea. Copy that formula and paste it down as many rows as you like.
| | A | B |
| : | ||
| 4 | T-() | prob |
| 5 | -5 | 0 |
| 6 | -4 | 0 |
| 7 | -3 | 0 |
| 8 | -2 | 0 |
| 9 | -1 | 0 |
| 10 | 0 | 1 |
| 11 | 1 | 0.16667 |
| 12 | 2 | 0.19444 |
| 13 | 3 | 0.22685 |
| 14 | 4 | 0.26466 |
| 15 | 5 | 0.30877 |
| 16 | 6 | 0.36023 |
| 17 | 7 | 0.25360 |
| 18 | 8 | 0.26809 |
| 19 | 9 | 0.28037 |
| 20 | 10 | 0.28929 |
| 21 | 11 | 0.29339 |
At large distances, the number converges to 2/7 ~= 28.57% (if the average roll is 3.5 spaces, it's perhaps not so surprising that the average probability you hit a space is 1/3.5).
In Excel, you can do neat plots to see what's going on:
In short, if you have some influence on where you try to land on the target from (such as the ability to change your roll by one, for example), the best spots (in order) are 6 spaces away, 5 spaces away and 11 spaces away, and of those, 6 is by far the best. Try to avoid being fewer than 4 spaces away, and 7 isn't much good either.
I used the approach outlined here to look at rolling two and three dice (2d6 and 3d6) as well; the direct calculation approach here adapts quite easily to these situations, yielding probabilities with a minute or so of effort.
Thursday, January 1, 2009
Let's start with a little probability intuition
Imagine you're playing a board game where your pieces move according to a die roll. Unless it's a very dull game, there will probably be other things that can influence your position as well, but we're ignoring them right now.
Let's imagine that normally your move is given by a single die roll (six sided die, d6), and you pass along the spaces only once - it's a straight "race", not a circuit.
No doubt you've seen many games where you move along spaces to some end, and a few spaces have special characteristics (such as "miss a turn" or "move ahead three spaces"). BoardGameGeek calls these "roll and move" games, and appears to list more than six thousand of them. If that doesn't ring a bell, think of something a bit like Snakes and Ladders.
(However, you can apply similar ideas to a large variety of games where you accumulate some resource with varying probabilities. )
Further, let's say there's a particularly desirable space to land on (which I'll call the target). You're currently 6 spaces away (that is, if you roll a 6 you will land on the space). You really would like to land on that space, either this turn, or next turn, or the turn after that, ... &c.
Quick - without working it out exactly, and assuming for now that no strategy is available to change the probability, what would you guess would roughly be your chance of hitting the the target at all?
Then, if you're so inclined, try to work out the probability. (If you're not inclined to attempt it, never fear - I will post the correct answer later. There's at least one fairly easy way to do it - and a lot of somewhat less easy ways to do it.)
This was one case where my intuition wasn't as directly useful as I might hope. Intuition served me just fine for figuring out what the probability would be from far away, but from closer up, not so much - at least not at first.
Let's imagine that normally your move is given by a single die roll (six sided die, d6), and you pass along the spaces only once - it's a straight "race", not a circuit.
No doubt you've seen many games where you move along spaces to some end, and a few spaces have special characteristics (such as "miss a turn" or "move ahead three spaces"). BoardGameGeek calls these "roll and move" games, and appears to list more than six thousand of them. If that doesn't ring a bell, think of something a bit like Snakes and Ladders.
(However, you can apply similar ideas to a large variety of games where you accumulate some resource with varying probabilities. )
Further, let's say there's a particularly desirable space to land on (which I'll call the target). You're currently 6 spaces away (that is, if you roll a 6 you will land on the space). You really would like to land on that space, either this turn, or next turn, or the turn after that, ... &c.
Quick - without working it out exactly, and assuming for now that no strategy is available to change the probability, what would you guess would roughly be your chance of hitting the the target at all?
Then, if you're so inclined, try to work out the probability. (If you're not inclined to attempt it, never fear - I will post the correct answer later. There's at least one fairly easy way to do it - and a lot of somewhat less easy ways to do it.)
This was one case where my intuition wasn't as directly useful as I might hope. Intuition served me just fine for figuring out what the probability would be from far away, but from closer up, not so much - at least not at first.
Subscribe to:
Posts (Atom)