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

        riddles >> hard >> probability challenging prob.
        
(Message started by: BenVitale on Jun 13th, 2008, 12:02pm)
Title: probability challenging prob.
Post by BenVitale on Jun 13th, 2008, 12:02pm
Problem (1)
Take a stick and cut it twice so that you have three sticks. If you make the cuts randomly, what are the chances you can make a triangle out of your three sticks?

Is the answer 50%?

(2)
Alice tosses 849 fair coins and Bob tosses 850. What is the probability that Alice gets more heads than Bob?

Is the problem worded correctly? I understand it better if the problem would have asked:
What is the probability that Bob gets more heads than Alice?
Then my answer would be: 1/2

Do you agree? Is there something I'm missing here?


(3)
I've worked on the 4 Door Monty Hall Problem

Behind 1 of 4 closed doors is a prize. You pick door 1. Monty opens the 4th door and it is empty. You switch your choice to door 2. Now monty opens door 3 and it is also empty. Given the choice, should you switch back to door 1, and what are your chances of winning if you do?

My answer: chances are 5/8 if you switch

Has anyone worked on an N door generalization of the problem?
Title: Re: probability challenging prob.
Post by jollytall on Jun 13th, 2008, 2:11pm
(1)
If I define the two random cuts as such that I generate to numbers (0-1) randomly and then cut at those places then I would go for 1/4.
If both are <0.5 or both >0.5 surely you cannot make a triagle. This is already 1/2. But even when a<0.5 and b>0.5 you can have that b-a>0.5. This is again half of the remaining, i.e. 1/4. So you cannot make 3/4.

(2) The two questions are not the same. They can have the same number of heads. Both questions can be answered though if you calculate the probability of A having a heads and B having b heads. Then you sum for all possible outcome of p(a) the sum of p(b) where b<a.
p(a)= (a|849)/2^849 = a!*(849-a)!/849!/2^849
p(b)= (b|850)/2^850 = a!*(850-a)!/850!/2^850
sum a=1 to 849: p(a)*( sum b=0 to a-1 p(b) )

(3)
I guess you had:
Step 0
1/4 1/4 1/4 1/4.
Step 1
1/4 3/8 3/8 0
Step 2
5/8 3/8 0 0
This sequence is misleading though. It assumes that in step 2 he can show W3. But it is not necessary the case. He can do it 5/8 of the time, while he can show W1 in 6/8 of the time (3/8 he can show either of them). We should know (or assume) something about his strategy when he can show both.

If we assume he shows W1 if he can then showing W3 means we must change back 1/1 (he could not show W1 because it is with the gift).
If we assume he shows W3 if he can then I would not change back 3/5 to stay.
If we assume that if he can show both then he changes random (1/2-1/2) then showing W3 is either because only that he could show (1/4 probability, after changing back 1/1) or both were free 3/8 of the time, he chose it 1/2, i.e. 3/16 and you should not change back. So changing back is winning 4/7 and not 5/8.
Title: Re: probability challenging prob.
Post by jollytall on Jun 13th, 2008, 2:51pm
A bit more explanation on (3).
Let's imagine N is very big and in the first step he shows N-3. We are left with three windows, W1, W2, W3. W1 was our first choice, but now we change to W2 (since almost 50% that it is there). Now he shows W3.
If we assume his strategy is to show W1 if he can then we must change back to W1.
If we assume his strategy is to show W3 if he can then we are either in the case with 1/N probability that it is under W1 or the (N-1)/2N that it is under W2. So staying with W2 is (N-1)/(N+1) chance the winner.
If he choses whichever he can random, then we are either in the case with 1/N when he could only show W3 or we are in the case with probability (N-1) /4N that the gift is under W2 AND he chose W3. So staying is better with a probability (N-1)/(N+3). For N=4 it means changing back is better, for N=5 it is 50-50 and for N>5 it is better to stay with W2.
Title: Re: probability challenging prob.
Post by BenVitale on Jun 13th, 2008, 3:51pm

Quote:
Problem (1)
Take a stick and cut it twice so that you have three sticks. If you make the cuts randomly, what are the chances you can make a triangle out of your three sticks?

Is the answer 50%?


I think 50% is the wrong answer. I believe now that the answer is 100% !!

Because the basic principle at work here is that no single side of a triangle can be longer than the other two sides combined. If you take a stick and then cut it in 3, you won't violate the basic principle.
Title: Re: probability challenging prob.
Post by BenVitale on Jun 13th, 2008, 4:07pm

Quote:
(2)
Alice tosses 849 fair coins and Bob tosses 850. What is the probability that Alice gets more heads than Bob?  

Is the problem worded correctly? I understand it better if the problem would have asked:
What is the probability that Bob gets more heads than Alice?  
Then my answer would be: 1/2

Do you agree? Is there something I'm missing here?


The way I understand this is either Bob has more heads than Alice or Bob has more tails than Alice, but not both.

It is 1/2 because suppose Bob has 1 coin and Alice has 0, then the probability is 1/2. The additional 849 tosses each makes should not affect this, right?
Title: Re: probability challenging prob.
Post by SMQ on Jun 13th, 2008, 7:12pm

on 06/13/08 at 15:51:53, BenVitale wrote:
I believe now that the answer is 100% !!

I believe you are mistaken.  If I have a stick 1m long and I cut two 10cm pieces from it, clearly no triangle can be made with these two pieces and the remaining 80cm piece.

--SMQ
Title: Re: probability challenging prob.
Post by BenVitale on Jun 13th, 2008, 7:38pm

on 06/13/08 at 19:12:41, SMQ wrote:
I believe you are mistaken.  If I have a stick 1m long and I cut two 10cm pieces from it, clearly no triangle can be made with these two pieces and the remaining 80cm piece.

--SMQ


You're thinking of triangles that connect.
I was thinking of triangles that don't necessarily connect, and used the basic principle.

And, in your case, what is the probability?
Title: Re: probability challenging prob.
Post by towr on Jun 14th, 2008, 4:27am

on 06/13/08 at 19:38:33, BenVitale wrote:
You're thinking of triangles that connect.
I was thinking of triangles that don't necessarily connect, and used the basic principle.
What does that mean? Connecting triangles?! We're trying to make one triangle from three pieces of stick.
If you have sides of length a,b,c and a+b < c, you can't make a triangle with those sides.
Title: Re: probability challenging prob.
Post by BenVitale on Jun 14th, 2008, 10:39am

on 06/14/08 at 04:27:01, towr wrote:
What does that mean? Connecting triangles?! We're trying to make one triangle from three pieces of stick.
If you have sides of length a,b,c and a+b < c, you can't make a triangle with those sides.


How about

/\

_________________________

One could place them such that a triangle appears, but with one side much longer.
I was trying to be tricky.

But, if we are not trying to be tricky then we need to calculate the probability the longest piece is shorter than the two other pieces combined.


Right side --------------------------------- Left side

(a) the first cut is either somewhere close to the left side or close to the right side.
(b) the first cut is at the center.

If (b) you won't be able to make a triangle.

The second cut:

If it is at the center you won't be able to make a triangle.

Since the first cut has to be on one side or the other, you have a 50% chance of getting the same side with the second cut.
Title: Re: probability challenging prob.
Post by jollytall on Jun 14th, 2008, 1:02pm
BenVitale,

Read what I said re (1). You did not specify precisely how you make two random cuts. One interpretation was to make two random numbers 0-1 first and then do the cutting at those two positions. Then the probability is 1/4.

I guess you also want to say the same logic of cutting, but your following reasoning is incorrect. It is true that if they are on the same half then you cannot make a triangle and that has 1/2 probability. But even if they are in the opposite sides it does not guarantee that you can make a triangle. It can happen that the middle piece is too long. This is 1/2 of the cases when the two cuts are at the opposite sides, or 1/4 of all the cases. This leaves 1/4.

Actually you can also define two random cuttings a bit different. First you make one cut at a random place and keep aside the left part. Then from the remaining (right) side again with a linear distribution you cut down the second piece at what is left is the third (just like in the Sausage duel). In this case if the first cut is >0.5 you do not have a chance. If it is less then 0.5 (x) then the probability that the second one result a triabgle is x/(1-x). You simply have to integral it 0-0.5 to get the total probability of a triangle made.
Title: Re: probability challenging prob.
Post by BenVitale on Jun 14th, 2008, 3:03pm
Thanks for the feedback.

The problem was presented to me as such


Quote:
Take a stick and cut it twice so that you have three sticks. If you make the cuts randomly, what are the chances you can make a triangle out of your three sticks?


It did not specify precisely how one can make 2 random cuts.


on 06/13/08 at 14:11:55, jollytall wrote:
(1)
If I define the two random cuts as such that I generate to numbers (0-1) randomly and then cut at those places then I would go for 1/4.
If both are <0.5 or both >0.5 surely you cannot make a triagle. This is already 1/2. But even when a<0.5 and b>0.5 you can have that b-a>0.5. This is again half of the remaining, i.e. 1/4. So you cannot make 3/4. ............

.


I need time to process your solution. I was so convinced of my solution, i need time, change my mind-set.
Title: Re: probability challenging prob.
Post by jollytall on Jun 15th, 2008, 12:16am
A two parameter random situation is best to imagine graphically and then compare the areas. Earlier I was lazy to draw, but here is a very simple one.
Title: Re: probability challenging prob.
Post by BenVitale on Jun 15th, 2008, 12:45pm
Jollytall, I now understand your solution. Thanks.

If we increase the number of doors from 3 to 100. If there are 100 doors, and Monty Hall shows that 98 of them are valueless.

the chance the prize behind the remaining door is

Using the formula in the following linked document

http://en.wikipedia.org/wiki/Monty_Hall_problem

N door generalization of the original problem in which the host opens p losing doors and then offers the player the opportunity to switch; in this variant switching wins with probability
(N-1)/N(N-p-1)

N=100, p=98 so the probability is 99/100

How to establish (N-1)/N(N-p-1) ?
Title: Re: probability challenging prob.
Post by towr on Jun 15th, 2008, 1:41pm

on 06/15/08 at 12:45:47, BenVitale wrote:
How to establish (N-1)/N(N-p-1) ?
The not-selected doors have a sum probability of (N-1)/N of containing the price. There are (N-p-1) identical doors left. So divide the total probability by this to get  (N-1)/N(N-p-1) per door for switching.

But note that this is unlike your earlier generalization where doors where opened one at a time and you could switch at every step.
Title: Re: probability challenging prob.
Post by BenVitale on Jun 16th, 2008, 3:19pm

Quote:
(3)
I've worked on the 4 Door Monty Hall Problem

Behind 1 of 4 closed doors is a prize. You pick door 1. Monty opens the 4th door and it is empty. You switch your choice to door 2. Now monty opens door 3 and it is also empty. Given the choice, should you switch back to door 1, and what are your chances of winning if you do?  

My answer: chances are 5/8 if you switch


Sorry, i forgot about this one. This is how I reasoned:

The chances are 5/8 if you switch. The initial chances of your first choice were 1/4, and opening another door without the prize doesn't change that, so the remaining 2 doors now have a 3/8 chance because the chances of all possibilities must sum to 1. But then when Monty opens door 3, using the same reasoning, door 2 stays at 3/8 chance and so the remaining door changes to 5/8.
Title: Re: probability challenging prob.
Post by jollytall on Jun 17th, 2008, 12:08am
BenVitale,

It was clear how you calculated. I also mentioned it in my first reply. But you also see there and then more in details in the second one, why that is not correct.

You also have to have some initial assumption about Monthy's actions. In case of four windows it is very important.
It is also important in the original problem. We always assume that Monthy MUST show an empty window after your first choice. In a real game it would not necessarily be the story. The producer might have other instructions. If you assume that they want to save cost then he will only show an empty window and offer to swap if you found the gift. So with this assumption you should never swap. But the opposite might be true as well. Their sponsor wants to gift given. So if you found it, he will simply give it and will only offer the change if you missed. So you must change. This is so obvious that we never mention.
But in case of four windows it is not that obvious, what the instructions are.
Title: Re: probability challenging prob.
Post by Hippo on Jun 17th, 2008, 2:15am
The modified monty hall is formulated wrongly. By these rules the moderator have no choice in fourth step with probability 3/8. ... so as mentioned by jollytall ... without the knowledge of moderators strategy you cannot compute the win probabilities (in range from 2/5 to 1 for switching).

If by the rules he will open 2nd doors even in the case you don't swith, you should prefere not to swith before the last door opening.
Title: Re: probability challenging prob.
Post by towr on Jun 17th, 2008, 2:52am
How about these four versions for the modified monty hall with N doors
1) The host must uniformly randomly open a (no-prize) door amongst the closed doors, excluding your current pick. (And of course the game ends when the host has no door left to open.)
2) The host must uniformly randomly open a (no-prize) door amongst the doors that have yet never been selected (either in the current or previous rounds)
3) Like 2, but you also cannot switch back to a door you chose previously.
4) The host has to open a closed (no-prize) door until you commit to a choice (or there are no other doors left), but he tries to minimize your chance of winning.
Title: Re: probability challenging prob.
Post by jollytall on Jun 17th, 2008, 5:29am
2) Which one do you get, the last chosen, or do you have still a chance to change when he announces that he cannot legally open a window? (you choose 1, he opens 4, you choose 2, he announces - It is behind 3).

1) As Hippo says, wait until only 2 windows left. Change then. Although if it is allowed to change once he announces that although there is a closed door, but he is not allowed to open it, you can improve further. Choose and stick to it until either he opens all, or he announces that he cannot legally open the other.
Title: Re: probability challenging prob.
Post by towr on Jun 17th, 2008, 5:58am

on 06/17/08 at 05:29:57, jollytall wrote:
2) Which one do you get, the last chosen, or do you have still a chance to change when he announces that he cannot legally open a window? (you choose 1, he opens 4, you choose 2, he announces - It is behind 3).
Well, typically you get to switch after the host opened another door. So if he can't open another one for whatever reason, you don't get to switch either.

Actually, to make any of the 4 cases interesting, we really need to encourage switching in some way; for instance include the rule that you either switch to a another/new door, or the game ends and you get what's behind your door.
Because otherwise you just wait till (N-2) doors have been opened and switch then.

I really should have put a bit more thought into it.
Title: Re: probability challenging prob.
Post by BenVitale on Jul 3rd, 2008, 8:05pm
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
Title: Re: probability challenging prob.
Post by towr on Jul 4th, 2008, 12:18am

on 07/03/08 at 20:05:06, BenVitale wrote:
Taking a break from theoretical physics, i propose the following fun probability problem:
It's not really a probability problem if there isn't any data about the probabilities.
You may as well start a rumour that you're a serial killer and let people know what seat you're in. Then they'll 'probably' avoid you.
Title: Re: probability challenging prob.
Post by BenVitale on Jul 4th, 2008, 1:08am

on 07/04/08 at 00:18:40, towr wrote:
It's not really a probability problem if there isn't any data about the probabilities.
You may as well start a rumour that you're a serial killer and let people know what seat you're in. Then they'll 'probably' avoid you.


Couldn't we determine the seat to choose in order to maximize the probability of ending up with an empty seat next to you?

How about choosing the least desirable seat on the plane -- a seat that no one would choose if other options are available? So, in my opinion, the worst seat on a commercial flight is the last row at the rear of the aircraft. Those seats will have the highest probability of being empty.

Or how about outside aisle seat ?

no dude likes to sit in middle so next guy that comes will sit in the window (many prefer views and sights of journey)

Now to the middle seat when a person buys ticket and is previously aware of situation then based on human pyschology they have tendencey not to sit beside 2 people for lack of freedom and peace; it is simple: most people don't like sitting crowd with 2 person beside them in a big place like a plane or even coach; yet if you choose window seat then couples of 2 are most likely to sit in the next 2 seats beside you the difference here and choosing aisle seat is that if you sit on outside seat couples would not likely be pleased to be "trap" between you and vehicle walls, sitting on outside also shows hints of domination and power
Title: Re: probability challenging prob.
Post by towr on Jul 4th, 2008, 1:24am

on 07/04/08 at 01:08:16, BenVitale wrote:
Couldn't we determine the seat to choose in order to maximize the probability of ending up with an empty seat next to you?
If we had any relevant data on the subject; but we don't. Or I don't, in any case.


Quote:
How about choosing the least desirable seat on the plane -- a seat that no one would choose if other options are available?
And which would that be?
(and of course you should pick the seat next to it, not the seat itself)
And what of the motivations of the other people? Do they prefer to sit next to someone, or does everyone want an empty seat next to them.


Quote:
So, in my opinion, the worst seat on a commercial flight is the last row at the rear of the aircraft. Those seats will have the highest probability of being empty.
Well, at least no I know where to sit in a plane if I want to avoid you ;) But what about other people?



Quote:
Or how about outside aisle seat ?

no dude likes to sit in middle so next guy that comes will sit in the window (many prefer views and sights of journey)
But if you sit in the middle, you have two chances of having an empty seat next to you. What's the chance of someone willing to shuffle past the guy in the middle seat to take a window seat? If there's other less obstructed seats available they may fill up first.

Of course there's a disturbing lack of any statistical data to actual base any probabilistic judgment on.
Title: Re: probability challenging prob.
Post by ThudanBlunder on Jul 4th, 2008, 4:51am

on 07/04/08 at 01:24:55, towr wrote:
Of course there's a disturbing lack of any statistical data to actual base any probabilistic judgment on.

Yeah, but for Ben 'no data' just means it's quite Hard.  :)
Title: Re: probability challenging prob.
Post by BenVitale on Jul 4th, 2008, 1:34pm
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?
Title: Re: probability challenging prob.
Post by BenVitale on Jul 6th, 2008, 2:16pm
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?
Title: Re: probability challenging prob.
Post by towr on Jul 6th, 2008, 3:28pm
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).
Title: Re: probability challenging prob.
Post by ThudanBlunder on Jul 6th, 2008, 4:20pm

on 07/06/08 at 14:16:20, 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 (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_easy;action=display;num=1067088849;) is a similar type of problem that you might find interesting.
Title: Re: probability challenging prob.
Post by BenVitale on Jul 6th, 2008, 6:00pm

on 07/03/08 at 20:05:06, 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.
Title: Re: probability challenging prob.
Post by towr on Jul 7th, 2008, 1:07am

on 07/06/08 at 18:00:53, 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.
Title: Re: probability challenging prob.
Post by BenVitale on Jul 7th, 2008, 1:24pm
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.
Title: Re: probability challenging prob.
Post by BenVitale on Jul 7th, 2008, 6:06pm
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?
Title: Re: probability challenging prob.
Post by BenVitale on Jul 9th, 2008, 5:29pm

on 07/06/08 at 16:20:32, ThudanBlunder wrote:
Here (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_easy;action=display;num=1067088849;) 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
Title: Re: probability challenging prob.
Post by Christine on Jul 11th, 2008, 2:14am
How about perhaps choosing a middle seat somewhere in the section ?
Title: Re: probability challenging prob.
Post by ThudanBlunder on Jul 11th, 2008, 2:30am

on 07/09/08 at 17:29:12, 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 (http://en.wikipedia.org/wiki/Drake_equation) seems like a model of precision in comparison. ::)
Title: Re: probability challenging prob.
Post by BenVitale on Jul 11th, 2008, 2:40am

on 07/11/08 at 02:30:27, ThudanBlunder wrote:
Well, up to now you have included so many subjective variables that the Drake equation (http://en.wikipedia.org/wiki/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?
Title: Re: probability challenging prob.
Post by ThudanBlunder on Jul 11th, 2008, 3:00am

on 07/11/08 at 02:40:51, 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.
Title: Re: probability challenging prob.
Post by LeoYard on Jul 15th, 2008, 9:51am
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?
Title: Re: probability challenging prob.
Post by towr on Jul 15th, 2008, 11:16am

on 07/15/08 at 09:51:00, 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.)
Title: Re: probability challenging prob.
Post by Eigenray on Jul 15th, 2008, 12:49pm
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) = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/prod.gif(x-ri),
then
2mF(k,m) = 2m - http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gifai rim
for some constants ai.  Since F(k,m)=0 for 0 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif m < k, we can solve (Vandermonde/Lagrange interpolation):
a1 = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/prod.gifi=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) = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gifai (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).
Title: Re: probability challenging prob.
Post by LeoYard on Jul 15th, 2008, 4:00pm
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?
Title: Re: probability challenging prob.
Post by Eigenray on Jul 15th, 2008, 4:31pm
Are you looking for a closed form?  The probability of getting a streak of length k in n flips is

P(k,n) = 1 - http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif 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 :-[
Title: Re: probability challenging prob.
Post by BenVitale on Jul 19th, 2008, 8:32pm
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.
Title: Re: probability challenging prob.
Post by ThudanBlunder on Jul 19th, 2008, 8:46pm

on 07/19/08 at 20:32:00, 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 (http://en.wikipedia.org/wiki/Catch-22_(logic)), too.  ::)
Title: Re: probability challenging prob.
Post by towr on Jul 20th, 2008, 7:29am

on 07/19/08 at 20:32:00, 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.
Title: Re: probability challenging prob.
Post by BenVitale on Aug 8th, 2008, 3:18pm
Concerning the selection of a seat on a flight, I've just come across a website that can help me with problem.

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.

http://many.corante.com/archives/2006/02/26/airtroductions.php

Peter Shankman founder of Airtroductions.com

http://jscms.jrn.columbia.edu/cns/2006-05-02/stefanini-airplanematchmaking


AirTroductions Sets Up In-Flight Connections

http://www.washingtonpost.com/wp-dyn/content/article/2005/09/24/AR2005092400216.html
Title: Re: probability challenging prob.
Post by ThudanBlunder on Aug 8th, 2008, 3:45pm

on 08/08/08 at 15:18:38, 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
Title: Re: probability challenging prob.
Post by BenVitale on Aug 8th, 2008, 4:05pm
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.


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