Finding the largest Number with no return back

Thread Starter

zulfi100

Joined Jun 7, 2012
656
Hi,
I want to understand this concept.
http://timroughgarden.org/w17/l/l16.pdf
Specifically, when the numbers are adversarially chosen but then randomly ordered, it is easy to stop on the largest number with 25% probability: watch the first n/2 numbers go by, and stop on the first subsequent number that exceeds them all (if any). As long as the highest number is in the second half of the sequence and the second-highest number is in the first half of the sequence (with ≥ 25% probability), you are guaranteed to stop on the highest number. An optimized version of this algorithm (which looks at the first 1/e fraction of the elements) and analysis yields a success probability of ≈ 1 e ≈ 36.7% (see e.g. Wikipedia), thus yielding the “37% rule”
1. What is 25% probability?

Somebody please guide me.
Zulfi.
 

Thread Starter

zulfi100

Joined Jun 7, 2012
656
Hi,
Thanks for your reply. I can't understand this scenario : adversarially chosen but then randomly ordered

Somebody please guide me.

Zulfi.
 

WBahn

Joined Mar 31, 2012
29,976
What did it say on the very first page?

In the random permutation model, an adversary chooses an arbitrary (worst-case) input. Then, nature presents the input one piece at a time, in an ordering that is chosen uniformly at random.
What is it that you don't understand about that?

You are trying to achieve some goal based on a sequence of inputs in which you have to make irrevocable decisions after each input as you see them. The adversary -- i.e., someone that wants you to do poorly -- gets to choose the inputs that you will see, but they don't get to choose the order you will see them in, which is random.

So let's say that the goal is to pick the largest value among a sequence of numbers. You give the bad guy N ping pong balls and they write a number on each one. The balls are then put in a bag and shaken up and now you draw them out one at a time. You can write down anything you want to about them and use that information freely as you go. At some point you put the ball that you just drew into a jar and, once you've done that, it is revealed what the highest number was that was written on any of the balls. If that matches the number on the ball in the jar, then you win. Otherwise, you lose.

Your objective is to devise a strategy of deciding when to stop and putting the ball in the jar that will give you the best chance of winning. The adversary's objective is to choose a set of numbers that will defeat your strategy. Since they have no control over the order that the numbers will come at you, they have to choose a set of numbers that is likely to trick you in some way into making a bad choice.
 

Thread Starter

zulfi100

Joined Jun 7, 2012
656
Hi,
Thanks for your efforts but actually I can't understand how we can chose the largest number with 25% probability and after reading your example I am still not able to understand 25% probability but now its clear what is adversary in this context.

If you have time please explain me how we can get 25% probability.

Zulfi.
 

WBahn

Joined Mar 31, 2012
29,976
Hi,
Thanks for your efforts but actually I can't understand how we can chose the largest number with 25% probability and after reading your example I am still not able to understand 25% probability but now its clear what is adversary in this context.

If you have time please explain me how we can get 25% probability.

Zulfi.
What is the probability that the largest number is in the first half of the group?

What is the probability that the second-largest number is in the first half of the group.

What is the probability that the largest number is in the first half of the group AND that the second-largest number is in the second half of the group?
 

Thread Starter

zulfi100

Joined Jun 7, 2012
656
Hi,
Q. What is the probability that the largest number is in the first half of the group?
1- Pr[ largest number is not in the second half] or
1/(elements in the first half)
Q. What is the probability that the second-largest number is in the first half of the group
1/(elements in the first half -1) B/c we have to exclude the largest number
or
1-Pr[Second largest number is not in the second half of the group]

Q. What is the probability that the largest number is in the first half of the group AND that the second-largest number is in the second half of the group?

1/(number of elements in the first half of the grp) * 1/(number of elements in the second half of the group)

Zulfi.
 

WBahn

Joined Mar 31, 2012
29,976
Hi,
Q. What is the probability that the largest number is in the first half of the group?
1- Pr[ largest number is not in the second half] or
1/(elements in the first half)
Think about this. Are you really saying that if I have a sequence of 2,000,000 numbers and I write the first half of them on one sheet of paper (call it List A) and the second half of them on another sheet (call it List B), that there is only a one-in-a-million chance that the largest number is somewhere in List A?

Put it in other terms. Fifty thousand people enter a stadium and sit in random seats, all of which are numbered sequentially. What is the probability that the tallest person is sitting in an even numbered seat?

EDIT: Fixed typos.
 
Last edited:

Thread Starter

zulfi100

Joined Jun 7, 2012
656
Think about this. Are you really saying that if I have a sequence of 2,000,000 numbers and I write the first half of them on one sheet of paper (call it List A) and the second half of them on another sheet (call it List B), that there is only a one-in-a-million chance that the largest number is somewhere in List A?
Two answers possible:
1- 1/(1,000,000)
or
1/(1,000, 000)
Put it in other terms. Fifty thousand people enter a stadium and are sit in random seats, all of which are numbers sequentially. What is the probability that the tallest person is sitting in an even numbered seat?
1- 1/25000
or
1/25000

Sorry, I am not sure.

Somebody please guide me.

Zulfi.
 

djsfantasi

Joined Apr 11, 2010
9,156
You have two cups of 50,000 M&Ms without any blue M&Ms and one blue M&M. You drop the blue M&M into one cup and remove any one candy You shake the cups and move them around so so don’t know which cup has the blue M&M.

Pick any cup. What’s the probality that is has the blue M&M?
 

WBahn

Joined Mar 31, 2012
29,976
Hi,
Please provide me correct answer to post#9.

Zulfi.
One of the reasons why you make virtually no progress on being able to learn and work with this stuff is that you won't fight your way through it -- if your first attempt isn't correct you just want people to give you the answers and explanations. Well, how's that been working for you?

You have been asked the same a couple of different ways that should be easier to understand intuitively and you haven't made any effort to even try to answer either of them.

Let's step it back some more.

I have 100 marbles (99 white marbles and 1 black marble) that are split evenly between Bag A and Bag B. What is the probability that the black marble is in Bag B?
 

Thread Starter

zulfi100

Joined Jun 7, 2012
656
Hi,
Thanks for your replies.
Excuse me probability is not my main subject and this is not my hw. This is not good that you bombard me with questions and provide me no answer. I would always be wrong if I don't know the correct answer.
djsfantasi

I have already shown my work in post#9. Now its your turn to tell me if its right or not. You have to work in a stepwise manner. Otherwise you are taking many miles away from my actual question.

Zulfi.
 

SamR

Joined Mar 19, 2019
5,031
Ummm... Forget probability and use plain old common sense?!?! How many bags are there? How many bags can the black marble be in?
 

Thread Starter

zulfi100

Joined Jun 7, 2012
656
Sir this is not my question. My question is in post#1 which has been put to background. Instead of solving my own question I am solving others questions.

Zulfi
 

MIS42N

Joined Jan 25, 2013
22
OK lets settle this. You have a lot of numbers in random order. You divide them in half. There are two numbers - the highest and the second highest you are interested in. There are four equally likely possibilities:
1) both numbers are in the first half
2) both numbers are in the second half
3) the high number is in the first and the second highest is in the second half
4) the high number is in the second half and the second highest is in the first half
Since the sum of probabilities is 1 (100%) and each outcome has equal probability, each outcome has a probability of 25%. The specific outcome of interest is scenario 4) which has a probability of 25%. Hope that makes it plain.
I'm not clear what the paper is about. Probably sorting algorithms. Some sorting methods assume the numbers to be sorted are truly random, and work pretty well if they are. But if they are in a specific sequence (the adversity, or worst case situation) the sort takes a lot longer. A bubble sort is probably the worst sort algorithm, but a shell sort is a modified bubble sort and normally runs much quicker. But if the input is ordered in a particular way, the shell sort takes as long as a bubble sort.
Bubble sort and shell sort don't need a lot of work space because they sort by swapping elements. If there is plenty of space other algorithms are faster and less easily disrupted by specific ordering of elements (merge sort for instance).
 

WBahn

Joined Mar 31, 2012
29,976
Sir this is not my question. My question is in post#1 which has been put to background. Instead of solving my own question I am solving others questions.

Zulfi
Actually, the problems we are asking you ARE your original question (or the very first step involved in it), just restated using different words because the words in the original problem are leading you down a rabbit hole.

That's because you clearly don't understand the fundamental concepts required to solve the question. We are trying to help you build those fundamentals so that you identify what is important in the original problem by seeing that it is the exact same problem, from a probability standpoint, as the more obvious and simpler problems we are asking you (and that you refuse to even attempt to answer).

We could walk through the logic on THIS problem in excruciating detail and, at best, you will THINK you understand it. But if you were given an identical problem tomorrow that is simply phrased a bit differently, you'd be right back here asking for someone to spoon feed you a solution to that one, too, because you won't have learned anything about HOW to identify what the problem really is, to put it into terms that you can work with, and to then actually work with that information without someone else showing you step-by-step how to do THAT problem.
 
Top