Author |
Topic: probability challenging prob. (Read 5674 times) |
|
Benny
Uberpuzzler
Gender: 
Posts: 1024
|
 |
Re: probability challenging prob.
« Reply #25 on: Jul 4th, 2008, 1:34pm » |
 Quote  Modify
|
Actually, i was scheduled to fly to New Jersey to meet with my relatives. They booked the flight for me. I was so absorbed with math problems that i missed my flight. I have to take the next flight.
Regarding the problem: Maybe you guys are right. I need to rethink this problem. I wanted to present an abstract problem.
Towr, ThudanBlunder,
Any suggestions? How would you rewrite this problem and make it interesting?
|
|
 IP Logged |
If we want to understand our world — or how to change it — we must first understand the rational choices that shape it.
|
|
|
Benny
Uberpuzzler
Gender:
Posts: 1024
|
|
Re: probability challenging prob.
« Reply #26 on: Jul 6th, 2008, 2:16pm » |
Quote Modify
|
Towr and ThudanBlunder,
The goal is to create a problem that addresses different concepts of mathematics: combinatorics, probability, pigeonhole principle and Game Theory all mixed together in one problem.
What sorts of data you would like to see in order to start?
|
|
IP Logged |
If we want to understand our world — or how to change it — we must first understand the rational choices that shape it.
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: probability challenging prob.
« Reply #27 on: Jul 6th, 2008, 3:28pm » |
Quote Modify
|
Well, at the very least we need some model of passengers. Are they all the same, with the same preferences? And then we need information about the desirability of seats; how much better is a seat at the front than at the back; at the window the aisle or middle; how does it change depending on occupied seats. Anyone one of those variables is likely to change the result.
Simplest case, I think, would be all seats are equally desirable, and all passengers are equal in reasoning and preference. Which would mean none of them wants someone sitting next to them; but they do all need to sit somewhere.
If the number of passengers exceeds 2/3 of the number of seats, then some will have to sit next to each other. I doubt that in this case there's some strategy that gives the person with first pick a better chance than others to fulfill his dream of sitting next to empty seats though. (The first 1/3rd of possible passengers can take the same strategy, because all rows are equivalent, and the next passenger can't tell the difference between them).
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: probability challenging prob.
« Reply #28 on: Jul 6th, 2008, 4:20pm » |
Quote Modify
|
on Jul 6th, 2008, 2:16pm, BenVitale wrote:
The goal is to create a problem that addresses different concepts of mathematics: combinatorics, probability, pigeonhole principle and Game Theory all mixed together in one problem.
|
|
Here is a similar type of problem that you might find interesting.
|
|
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
Benny
Uberpuzzler
Gender:
Posts: 1024
|
|
Re: probability challenging prob.
« Reply #29 on: Jul 6th, 2008, 6:00pm » |
Quote Modify
|
on Jul 3rd, 2008, 8:05pm, BenVitale wrote:Taking a break from theoretical physics, i propose the following fun probability problem:
Suppose you are traveling alone (let's say on a business trip) in coach, or any other flight class that deals in rows of three seats per aisle side.
When buying your ticket, you are presented with a choice of any seat you want. We will assume that you are the first person to get to select your seat - that is, you can have your choice of any seat in coach.
You want to maximize the probability of ending up with an empty seat next to you. We'll assume the flight is near, but not at, capacity.
Which seat do you choose?
Of course, there are other "quality-of-flight" factors we can ignore that mess up a perfectly good plan, such as:
- the crying baby factor
- the little-kid-kicking-the-back-of-your-seat factor
- the incessant talker factor
- the fat-guy-that-ought-to-take-two-seats factor
- whatever-else-you-can-think-of factor
|
|
The important assumption is: you are the first person to get to select your seat.
the middle seat in any given row is a losing proposition. You have twice the chance of ending up with a person sitting next to you, on either or both sides.
So next 2 things to consider:
(a) window or aisle?
(b) which row?
The front rows?
I don't think so. They have the highest probability of filling up. People like being the first to exit the plane. People have an incentive to choose a seat in front.
Reflect upon your personal experience, and answer honestly: when you had the choice of seats, which seat did you selected most often?
There are 3 other factors :
(1) Day of the flight
What is the best day of the week to fly and get cheaper airfare?
According to http://www.answerbag.com/q_view/734331 it's on Tuesday, Thursday, Saturdays as a general rule.
Late night or early, early morning vs. late morning or mid day/mid-evening also.
(2) duration of flight
The duration of the traveling by air may affect your choice of seat. Based on my personal experience
an hour flight is not terribly long so I didn't care whoever was seated next to me. But a 3-hour or a
5-hour flight is much different. I am more self-conscious, I prefer to have an empty seat next to me.
(3) Domestic flight vs International flight
In this case I will check this website http://www.towd.com/ for statistics on when their busy and less busy times of year are.
For simplicity let's ignore factor #3
And, I think that some people may choose the seats in the very back of the plan in order to be close to the bathroom, especially for long flights. So, I don't think we should choose the very last rows.
Aisle or window?
It doesn't matter. If you choose, the window, another player will choose the aisle, thus making the middle seat very unappealing.
So, I assume that all players of the game will avoid choosing a seat adjacent to another player, if possible.
|
|
IP Logged |
If we want to understand our world — or how to change it — we must first understand the rational choices that shape it.
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: probability challenging prob.
« Reply #30 on: Jul 7th, 2008, 1:07am » |
Quote Modify
|
on Jul 6th, 2008, 6:00pm, BenVitale wrote:| the middle seat in any given row is a losing proposition. You have twice the chance of ending up with a person sitting next to you, on either or both sides. |
|
Only if the other people want to sit next to someone.
Besides, if someone next sits at the aisle seat next to you, someone trying to get to the window seat would need to pass two people. So you can be fairly sure that seat remains free, and when everyone has boarded scoot over.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Benny
Uberpuzzler
Gender:
Posts: 1024
|
|
Re: probability challenging prob.
« Reply #31 on: Jul 7th, 2008, 1:24pm » |
Quote Modify
|
I thought of 2 additional things:
(1) I don't mind if a female passenger sits next to me. But there's no way knowing that in advance. And it would complicate the problem greatly.
(2) A way to cheat: If I buy 2 tickets then it will guarantee me that I won't have anyone sitting next to me.
|
|
IP Logged |
If we want to understand our world — or how to change it — we must first understand the rational choices that shape it.
|
|
|
Benny
Uberpuzzler
Gender:
Posts: 1024
|
|
Re: probability challenging prob.
« Reply #32 on: Jul 7th, 2008, 6:06pm » |
Quote Modify
|
I still don't have any statistical data on the subject.
I think the best choice of row is anywhere between 3 and 6 rows from the back of the plane, not inclusive of the last three rows. So, if there are 30 rows of seats on the plane (R = 30), I think your best bet is to choose between rows 27 and 24.
And, it depends on the type and size of aircrafts.
I would conjecture that the range of preferable rows increases with the size of the aircraft - e.g. if R = 50, maybe the range could be like 5 rows.
Do you agree?
|
|
IP Logged |
If we want to understand our world — or how to change it — we must first understand the rational choices that shape it.
|
|
|
Benny
Uberpuzzler
Gender:
Posts: 1024
|
|
Re: probability challenging prob.
« Reply #33 on: Jul 9th, 2008, 5:29pm » |
Quote Modify
|
on Jul 6th, 2008, 4:20pm, ThudanBlunder wrote:
Here is a similar type of problem that you might find interesting.
|
|
Thanks for the link. Interesting twist. It is not exactly what I have in mind though. I found the crazy passenger on the airplane at this link
http://www.emicrosoftinterview.com/Puzzles-Riddles/94.aspx
But what do you think of the proposition I posted above, that is
Quote:
I think the best choice of row is anywhere between 3 and 6 rows from the back of the plane, not inclusive of the last three rows. So, if there are 30 rows of seats on the plane (R = 30), I think your best bet is to choose between rows 27 and 24.
And, it depends on the type and size of aircrafts.
I would conjecture that the range of preferable rows increases with the size of the aircraft - e.g. if R = 50, maybe the range could be like 5 rows.
|
|
I found this article, I'm trying to figure out whether or not I can use the info in this article in the problem
http://www.math.duke.edu/news/awards/MCM2007lmw.pdf
|
| « Last Edit: Jul 9th, 2008, 5:43pm by Benny » |
IP Logged |
If we want to understand our world — or how to change it — we must first understand the rational choices that shape it.
|
|
|
Christine
Full Member
Posts: 159
|
|
Re: probability challenging prob.
« Reply #34 on: Jul 11th, 2008, 2:14am » |
Quote Modify
|
How about perhaps choosing a middle seat somewhere in the section ?
|
|
IP Logged |
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: probability challenging prob.
« Reply #35 on: Jul 11th, 2008, 2:30am » |
Quote Modify
|
on Jul 9th, 2008, 5:29pm, BenVitale wrote:
But what do you think of the proposition I posted above, that is
|
|
Well, up to now you have included so many subjective variables that the Drake equation seems like a model of precision in comparison. 
|
|
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
Benny
Uberpuzzler
Gender:
Posts: 1024
|
|
Re: probability challenging prob.
« Reply #36 on: Jul 11th, 2008, 2:40am » |
Quote Modify
|
on Jul 11th, 2008, 2:30am, ThudanBlunder wrote:
Well, up to now you have included so many subjective variables that the Drake equation seems like a model of precision in comparison.
|
|
It is not easy to write a problem. I'm going around in circles with this thing. I fly quite often, and I'm trying to find an advantegeous strategy to book a flight.
Could you offer some suggestions to re-rewrite this problem?
|
|
IP Logged |
If we want to understand our world — or how to change it — we must first understand the rational choices that shape it.
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: probability challenging prob.
« Reply #37 on: Jul 11th, 2008, 3:00am » |
Quote Modify
|
on Jul 11th, 2008, 2:40am, BenVitale wrote:
Could you offer some suggestions to re-rewrite this problem?
|
|
With mathematical modelling an initial KISS model is preferable. Then later you can can refine and expand it.
|
|
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
LeoYard
Newbie
Posts: 35
|
|
Re: probability challenging prob.
« Reply #38 on: Jul 15th, 2008, 9:51am » |
Quote Modify
|
Are streaks possible?
This is my problem:
If you flip a coin 1,179 times, what is the probability that you will hit a streak where the coin lands on heads 21 times in a row?
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: probability challenging prob.
« Reply #39 on: Jul 15th, 2008, 11:16am » |
Quote Modify
|
on Jul 15th, 2008, 9:51am, LeoYard wrote:Are streaks possible?
This is my problem:
If you flip a coin 1,179 times, what is the probability that you will hit a streak where the coin lands on heads 21 times in a row? |
|
I get a probability of about 0.0002765, but I can't vouch for a lack of errors in my program.
I used the recursion
F(0, M) = 1
F(N, 0) = 0
F(N, M) = 1/2 F(N-1, M-1) + 1/2 F(21, M-1)
And then calculated F(21, 1179)
(F(N, M) stands for the probability we get a streak of 21 given we have M coins to go, and we currently need N to finish a streak of 21; if we throw heads, we need one less, if we throw tails we need to start over.)
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: probability challenging prob.
« Reply #40 on: Jul 15th, 2008, 12:49pm » |
Quote Modify
|
Let's fix the number k of heads required. Then the numbers 2mF(*,m) satisfy a first order linear recurrence, with transition matrix
1 1 0 0 0 ... 0
1 0 1 0 0 ... 0
1 0 0 1 0 ... 0
.....
1 0 0 0 0 ... 1
0 0 0 0 0 ... 2,
which has characteristic polynomial
(x-2)(xk - xk-1 - xk-2 - ... - x - 1)
= (x-2)[(xk+1-2xk+1)/(x-1)].
We can show (using Rouche's theorem) the second factor is always irreducible: all its roots have norm < 1, except for one of them, which approaches 2 from below as k gets large. For k=21, this root is about 1.99999952; the rest have norms < 0.996. Now, 2mF(k,m) is a linear combination of m-th powers of these roots. Since F(k,m) approaches 1, we have that 1-F(21,m) ~ c*0.99999976m as m goes to infinity.
In fact, if we write
f(x) = (xk+1-2xk+1)/(x-1) =  (x-ri),
then
2mF(k,m) = 2m -  ai rim
for some constants ai. Since F(k,m)=0 for 0  m < k, we can solve (Vandermonde/Lagrange interpolation):
a1 = i=2k (2-ri)/(r1-ri)
= [f(2)/(2-r1)] / f'(r1)
= r1(r1-1)/[ r1(k+1) - 2k ].
If r1 is the root with norm > 1, then because
r1k(2-r1) = 1,
we must have r1 converging from below to 2 exponentially in k, which means that a1 will converge to 1 from above. Indeed, for k=21, we have a1 = 1.00000453, and therefore
1 - F(21,m) = ai (ri/2)m
~ a1 (r1/2)m
~ 1.00000453 * 0.999999762m.
With m=1179, this first term a1 (r1/2)m is about 2*10-359 more than the correct answer.
Since r1 ~ 2 - 1/2k for k large, we can use the approximation
1 - F(k,m) ~ ( 1 + (k-2)/2k+1 ) * ( 1 - 1/2k+1 )m,
which is 99.99999986% accurate for the given problem (but it's only a good approximation if m isn't too large, relative to k).
|
| « Last Edit: Jul 15th, 2008, 2:18pm by Eigenray » |
IP Logged |
|
|
|
LeoYard
Newbie
Posts: 35
|
|
Re: probability challenging prob.
« Reply #41 on: Jul 15th, 2008, 4:00pm » |
Quote Modify
|
Thank you very much to both of you. It is this idea of streaks I'm not clear on, for example determining the longest streak if you you flip it 1179 times, and the probability of getting a streak of length p if you flip n times?
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: probability challenging prob.
« Reply #42 on: Jul 15th, 2008, 4:31pm » |
Quote Modify
|
Are you looking for a closed form? The probability of getting a streak of length k in n flips is
P(k,n) = 1 - ai(ri/2)n,
where r1,...,rk are the roots of (xk+1-2xk+1)/(x-1), and
ai = ri(ri-1) / [ ri(k+1) - 2k ].
I don't know if it gets much more closed than that. Actually, we have
P(1,n) = 1 - 1/2n
P(2,n) = 1 - Fn+2/2n,
P(3,n) = 1 - Tn+2/2n,
where Fn are the Fibonacci numbers, Tn are the Tribonacci numbers, etc. That is,
Ak(n) = 2n(1-P(k,n))
is given by
Ak(n) = 0, n < -1;
Ak(-1) = 1;
Ak(n) = Ak(n-1) + Ak(n-2) + ... + Ak(n-k+1).
Ak(n) counts the number of ways to avoid a k-streak with n flips. Which is kind of obvious now in hindsight 
|
|
IP Logged |
|
|
|
Benny
Uberpuzzler
Gender:
Posts: 1024
|
|
Re: probability challenging prob.
« Reply #43 on: Jul 19th, 2008, 8:32pm » |
Quote Modify
|
Has anyone read "Catch-22" by Joseph Heller?
In his novel, Catch-22 describes a false dilemma, where no real choice exists.
I read somewhere Online that in probability theory, it refers to a situation in which multiple probabilistic events exist, and the desirable outcome results from the confluence of these events, but there is zero probability of this happening, as they are mutually exclusive.
|
|
IP Logged |
If we want to understand our world — or how to change it — we must first understand the rational choices that shape it.
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: probability challenging prob.
« Reply #44 on: Jul 19th, 2008, 8:46pm » |
Quote Modify
|
on Jul 19th, 2008, 8:32pm, BenVitale wrote:| Has anyone read "Catch-22" by Joseph Heller? |
|
No, but I've seen the film.
Quote:| I read somewhere Online that in probability theory, it refers to a situation in which multiple probabilistic events exist, and the desirable outcome results from the confluence of these events, but there is zero probability of this happening, as they are mutually exclusive. |
|
Yeah, I read that, too.
|
| « Last Edit: Jul 20th, 2008, 7:33am by ThudnBlunder » |
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: probability challenging prob.
« Reply #45 on: Jul 20th, 2008, 7:29am » |
Quote Modify
|
on Jul 19th, 2008, 8:32pm, BenVitale wrote:| Has anyone read "Catch-22" by Joseph Heller? |
|
Over ten million copies of it have been sold, if all of those went unread, I think it needs an entry in the Guinness book of world records.
Besides, I read my copy of it.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: probability challenging prob.
« Reply #47 on: Aug 8th, 2008, 3:45pm » |
Quote Modify
|
on Aug 8th, 2008, 3:18pm, BenVitale wrote:AirTroductions is a New York-based website that allows you to find suitable seatmates on an airplane trip. You post a profile, and if you find a match, there's a $5 charge.
|
|
That's a neat idea. You pay them $5 and they match you with somebody else who doesn't want to sit next to anybody.
Probably you will all end up crammed into the back of the plane. LOL
|
| « Last Edit: Aug 8th, 2008, 8:39pm by ThudnBlunder » |
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
Benny
Uberpuzzler
Gender:
Posts: 1024
|
|
Re: probability challenging prob.
« Reply #48 on: Aug 8th, 2008, 4:05pm » |
Quote Modify
|
I was thinking about sitting next to a female passenger.
AND
There are two free web sites to visit for seat maps:
http://www.seatguru.com/
http://seatexpert.com/index.html
To see seat maps on specific flights that show which seats are occupied or not
http://www.expertflyer.com/index.jsp
The trick is to book ahead of time and from time to time with the airline about your seat, you have the option to change your seat if the seat next to you is occupied.
|
| « Last Edit: Aug 8th, 2008, 4:19pm by Benny » |
IP Logged |
If we want to understand our world — or how to change it — we must first understand the rational choices that shape it.
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print