Dominion Strategy Forum

Please login or register.

Login with username, password and session length
Pages: 1 ... 15 16 [17] 18 19 ... 45  All

Author Topic: Maths thread.  (Read 115777 times)

0 Members and 3 Guests are viewing this topic.

GeoLib

  • Jester
  • *****
  • Offline Offline
  • Posts: 965
  • Respect: +1263
    • View Profile
Re: Maths thread.
« Reply #400 on: May 23, 2015, 05:40:28 pm »
+1

Ok I have a problem that I don't really know the answer too. Or rather, I have two contradictory answers that I'm trying to reconcile. Perhaps it's more suited to the logic puzzles thread, but I think reconciling the answers might be a math issue. Anyways:

There is a king with a kingdom of countably infinite people. He decides to play a game with his subjects. This game consists of multiple rounds. In the first round, he calls one of his subjects to play. They come to the castle and he flips two coins. If they're both heads then that person wins and the game is over. Otherwise, he calls up two people, flips two coins. If they're both heads those people both win and the game is over. Otherwise, he calls up four people, etc. The game ends as soon as someone wins. In each round twice as many people come up and their fates are still decided by two coin flips.

You are called by the King. What is your probability of winning?
Logged
"All advice is awful"
 —Count Grishnakh

liopoil

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2587
  • Respect: +2478
    • View Profile
Re: Maths thread.
« Reply #401 on: May 23, 2015, 06:01:26 pm »
+2

If I understand right, the answer would be 1/4, simply the probability both are heads. You are called, so you will get a chance at the coins being flipped, and no other chances.
Logged

GeoLib

  • Jester
  • *****
  • Offline Offline
  • Posts: 965
  • Respect: +1263
    • View Profile
Re: Maths thread.
« Reply #402 on: May 23, 2015, 06:14:58 pm »
+2

If I understand right, the answer would be 1/4, simply the probability both are heads. You are called, so you will get a chance at the coins being flipped, and no other chances.

Yeah this is one answer and I think the right one. So the question is, how do you reconcile this: No matter when the game ends, there are more winners than losers. Say the King flipped all the coins and figured everything out first, and only then started calling people to tell them whether they've won or lost. This seems like exactly the same game, but he calls more people to tell them they've won than he calls people to tell them they've lost.
Logged
"All advice is awful"
 —Count Grishnakh

liopoil

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2587
  • Respect: +2478
    • View Profile
Re: Maths thread.
« Reply #403 on: May 23, 2015, 06:44:28 pm »
0

Hmm, okay. So if we solve it that way, the question is, what fraction of people are winners? This is always greater than .5 as you say, but it varies. Possible fraction sequence is 1, 2/3, 4/7, 8/15.... and in general if the game ends in the nth round the fraction is 2^(n - 1)/(2^n - 1). What is the probability that it ends in the nth round? 1/4, 3/16, 9/64, 27/256..., or in general (1/4)*((3/4)^(n - 1). So the expected fraction is the infinite series formed from the product of the two:

1/4 + 1/8 + 9/112 + ...

and in general the nth term of the series is 6^(n - 1)/(2^3n - 2^2n), which you can check for yourself by multiplying.

And... I'll let somebody else figure out if the series converges and if so what to. But clearly if it converges it is greater than 1/4, and after just 3 terms it is 5/112 away from 1/2, so my guess is that's where it converges. So I am very confused too, unless this series doesn't converge for some reason.
Logged

sitnaltax

  • Apprentice
  • *****
  • Offline Offline
  • Posts: 281
  • Respect: +481
    • View Profile
Re: Maths thread.
« Reply #404 on: May 23, 2015, 06:50:24 pm »
+3

It looks to me like the apparent paradox is resolved by the fact that in the second scenario, you have an additional piece of information: the knowledge that the experiment is already over.

I am also reminded of the two-envelopes paradox, although I can't put my finger on exactly why.
Logged

liopoil

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2587
  • Respect: +2478
    • View Profile
Re: Maths thread.
« Reply #405 on: May 23, 2015, 06:58:25 pm »
0

It looks to me like the apparent paradox is resolved by the fact that in the second scenario, you have an additional piece of information: the knowledge that the experiment is already over.

I am also reminded of the two-envelopes paradox, although I can't put my finger on exactly why.
Why is that fact relevant?

The envelopes paradox I resolve to myself by reasoning that you can't actually choose a real number (or a rational number?) uniformly at random. That doesn't happen here.
« Last Edit: May 23, 2015, 06:59:45 pm by liopoil »
Logged

scott_pilgrim

  • Saboteur
  • *****
  • Offline Offline
  • Posts: 1035
  • Respect: +2005
    • View Profile
Re: Maths thread.
« Reply #406 on: May 23, 2015, 07:48:42 pm »
+1

I think the problem comes from two different ways of multiplying zero by infinity, basically.  In both cases, you know that you are going to be chosen out of a countably infinite number of people, so there is a 0% chance that that will happen.  You're looking at two different ways of that 0% actually happening, and since the problem doesn't tell you which way is the right one, you could come up with different answers depending on how you look at it.  The difference is between determining how many people are going to be called in first, and then knowing that you're one of them; and having no idea where you are in the line-up, but knowing that you're going to play, and that when you do, you have a 1/4 chance of winning.  So basically, I think sitnaltax has it right.

For some reason it reminds me of this: http://en.wikipedia.org/wiki/Bertrand_paradox_(probability)
Logged

GeoLib

  • Jester
  • *****
  • Offline Offline
  • Posts: 965
  • Respect: +1263
    • View Profile
Re: Maths thread.
« Reply #407 on: May 23, 2015, 07:58:58 pm »
0

Hmm, okay. So if we solve it that way, the question is, what fraction of people are winners? This is always greater than .5 as you say, but it varies. Possible fraction sequence is 1, 2/3, 4/7, 8/15.... and in general if the game ends in the nth round the fraction is 2^(n - 1)/(2^n - 1). What is the probability that it ends in the nth round? 1/4, 3/16, 9/64, 27/256..., or in general (1/4)*((3/4)^(n - 1). So the expected fraction is the infinite series formed from the product of the two:

1/4 + 1/8 + 9/112 + ...

and in general the nth term of the series is 6^(n - 1)/(2^3n - 2^2n), which you can check for yourself by multiplying.

And... I'll let somebody else figure out if the series converges and if so what to. But clearly if it converges it is greater than 1/4, and after just 3 terms it is 5/112 away from 1/2, so my guess is that's where it converges. So I am very confused too, unless this series doesn't converge for some reason.


After 1000 terms its at 0.671837 and it's still there at 10000, so that's probably about right.


It looks to me like the apparent paradox is resolved by the fact that in the second scenario, you have an additional piece of information: the knowledge that the experiment is already over.

I am also reminded of the two-envelopes paradox, although I can't put my finger on exactly why.

Yeah something involving you getting new information might be it.

The other thing is that while the fraction that are winners and the number of rounds are convergent series, the total number of players is not. I don't know if we're losing something in the infinity. Like perhaps it doesn't even make sense to talk about the king finishing choosing everyone and then calling them because he would have to have already picked out an undefined number of people.

PPE: I will check out the Bertrand Paradox
Logged
"All advice is awful"
 —Count Grishnakh

Ghacob

  • Young Witch
  • ****
  • Offline Offline
  • Posts: 149
  • Shuffle iT Username: Gender
  • J. They/them
  • Respect: +204
    • View Profile
Re: Maths thread.
« Reply #408 on: May 23, 2015, 08:43:07 pm »
+1

http://www.wolframalpha.com/input/?i=0.671837+possible+closed+forms

Definitely one of those is what we're looking at here
Logged
Gender happened.

Titandrake

  • Mountebank
  • *****
  • Online Online
  • Posts: 2152
  • Respect: +2716
    • View Profile
Re: Maths thread.
« Reply #409 on: May 23, 2015, 09:22:19 pm »
0

The envelopes paradox I resolve to myself by reasoning that you can't actually choose a real number (or a rational number?) uniformly at random. That doesn't happen here.

I don't see how that's part of the paradox? I thought the paradox was that you can show that you should switch envelopes indefinitely.

If you're talking about the strategy that gives > 50% chance of picking the envelope with more money, it's not a paradox, it's just an incredibly unintuitive result.
Logged
I have a blog! It's called Sorta Insightful. Check it out?

liopoil

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2587
  • Respect: +2478
    • View Profile
Re: Maths thread.
« Reply #410 on: May 23, 2015, 09:40:09 pm »
+1

The envelopes paradox I resolve to myself by reasoning that you can't actually choose a real number (or a rational number?) uniformly at random. That doesn't happen here.

I don't see how that's part of the paradox? I thought the paradox was that you can show that you should switch envelopes indefinitely.

If you're talking about the strategy that gives > 50% chance of picking the envelope with more money, it's not a paradox, it's just an incredibly unintuitive result.
The reasoning behind switching envelopes indefinitely assumes that the other envelope is equally likely to have half or twice as much money, and this is only true if we chose one of the values uniformly at random. I haven't heard of that strategy you mention.
Logged

pacovf

  • Cartographer
  • *****
  • Offline Offline
  • Posts: 3428
  • Multiediting poster
  • Respect: +3766
    • View Profile
Re: Maths thread.
« Reply #411 on: May 23, 2015, 10:43:13 pm »
0

This problem reminds me of the common Casino get-rich scheme: after any loss, double the bet, and that way you are guaranteed to eventually get the initial bet. Easy money!

Of course, the problem with that scheme is that you can't keep doubling the bet indefinitely, because your money is finite. As sitnaltax said, the source of the paradox here is that in one case you are assuming a finite number of trials, but not in the other.

EDIT: You can use 2^(n-1) < 2^n -1 < 2^n to find a lower and upper bound of the series (2/3 and 4/3, if the cold is not negatively affecting my calculating skills). And since all the terms of the sum are positive, the upper bound also proves the convergence.
« Last Edit: May 23, 2015, 10:58:59 pm by pacovf »
Logged
pacovf has a neopets account.  It has 999 hours logged.  All his neopets are named "Jessica".  I guess that must be his ex.

scott_pilgrim

  • Saboteur
  • *****
  • Offline Offline
  • Posts: 1035
  • Respect: +2005
    • View Profile
Re: Maths thread.
« Reply #412 on: May 23, 2015, 11:18:21 pm »
0

It also reminds of me of the game where I pay you $k to play, and the we flip a coin.  If tails, the game ends and you pay me $1.  If heads, we flip another coin.  If tails the game ends and you pay me $3.  If heads, we flip another coin.  Repeat until you get tails, and then pay me $3^n, where n is the number of heads flipped.

The funny thing about that game is that the expected payout is infinite, which means in theory I should be willing to pay you any (finite) amount of money to play it.
Logged

Titandrake

  • Mountebank
  • *****
  • Online Online
  • Posts: 2152
  • Respect: +2716
    • View Profile
Re: Maths thread.
« Reply #413 on: May 23, 2015, 11:20:29 pm »
+1

The >50% strategy is actually for a different problem, but I'll share it anyways because it's pretty cool.

In this problem, there are two envelopes. One has more money than the other, but you don't know what the amounts are. You're given an envelope and can see how much money is inside. After doing so, you can either keep this envelope or switch with the other one. You can only do this once.

Given that you don't know the values, it's strange that you can ensure a >50% chance you pick the better envelope. The trick is that you choose whether to switch randomly, in a way that is more likely to switch when you have the smaller envelope.

For simplicity, let the envelope values be A and B, where A < B and both are positive integers. Use the following switching scheme: look at the amount of money in your envelope, let's say that's M. Flip a fair coin M times. If you get all heads, switch envelopes. Otherwise, keep envelopes.

The chance you get the envelope with B is 1/2 * (1 - 1/2^B) + 1/2 * (1/2^A) = 1/2 + 1/2^{A+1} - 1/2^{B+1}. Since A < B, this is very slightly larger than 1/2.

What we're basically doing here is getting a sample from the geometric distribution, the number of trials needed before reaching an ending condition. In this scheme, it's # of flips until first tails. If the sample (the # of flips) is >= M we switch, and otherwise we don't. To generalize this to real numbers, you can use a continuous probability distribution, such as the normal distribution. All you need is P(sample >= A) > P(sample >= B) for A < B, which is always true as long as your distribution has non-zero weight over the range [0, infinity)
Logged
I have a blog! It's called Sorta Insightful. Check it out?

DStu

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2627
  • Respect: +1488
    • View Profile
Re: Maths thread.
« Reply #414 on: May 24, 2015, 02:23:49 am »
0

If I understand right, the answer would be 1/4, simply the probability both are heads. You are called, so you will get a chance at the coins being flipped, and no other chances.

Yeah this is one answer and I think the right one. So the question is, how do you reconcile this: No matter when the game ends, there are more winners than losers. Say the King flipped all the coins and figured everything out first, and only then started calling people to tell them whether they've won or lost. This seems like exactly the same game, but he calls more people to tell them they've won than he calls people to tell them they've lost.

The difference between both scenarios is that you somewhere in between flip an expectation value and a limes, and you can't do this here.

I can't exactly put the finger on it, because I also think it depends a bit on how you want to put it exactly mathematically. This is already not trivial, as there are some other problems in this, too; like for example the non-existence of a uniform distribution on a countable infinite set (you can't just say you are on a random position).  This would be solveable by e.g. assuming #coin tosses < N, in this scenario you could calculate everything (and get to the conclusion that it is more likely to win than lose) and then letting N->\inf, but there you get your problem with swapping expectation and limes.

Edit:
So in abstract the difference between the two approaches is that you are in a situation where you can either have a straightforeward calculation of you odds (two coins -> 1/4), or go back to the broad situation with subtle mathematical problems like infinities and conditional expectiations and such, and try to get your odds from this picture.

/edit

Quote
This problem reminds me of the common Casino get-rich scheme: after any loss, double the bet, and that way you are guaranteed to eventually get the initial bet. Easy money!

Of course, the problem with that scheme is that you can't keep doubling the bet indefinitely, because your money is finite. As sitnaltax said, the source of the paradox here is that in one case you are assuming a finite number of trials, but not in the other.
Even if you could, this is the same "paradox", as your expected win at each time is 0, but at the end is 1.  Again, you swapped expectation and limes somewhere.
« Last Edit: May 24, 2015, 02:28:05 am by DStu »
Logged

Witherweaver

  • Adventurer
  • ******
  • Offline Offline
  • Posts: 6476
  • Shuffle iT Username: Witherweaver
  • Respect: +7842
    • View Profile
Re: Maths thread.
« Reply #415 on: May 24, 2015, 07:42:09 am »
+5

Again, you swapped expectation and limes somewhere.

You can only swap expectations and limes in the presence of some convergence theorem, e.g., monotone convergence or dominated convergence.  Monotone convergence is when all the limes are in order of color tone.  Dominated convergence is when the limes become sentient and take over Earth as benevolent overlords. 
« Last Edit: May 24, 2015, 07:43:18 am by Witherweaver »
Logged

liopoil

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2587
  • Respect: +2478
    • View Profile
Re: Maths thread.
« Reply #416 on: May 24, 2015, 08:54:06 am »
+1

Okay, what's a lime?
Logged

Ghacob

  • Young Witch
  • ****
  • Offline Offline
  • Posts: 149
  • Shuffle iT Username: Gender
  • J. They/them
  • Respect: +204
    • View Profile
Re: Maths thread.
« Reply #417 on: May 24, 2015, 09:09:38 am »
+2

Okay, what's a lime?
                                                 Moat                                 
Logged
Gender happened.

Witherweaver

  • Adventurer
  • ******
  • Offline Offline
  • Posts: 6476
  • Shuffle iT Username: Witherweaver
  • Respect: +7842
    • View Profile
Re: Maths thread.
« Reply #418 on: May 24, 2015, 09:23:51 am »
+1

Okay, what's a lime?

Limit.  I'm not sure if Dstu just says that or it was some weird autocorrect.  But the idea is, suppose you have functions {f_n} and some limiting function f such that f_n -> f pointwise, meaning that for each x in the common domain,

lim_{n-> inf} f_n(x) = f(x).

Now what can we say about int(f_n) vs int(f)?  Well, it is not in general true that the sequence {int(f_n)} converges to int(f).  There is a fairly trivial counterexample, but I'd have to think of what it is, and I don't have the time right now.  I think maybe something like sin(nx)/n.  To get the limit of the integrals to converge to the integral of the limit (i.e., to interchange limits and integrals), you need some more assumptions on the functions.  The Monotone Convergence Theorem and the Dominated Convergence Theorem provide two such conditions for when you can do this.

Expectations are simply integrals, where the integration is done in some probability measure.

Now I have explained my joke, so you may find it very much funny and adorn it with upvotes. 
Logged

DStu

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2627
  • Respect: +1488
    • View Profile
Re: Maths thread.
« Reply #419 on: May 24, 2015, 09:54:38 am »
+2

... and to explain the lime, it was early, my English was still half asleep and was under the illusion that the latin word used in German can't be so wrong.
Logged

Witherweaver

  • Adventurer
  • ******
  • Offline Offline
  • Posts: 6476
  • Shuffle iT Username: Witherweaver
  • Respect: +7842
    • View Profile
Re: Maths thread.
« Reply #420 on: May 24, 2015, 01:11:13 pm »
0

Lime is Latin for limit?  That's interesting.. I wonder how the word came about for the fruit.
Logged

DStu

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2627
  • Respect: +1488
    • View Profile
Re: Maths thread.
« Reply #421 on: May 24, 2015, 01:11:26 pm »
+2

Lime is Latin for limit?  That's interesting.. I wonder how the word came about for the fruit.
Limes

edit: lol
Quote from: wikipedia
Limes
From Wikipedia, the free encyclopedia
For the fruit, see Lime (fruit). For the mathematical concept, see Limit (mathematics).

A limes (/ˈlaɪmiːz/;[1] Latin pl. limites) was a border defence or delimiting system of Ancient Rome. It marked the boundaries of the Roman Empire.
« Last Edit: May 24, 2015, 01:13:19 pm by DStu »
Logged

qmech

  • Torturer
  • *****
  • Offline Offline
  • Posts: 1918
  • Shuffle iT Username: qmech
  • What year is it?
  • Respect: +2315
    • View Profile
Re: Maths thread.
« Reply #422 on: May 24, 2015, 05:12:52 pm »
+2

There is a fairly trivial counterexample, but I'd have to think of what it is, and I don't have the time right now.

Very tall, very thin spikes, say with height n and width 1/n.
Logged

sudgy

  • Cartographer
  • *****
  • Offline Offline
  • Posts: 3392
  • Shuffle iT Username: sudgy
  • It's pronounced "SOO-jee"
  • Respect: +2652
    • View Profile
Re: Maths thread.
« Reply #423 on: May 27, 2015, 04:18:24 pm »
0

Random game theory question I was wondering (I don't know any game theory, so your explanations won't make sense, I just want an answer (discuss your explanations with each other of course if you want)):

Think of the candy jar game.  There is a certain amount of candy in a jar and several people guess how much there is.  Whoever guesses the closest wins.  Now, here's the catch:  If two people guess the same amount above and below (say the answer is 207 and two people guessed 205 and 209), then the person with the higher number wins.  How will this affect your strategy?

And, a hard mode I guess: I was thinking of this because of a candy jar I'm making with nerds.  I haven't finished counting, but there will be at least 10,000 nerds in it.  It looks like there's less nerds than there are for some reason, and when I had 7000 in there my brother thought there were 2000.  Would knowing that everybody will guess lower than the actual amount affect the answer to the first question?
Logged
If you're wondering what my avatar is, watch this.

Check out my logic puzzle blog!

   Quote from: sudgy on June 31, 2011, 11:47:46 pm

theory

  • Administrator
  • *****
  • Offline Offline
  • Posts: 3594
  • Respect: +6041
    • View Profile
    • Dominion Strategy
Re: Maths thread.
« Reply #424 on: May 27, 2015, 04:31:27 pm »
+1

I think as defined that problem is too vague to admit of a precise answer.  But note that problems very similar to yours have extremely unexpected results. 

http://blog.xkcd.com/2010/02/09/math-puzzle/
http://mathoverflow.net/questions/9037/how-is-it-that-you-can-guess-if-one-of-a-pair-of-random-numbers-is-larger-with
Logged
Pages: 1 ... 15 16 [17] 18 19 ... 45  All
 

Page created in 0.092 seconds with 21 queries.