Imagine you're going to walk a ten mile distance. In every 1/10 of a mile mark there's a stack of gold coins in the ground. You know each stack has between 1 and 100 coins randomly. You can only see one stack at a time. Along the ten miles, you can only grab one stack with you, never turn back and never switch the stack once you have chosen one. You can only do this challenge once./Sci/entifically and mathematically speaking, what strategy should you use to secure the maximum amount of gold?
>>17032754Do you have a calculator with you or not?
>>17032754>randomlydefine how the stack value is determined
So, my original guess is that if you get a bag with 90+, you should just take that.In most iterations, there is a bag with 100 coins. Waiting for 100 and only 100 is good, but there is a chance you can end up with whatever is the last bag.What I've done is probabilistically calculate the chance that the bag you're on is the best bag. If it's better than 50/50, you keep the bag. In most cases, it's the best bag. It's mostly 100, and if it's not 100, then it's usually 97+. In very rare cases, you skip a 99 bag early when it's more likely to get a 100 bag, but then you keep a 97 bag when the 100 bag is rare, which there sometimes is or isn't. This method gives a few coins better result than picking the first 90 bag. You can check if it's worse than 100 only and sometimes getting last bag.
>>17032841Here is a nice sequence where there is no 100 bag and the statistical method gets a low last bag
>>17032841no dude. if the first stack is 99 and you take it, you'll most likely regret it.if there is only one stack left, you have no choice but to take it; the expected value is 50.5if there are two stacks left, you strategy would be, if the 2nd-to-last stack is 50 or lower, don't take it, take the chance of the last stack; otherwise take it. with this strategy the expected value of 2 stacks is 63.with 100 stacks in front of you, the expected value should be very close to 100.
>>17032935>if the first stack is 99 and you take it, you'll most likely regret itwhat? to put this in real terms, a 1oz gold coin goes for just over 4kso you're saying in this scenario you would give up 396,000 for a chance at 400,000?
step aside, nerds
>>17032935What? People who only read you must be very confused.
>>17032754Intuitively with 100 chances and a spread of 100 the chances of 100 are pretty good but only at the start. I believe the optimal strategy will be to set your acceptance limit that you adjust based on how many rolls you have left. Intuitively it probably should be something like "more than 50% chance of getting a better number than X in the future". With 100 pulls left the chance of a 100 is 63% so you probably only take the first pile if it's 100, the chance of 100 drops below 50% only at 68 rolls left so that would probably be the spot where you start going for 100 or 99, you continue that up to 34 at which point you swap to 100,99 or 98 and so on.If you don't swap your strategy then the highest expected value at the start is for picking 96 or above on sight but I don't think that's correct play overall.
>>17032754Probably has to do something with Euler's number so take the first stack that is higher than each of the first three stacks.
>>17033020Or rather take the first stack that is higher than each of the first 100/e % stacks that you see
>>17032754This is a good one gents, don't share solutions. Worth your time to solve and commit the concept to memory.Post 3 distance markers and stack size at each and whether you take or leave it and I will tell you if you are right or wrong. Also, distances and values you pick are more important than whether you take or leave btw. >>17032841>>17032848>>17032945Wrong>>17032954keep working at it.
You work your way backwards, starting with the tenth stack of coins. If you've reached the tenth stack and haven't selected yet, then you must. Your expected payout would be 50.5 coins at this point, and with that, you can work backwards. At the ninth stack, you should take if it has 51 or more coins. The expected utility here would be calculated by taking the average of what you're expected to get if you grab here or skip, which is going to be 51-100 (for grabbing) and 50.5 (for skipping). Average of 51-100 is 75.5, and if you average that with 50.5, and you get 63, which is the expected payout for playing at the ninth stack onwards. So, for the 8th stack, you should then grab at 64 or more coins. Continue this chain going all the way to the first stack, and you'll end up with the optimal strategy.
>>17033267it's a 10 mile walk with 100 stacks, not one mile and only 10 stacks, but the strategy still applies.
>>17033270ten miles? who's going to walk ten fucking miles? I'll take the first stack.
>>17032943Their greatest fear will be their gf will sell out for 396,001>>17033104Already ran off to murder-suicide? You can't come back to reply
>>17032943obviously (you) are not an average intelligent rational economic person, aka a jew.it's a fair point that people have different risk seeking/aversion profiles. but in this case, you are mistaken. you are not betting 396K for a 400K payout; you give up 396K in exchange of 99 more chances. and in the worst case you'll end up with $202K.
>>17033364since you niggers are so lazy, I'll do it. (using floating point so it may not be strict)1=50.50, 2=63.00, 3=70.03, 4=74.67, 5=78.01, 6=80.54, 7=82.53, 8=84.14, 9=85.48, 10=86.61, 11=87.57, 12=88.41, 13=89.14, 14=89.78, 15=90.36, 16=90.87, 17=91.33, 18=91.75, 19=92.14, 20=92.49, 21=92.81, 22=93.10, 23=93.38, 24=93.63, 25=93.86, 26=94.08, 27=94.29, 28=94.48, 29=94.66, 30=94.83, 31=94.99, 32=95.14, 33=95.29, 34=95.42, 35=95.55, 36=95.67, 37=95.79, 38=95.90, 39=96.01, 40=96.11, 41=96.20, 42=96.29, 43=96.38, 44=96.47, 45=96.55, 46=96.63, 47=96.70, 48=96.77, 49=96.84, 50=96.91, 51=96.97, 52=97.03, 53=97.09, 54=97.15, 55=97.20, 56=97.26, 57=97.31, 58=97.36, 59=97.41, 60=97.46, 61=97.50, 62=97.55, 63=97.59, 64=97.63, 65=97.68, 66=97.72, 67=97.75, 68=97.79, 69=97.83, 70=97.86, 71=97.90, 72=97.93, 73=97.96, 74=97.99, 75=98.02, 76=98.05, 77=98.08, 78=98.11, 79=98.14, 80=98.17, 81=98.19, 82=98.22, 83=98.24, 84=98.27, 85=98.29, 86=98.32, 87=98.34, 88=98.36, 89=98.39, 90=98.41, 91=98.43, 92=98.45, 93=98.47, 94=98.49, 95=98.51, 96=98.53, 97=98.55, 98=98.57, 99=98.59, 100=98.61, 101=98.63, 102=98.64, 103=98.66, 104=98.68, 105=98.69, 106=98.71, 107=98.73, 108=98.74, 109=98.76, 110=98.77, 111=98.79, 112=98.80, 113=98.81, 114=98.83, 115=98.84, 116=98.86, 117=98.87, 118=98.88, 119=98.89, 120=98.91, 121=98.92, 122=98.93, 123=98.94, 124=98.95, 125=98.96, 126=98.97, 127=98.98, 128=98.99, 129=99.00, 130=99.01,
>>17033364The worst case is last bag 1 coin
I haven't checked if those expected values are correct or even looked at the expected value formula, but, I think everyone can agree that 99 and 100 are equally likely and getting a 99 before a 100 is like 50/50 so that table has like a 50/50 chance to lose
>>17032754>/Sci/entifically and mathematically speaking, what strategy should you use to secure the maximum amount of gold?A trick question. The optimal strategy is to recognize that material possessions are an impediment to spiritual development, leave all the bags on the side of the road, and pursue a life of meditation and asceticism.
>>17032754>/Sci/entifically and mathematically speaking, what strategy should you use to secure the maximum amount of gold?Beat up the nerd telling me that I can't turn back or take more than one stack, then I walk the whole ten miles and gather up all the gold.
My marginal utility function for a gold coin when I already have 90 rapidly falls to zero so just grab the first one with more than 90 that you see.
Assuming the number of coins in each pile is truly random and independent of all other piles, it boils down to a binomial distribution problem: given that you see a pile of n coins at mark m, what are the odds there is at least one pile remaining with more than n coins? If p < 0.5 then statistically you should settle for the current pile.If you see 100 coins at any point, you should take it of course, but the same is true if you see 99, as even at mark 1 there is never p > 0.5 that you will see 100 later.You should settle for:98 coins at mark 17 or later97 at 4596 at 5995 at 6794 at 7393 at 7792 at 8091 at 8290 at 84(etc.)It slowly decays but basically you should only accept <80 if you're at mark 90 or later.
>>17032754>you can only grab one stack with yousays who ?I'll take as many as I can carrytry to stop meyou cant
>>17034465Sorry I was slightly off, I forgot to subtract the probability of exactly 1 success from the cumulative probability of at least 1 success.The approach is still correct but the exact numbers are different and actually mean you should be less willing to settle early to maximize value. Statistically you shouldn't even accept 98 coins until after pile 66; you are >50% likely to find either 99 or 100 in one of the remaining 34 piles.
>>17032754I just randomly made 10 sets of 1-100, and there were high 90's in them. Or get a refractor telescope and check out what's ahead.
>>17032754Checked this?https://en.wikipedia.org/wiki/Secretary_problem
>>17034465This is not really a complete solution to even be able to be testedJust like racist guy's buffoonery, I don't always have time to prove you wrongYou can clearly see here that racist guy's better than expected value solution wins about just over 60% of the time, while my solution is winning just over 70% of the time
>>17032754~30 or ~80.If its always random, you can wait until you hit 95+.But if you think someone's fuggin' with you in some way, you'll want ~30 or ~80 depending on if you weakly or strongly distrust them.The question is really about who put the gold there and why.
>>17034832Given a pile of x coins at mark y (and assuming both are out of 100 in this case) the probability of finding more coins at at least one later mark follows a binomial distribution, where X is the number of successful trials:Pr(X >= 1) = 1 - Pr(X = 0)Pr(X = 0) = C(n, 0) * p^0 * (1 - p)^(n - 0) = (1 - p)^np = 1 - x / 1001 - p = x / 100n = 100 - yPr(X >= 1) = 1 - Pr(X = 0) = 1 - (x / 100)^(100 -y)You should take the current pile of coins if Pr(X >= 1) < 0.5, i.e. if the odds are less than 50% that you will find a bigger pile later.So in the first visible run in your screenshot, for example, I would pass up on the max sack at 42 with 98 coins since there would be still a 69% chance of finding a better one. But I probably wouldn't end up with sack 100 with only 33 coins at the end.In theory you could also run a risk-averse or risk-taking version by changing the threshold from 0.5 to something higher or lower, but I doubt they would outperform the baseline one.
>>17034856>But I probably wouldn't end up with sack 100 with only 33 coins at the end.OkI'm glad you agree with me mostly. Just look at this and see that expected value table is losing to 100 only.
>>17034859I did 100 trials myself (each trial calculated automatically ofc but I entered results manually) and I think the shortfall of my approach is that it is left holding the bag at the end more often than I expected.I tried another 100 trials with the probability threshold changed to 0.9 (i.e. accept the bag if there is even a <90% chance of finding a better one) and the result was noticeably better. Now I'm wondering whether there is an optimal risk profile somewhere between the two. Alternatively, maybe the threshold could get more conservative as it approached the end to avoid bagholding scenarios while having less of a chance of settling too early.Or maybe we're all overthinking and the best solution is just "take the first one above 95".
>>17034859>>17034865Also I'm dumb and didn't read and just realized you came up with more or less exactly the same solution way before me, just not described the same way I came at it.Though I don't understand how "expected value table is losing" in your trial, doesn't it get the highest total?
>>17034869Well, the way the puzzle is is that you only do it one time. So the most likely thing is that there is a 100 bag and expected value and 100 only both find it. 100 only has more wins, meaning it's more likely that 100 only gets a 100 bag and expected value gets a 99, not the maximum on 1 run.
>>17034869>>17034873Anyways, I had improved my strategy by getting rid of some guaranteed losses. I had a small mistake where I wasn't adding some kept bags to my total when there was not a win. My average win rate is ~76%, it's a bit hard to understand without college statistics, no high schoolers here. You can see I'm getting about 150 more wins than the table in this thread at a cost of 5000 coins or so, like 33 coins for an extra win. You would want to argue that you could buy the last 250 wins for the same price.
>>17034904The racist guy has a tighter algo because he takes a 98 at the bottom. I am assuming it is the first 98 which is actually kind of close, but the second one is a no brainer. Your algo is kind of trash though anyone who just only takes 94+ beats you, that is their lowest take is 94. Heruistically, you could just take a 98 anytime it shows up because it is unreasonable to play for 98 only. Its a kind of inversion than to always take 98 or better.It may not be optimal but my guess is it would improve your strategy.
>>17035018I understand completely. I think it comes from fraternity statistics, business statistics, and church where you have alot of stupid people just reciting stupidly to other stupid people. Are you catlic by any chance? If you can trick someone young, they might wrongly recite you their entire life. Tell me about your hazing experience. Honestly, I get it. Most people avoided this OP because it reeks of irrelevant time wasting question, and what it is irrelevant to is your preconceived notions of gay dominance and whores at the whorehouse. Just make some random claim whenever there is no obvious evidence against. You can't even test by yourself whether 94+ gets more wins. Maybe another stupid person will recite with you. I can't believe how dumb you are. If this was your spikeball disc golf league and someone went 76-24 against you going 60-40, you would be claiming you won as long as your 60 wins won by a bigger margin. Even 100 only went 65-35, but keep licking racist guy's ass. That's all you wanted to do anyways. Faggot.
>>17032754If s_{n-1}=z#s_{n} = floor{z}+1And s_{n} = \frac{(100-z)}{100}(\frac{100+z}{2})The acceptance value always goes up by atleast one so you only accept 100 for the first 70 percent then you start going lower
>>17035130s_{n} = \frac{(100-z)}{100}(\frac{100+z}{2}) + \frac{z^2}{100}I forgor
Fun problem. You can use dynamic programming to find an optimal policy.>>17033267>>17033376Unless I made a mistake in my math or code, I believe these answers are right (provided that the goal is to maximize the expected amount of gold). Other approaches in this thread may be good too, but I haven't looked closely at them yet.>>17032935This also seems about right, except I don't think it's ideal to reject a stack of 99, even if it's the first one.
>>17035419The problem doesn’t deal in partial coins, so the minimum for you to take a given pile is that it’s strictly greater then the expected value of the rest of the pilesGiven this, the acceptable amount should be going up faster then you predictedIf the estimated value of the next 99 stacks is 99.5 then it would be a mistake to take 99
>>17035428>The problem doesn’t deal in partial coins, so the minimum for you to take a given pile is that it’s strictly greater then the expected value of the rest of the piles>Given this, the acceptable amount should be going up faster then you predictedThis first line is clearly true (when the expected values are not integers, of course). That said, I'm a bit confused by the second line. I don't think it makes sense to speak of "the" acceptable amount, since many different choices can lead to the exact same strategy (precisely because we're not dealing with partial coins). My choices definitely aren't the largest possible, but I see nothing wrong with that.Am I missing your point here?>If the estimated value of the next 99 stacks is 99.5 then it would be a mistake to take 99Agreed. However, that value seems to be less than 99: by my calculations it's about 98.609, which agrees with >>17033376.
>>17035463When i think of it, I was moving with the presumption that if my minimum acceptable value for the next stack was n I shouldn’t take anything less then n+1, which is wrong. I was confusing the min acceptable value with the predicted valueI think your numbers are correct
>>17035481All good, that makes sense. I think the 98.609 threshold I gave is actually wrong due to an off-by-one error (it should really be the one before, 98.591), but for what we've been discussing it makes no difference. Hopefully I haven't missed more serious mistakes!
>>17035500value, not threshold*
>>17035463Your numbers are off on at least one point. We played your strategy the same up to 2, and then we just play 2@62, but this has higher EV than 2@63.
>>17035508Well the numbers in that post aren't quite mine (that isn't my post). Those seem to be correct _value function_ values, but not thresholds. My thresholds are 1@0, 2@50.5, 3@63, and so on.I think I agree that 2@62 is better than 2@63. But what about 3@62 vs. 3@63 :)?
>>17035538If 2 is optimal, then 3 is not optimal and your strategy is not optimalelse if 2 is not optimal, then your strategy is not optimal.Given 2, 3@62 > 3@63 2@50.5 is also not optimal btw.
>>17032754game of googol n/ehttps://youtu.be/OeJobV4jJG0?t=4m30s
>>17035945>If 2 is optimal, then 3 is not optimal and your strategy is not optimalWhat do you mean by "2" and "3" here? There is an optimal strategy for the last 3 stacks, and it is necessary that such a strategy (or more precisely, the part of the strategy pertaining to the last 2 stages) is also optimal for the last 2 stacks. In particular, there is a strategy that is optimal for both the last 2 and last 3 stages. I don't see how your stated implication works unless I'm misinterpreting it somehow...>else if 2 is not optimal, then your strategy is not optimal.Agreed.>Given 2, 3@62 > 3@63>2@50.5 is also not optimal btw.Why?
>>17035983they are not optimal because there is at least one other value that results in more coins across the entire sample space. For example, Taking 2@50.4+ is better than 2@50.5+
>>17036039The thresholds 2@50.4 and 2@50.5 specify the same strategy since each stack has an integer number of coins. I believe both are optimal choices (in general, any threshold [math]50 < t \leq 51[/math] should work).
>>170360522@49.9 > 2@50.
>>17036061These lead to the same strategy if 2@x means that we decide to pick up when the amount is [math]\geq x[/math], so they have the same EV. I don't think this strategy is as good as the one given by 2@t for [math]50 < t \leq 51[/math]. I believe the EV for 2@49.9 is 62.995, while 2@51's (or 50.4, or whatever in the aforementioned range) is 63.
>>17036070your math is wrong.Change the way you are looking at the problem. If you had 49.9 dollars and I offered a game of flip coin where you pay 49.9 dollars to play, but if you win you get 50 dollars, is that a game you would play?
>>17036073No, but what does that have to do with this? And to avoid potential confusion, the EVs I mentioned in my last reply aren't just for the value of the second stack, but also factor in optimal play for the final stack (i.e., taking it if nothing was taken previously).
>>17036073right so you won't pay 49.9 to play for 50, but you will leave 49.9 on the floor to play for 50.
>>17032754See first stack. Let's say it's 35 coins. Do probability. What is the statistical likelihood that the other 99 stacks are less than 35? Answer is tiny likelihood. Don't pick up stack. Next stack is 4 coins. What's the probability that 98 other stacks are less than 4? Answer is tiny likelihood. Keep walking.When I reach a point of 30% or higher likelihood that the remaining stacks are less, I'll take that stack.
>>17036086I won't pay 49.9 to play the coin game because my expected return is[eqn]E[50X - 49.9] = 50E[X] - 49.9 = 25 - 49.9 < 0.[/eqn](To model the coin, I assume [math]X[/math] is Bernoulli distributed with parameter 0.5.) This is different from our gold situation, where the expected return after giving up the 49.9 is positive:[eqn]E[Y - 49.9] = E[Y] - 49.9 = 50.5 - 49.9 > 0. \qquad (Y \sim \textrm{DiscreteUniform}(1, 100))[/eqn](In the above [math]Y[/math] denotes the number of coins in the final stack.)
>>17036119-24.95 * 998 (average entrance cost) + 50 * 998 (average result of entry) + 74,95 * 1002 (average non-entrance result)-25 * 1000 (average entrance cost) +50 * 1000 (average result of entry) + 75 * 1000(average non-entrance result)Why don't you count the money left on the table tho:1. Where did it come from?2. Where did it go?
>>17036073>If you had 49.9 dollars and I offered a game of flip coin where you pay 49.9 dollars to play, but if you win you get 50 dollarsThat's not the problem. You would pay 49.9 dollars for a ticket that has a payout of 1-100.
>>17032754If the stacks were not independently random then you grab the 100 coin stack.Generally you do a choice algorithm where you grab a stack if it is a certain size or larger ans that minimum threshold decreases as the number of stacks undiscovered decreases. The probability equation builds backwards where theblast stack you have to take, the 2nd to last stack you take 51 coins or greater. While the 30 stacks you probably aren't accepting fewer than 90 coins.Just build it backwards where you take if the result is greater than the expected outcome of continuing.With the range of 1-100 the last expection is 50.5, which is why choice 99 is 51 coins. Choice 98 is something like 100*(1 - (50/99)^2) = 75 coins.Choice 97 is 87 coins.I probably did the math wrong.
>>17036168Sorry, idk what you're saying/asking here. All the money is accounted for in my calculations, no?In the gold problem, the money I'm leaving behind (provided it's [math]\leq 50[/math] coins, since the number of coins is an integer) is worth less on average than an opportunity to decide on the final stack.
>>17036330I think there is a modeling problem because the 50 case at 2000 coins has a value of 100000 which contradicts your model, because this model is equivocating two events with a decision as if they are a single one, by equivalent result.If entrance fees are mapped to average results of that reentry, the average reentry <50 losers swallow the input map of <50 entrances which leaves the >50 members as risk free winnings. I don't know how that first one adds up to approach 100100 Maybe there is some implicit smuggling in of arbitrary metrics or something. Though it isn't exactly obvious where, I think the model is overcounting entrance fees some kind of way.
>>17036444I don't know if I fully understand what you're saying here. What exactly do you mean by the "50 case at 2000 coins"? Do you mean a version of this gold problem where each stack has 1-2000 coins and we're considering the 50th stage? If so, my approach certainly doesn't give that stage a value of 100000 (and for that matter, all stages are valued less than 2000, as needed). I'm happy to explain more if you want.Also, if your post does pertain to the gold problem, I don't model entrance fees at all, since they don't exist in the original problem.
>>17037304You must give up the current stack to keep playing the game. This is the entrance fee by equivalence, lose x for opportunity y. What I am saying is I think the other model is overcounting these entrance fees, two upward shots at >50 is going to strictly be greater than a single shot but that model doesn't reflect this.
>>17037321>You must give up the current stack to keep playing the game. This is the entrance fee by equivalence, lose x for opportunity y.Yes, this makes sense>What I am saying is I think the other model is overcounting these entrance fees, two upward shots at >50 is going to strictly be greater than a single shot but that model doesn't reflect this.What is an "upward shot"? I don't see how we're overcounting by using the observed number of coins on the current stack as the entrance fee: isn't this exactly what we are losing by moving on without taking the stack (provided we haven't already picked up a stack, of course)?
>>17032754>>17032841nope. it's 1 to 100 coins randomly, so every stack could be 1. what you do is pick the first stack that has more than 50, or, if you reach the half way point finding none, then you begin to reduce the number you'll accept proportionately to how many stacks remain. if you get to the last stack having taken none, you take it.
>>17032754nice
