|
|
mamgaeater
Legendary Hero
Shroud, Flying, Trample, Haste
|
posted May 10, 2009 03:16 AM |
|
|
hmm
0 points: 50% positive | 50% neutral
1 points: 50% positive | 40% negative |10% neutral
same with 2-5 and 6 cannot be counted.
positive
the chance of getting to 6 alone with 6 gems is a measly
1/64 assuming no negatives pop up.
(1/2)^6
____________
Protection From Everything.
dota
|
|
winterfate
Supreme Hero
Water-marked Champion!
|
|
posted May 10, 2009 03:33 AM |
|
|
Then you have to consider the negative chance, which counts as +2 jewels required (since you lose one level), and the neutral chance which counts as +1.
You have a (1/64) chance with no negatives, as you said.
You have a 40% chance of a negative once you have at least +1, and you have a 10% chance of a neutral outcome.
See why I hate maths? 
EDIT: Bah, lemme give it a try:
1/64 covers 50% of the possible outcomes, so another 1/64 can cover the other 50%.
5/10 = Up one level
4/10 = Down one level
1/10 = Stays the same
My head's going in circles. I hate abstract problems. 
At +0:
1/2 = Up
1/2 = Down
At +1:
1/2 = Up
2/5 = Down
1/10 = Neutral
I have no idea where to start. Where's the genetics problems? I need Punnett Squares, NOW!
*leaves thread hoping that someone else can answer this problem*
____________
If you supposedly care about someone, then don't push them out of your life. Acting like you're not doing it doesn't exempt you from what I just said. - Winterfate
|
|
TheDeath
Responsible
Undefeatable Hero
with serious business
|
|
posted May 10, 2009 03:40 AM |
|
|
Quote:
*ties a rope on Ashie's hip and drags her away from Runes of Magic*
+1
Asheera, what you ask is impossible. Nothing, on average, with the first jewels, will attain 100% chances, like in the second case, so the point is moot. It is IMPOSSIBLE no matter if the chances were 90% increase, 1% decrease and 9% remain the same. Chances NEVER EVER add up to 100% on average unless they were already 100% (second jewels) so the best you can do is with a margin of error that is acceptable to you, which I have no idea (since we're talking about money...).
Therefore, since it is impossible to achieve the same effect as the "second type of jewels" (100%), you would have to give me a maximum budget you intend to use for this. If I know your budget (and thus how many jewels), I can calculate the chances.
@mamga: no it's way more than that because you aren't limited to 6 jewels and you don't automatically "lose the game" if you get a 'bad' effect like -1, you can recover after that with +1. What you said would only be true if she had only 6 jewels and she HAD to get +6 out of them, which is a ridiculously low chance.
My solution: hack the servers or game to modify this, or realize it's just a stupid game and uninstall it before you put more emotion into your virtual items. (can't believe I'm actually witnessing the rise of another Xerox  )
____________
The above post is subject to SIRIOUSness.
No jokes were harmed during the making of this signature.
|
|
mamgaeater
Legendary Hero
Shroud, Flying, Trample, Haste
|
|
posted May 10, 2009 03:44 AM |
|
|
i speak if you had only 6 gems and no negatives pop up. thats the best possible outcome and assuming no negatives pop up and you have 6 gems to start with.
i don't know why i posted that before as it has no value whatsoever.
this is a 3d problem.
edit:
it is impossible to find an average unless you give a cap on how many jewels can be used.
an arbitrarily large number and any other number have no average.
since the opposite end of the spectrum is an arbitrarily large number an average is impossible since an infinite amount of gems can be spent.
infinity+8/2=infinity
of course i'm only in high school...
____________
Protection From Everything.
dota
|
|
winterfate
Supreme Hero
Water-marked Champion!
|
|
posted May 10, 2009 03:45 AM |
|
|
Oh, I play it too, hence why I understand the mechanic of the jewels she's talking about. 
@Ashie: Just get those 100% jewels would you?
@Mamga: Eww...3D. 
____________
If you supposedly care about someone, then don't push them out of your life. Acting like you're not doing it doesn't exempt you from what I just said. - Winterfate
|
|
TheDeath
Responsible
Undefeatable Hero
with serious business
|
|
posted May 10, 2009 03:59 AM |
|
Edited by TheDeath at 04:00, 10 May 2009.
|
Quote:
it is impossible to find an average.
No it's not. If you have the number of jewels you can use, it's easy. You already did it, with 6 jewels. But that is a small number. She mentioned a minimum of 10 anyway. But that is also too small (not worth calculating) so unless she gives me a high number of jewels as budget (which seemingly cost money, not sure if virtual or not) I won't bother. (I mean what's her budget, in terms of jewels?? bigger budget = bigger chances)
@winterfate: while I agree somewhat that most math papers or books are crap and too 'abstract' and too much math-talk, actual intuitive math that I learned to think in is so much more interesting than biology.
____________
The above post is subject to SIRIOUSness.
No jokes were harmed during the making of this signature.
|
|
winterfate
Supreme Hero
Water-marked Champion!
|
|
posted May 10, 2009 04:01 AM |
|
|
Hmmm...
10 jewels = 29 diamonds (virtual in-game currency purchasable for real money or for in-game gold; Ashie uses gold if I'm not mistaken).
At the least efficient purchase rate it's 5 USD for 100 diamonds.
So 100 jewels would be equal to 290 diamonds which is very nearly (but not exactly) 15 USD.
Just so you all know.
@Death: Ah, but biology is logical, and there are only three types of people in this world (in terms of thinking):
1) Logical people
2) Abstract people
3) People who delude themselves into thinking this doesn't apply to them.
You seem to have a more abstract way of looking at things. It'd blow my mind to try and think that way.
____________
If you supposedly care about someone, then don't push them out of your life. Acting like you're not doing it doesn't exempt you from what I just said. - Winterfate
|
|
TheDeath
Responsible
Undefeatable Hero
with serious business
|
|
posted May 10, 2009 04:10 AM |
|
|
Ok I may calculate it for 100, but not today (and don't know if tomorrow I'll get a chance to be online), it's 5 AM here
Quote:
@Death: Ah, but biology is logical, and there are only three types of people in this world (in terms of thinking):
1) Logical people
2) Abstract people
3) People who delude themselves into thinking this doesn't apply to them.
You seem to have a more abstract way of looking at things. It'd blow my mind to try and think that way.
Yes I actually visualize a lot of things both in math and programming, but you need to have extremely good logic also, or trust me, especially in programming, if you want to make it work the first time (60% or so of my small programs work perfectly first time testing).
And there are only 10 types of people in the world. Those who understand binary, and those who don't
____________
The above post is subject to SIRIOUSness.
No jokes were harmed during the making of this signature.
|
|
TheDeath
Responsible
Undefeatable Hero
with serious business
|
|
posted May 10, 2009 04:27 AM |
|
|
Ok decided to do this today
Nothing guaranteed though, this only works if you expect it to be uniform (i.e if random behaves nice )
(1/2*x) - (2/5*x) = 6
x = 60 jewels
____________
The above post is subject to SIRIOUSness.
No jokes were harmed during the making of this signature.
|
|
Ecoris
Promising
Supreme Hero
|
|
posted May 10, 2009 01:35 PM |
|
|
Quote:
Asheera, what you ask is impossible.
I think the question is this:
On average, how many jewels (of the 40-10-50 type) do you need to reach level 6. That IS a well-defined number.
____________
|
|
Ecoris
Promising
Supreme Hero
|
|
posted May 10, 2009 02:57 PM |
|
Edited by Ecoris at 15:00, 10 May 2009.
|
I can't give a rigorous answer to Asheera's problem, but I have made a small program that simulates the use of the jewels. In each iteration it uses "50-40-10"-jewels until it reaches level 6 and counts the total number of jewels used. I did this a million times and got the following distribution:
6: 15664
7: 15787
8: 26004
9: 25629
10: 30795
11: 30148
12: 32304
13: 31936
14: 31856
15: 30927
16: 30633
17: 29437
18: 28797
19: 27710
20: 26831
21: 25619
22: 24698
23: 23577
24: 22549
25: 21632
26: 20699
27: 20079
28: 18833
29: 17922
30: 17250
31: 16613
32: 16052
33: 15131
34: 14515
35: 13966
36: 13207
37: 12705
38: 12065
39: 11518
40: 10977
41: 10441
42: 9953
43: 9690
44: 9234
45: 8738
46: 8336
47: 8033
48: 7633
49: 7254
50: 6868
51: 6572
52: 6357
53: 6053
54: 5777
55: 5516
56: 5299
57: 5094
58: 4946
59: 4743
60: 4468
61: 4210
62: 3988
63: 3801
64: 3676
65: 3602
66: 3355
67: 3275
68: 2971
69: 2852
70: 2784
71: 2646
72: 2602
73: 2467
74: 2331
75: 2232
76: 2118
77: 2080
78: 1921
79: 1885
80: 1844
81: 1671
82: 1663
83: 1591
84: 1464
85: 1478
86: 1407
87: 1299
88: 1241
89: 1136
90: 1173
91: 1058
92: 1032
93: 1065
94: 934
95: 903
96: 837
97: 819
98: 749
99: 753
100: 690
101: 678
102: 643
103: 640
104: 588
105: 588
106: 515
107: 514
108: 466
109: 473
110: 435
111: 442
112: 425
113: 411
114: 351
115: 400
116: 379
117: 375
118: 353
119: 284
120: 299
121: 272
122: 273
123: 224
124: 270
125: 208
126: 193
127: 225
128: 200
129: 184
130: 191
131: 176
132: 176
133: 147
134: 157
135: 153
136: 128
137: 138
138: 140
139: 114
140: 107
141: 99
142: 79
143: 114
144: 81
145: 95
146: 70
147: 97
148: 83
149: 65
150: 78
151: 62
152: 70
153: 56
154: 63
155: 55
156: 60
157: 50
158: 36
159: 41
160: 42
161: 41
162: 33
163: 41
164: 40
165: 37
166: 37
167: 29
168: 31
169: 34
170: 32
171: 25
172: 25
173: 32
174: 33
175: 23
176: 12
177: 26
178: 20
179: 9
180: 22
181: 26
182: 18
183: 8
184: 19
185: 14
186: 15
187: 15
188: 11
189: 5
190: 12
191: 8
192: 14
193: 19
194: 12
195: 12
196: 9
197: 10
198: 6
199: 8
200: 10
201: 5
202: 9
203: 11
204: 3
205: 2
206: 5
207: 4
208: 5
209: 6
210: 8
211: 5
212: 3
213: 3
214: 4
215: 2
216: 3
217: 4
218: 3
219: 1
220: 2
221: 2
222: 0
223: 6
224: 3
225: 4
226: 0
227: 4
228: 3
229: 3
230: 3
231: 2
232: 2
233: 0
234: 1
235: 3
236: 2
237: 1
238: 1
239: 1
240: 1
241: 1
242: 3
243: 1
244: 1
245: 1
246: 1
247: 1
248: 1
249: 0
250: 1
251: 1
252: 2
253: 1
254 and above: 18 (the maximum was 314)
I.e. in 15664 out of the 1,000,000 iterations just 6 jewels were used to reach level 6. In 15787 out of the 1,000,000 iterations 7 jewels were used to reach level 6. And so on.
30.5 jewels were used on average to reach level 6. The median value is 24, i.e. there is a 50% chance that it takes 24 or fewer jewels to reach level 6.
The distribution is displayed below.
Edit: Notice (as expected) that 6 and 7 jewels are equally likely.
|
|
dimis
Responsible
Supreme Hero
Digitally signed by FoG
|
posted May 10, 2009 06:58 PM |
|
Edited by dimis at 19:05, 10 May 2009.
|
Asheera's Jewels
Ok,
I am unfamiliar with the problem (which Heroes version has something like that? - everyone seems to know apart from me), but if the number of "states" is correct in the picture below, then the answer is correct too. Here we go.
So, for example, when you are at state L3 you expect to spend 17.5072 cheap jewels to achieve the maximum (i.e. reach state L6). With the expensive ones, you can do that in just 3 steps. Hence, if the expensive jewels cost more than 17.5072/3 = 5.835733333333333 times the cost of the cheap jewels, then you shouldn't follow the "expensive" route, since it is indeed more expensive.  In other words, the price in which you buy the "expensive" jewels should change, depending on the state where you are at each moment.
This is for sure not a high school problem, so some guys should not be disappointed if they didn't make it. The only high school students which would be able to work on something like it would be ones preparing for national or international competitions in Informatics (of course there you would have more states, not just 6).
Anyway, there is a huge literature on problems like these. The picture above is essentially what is so-called a "Markov Chain", and you are performing a "Random Walk on a graph".
Another way of seeing the recursive equations (1)-(5) is by "Dynamic Programming".
Needless to say, I love problems like these. Thanks for the problem Asheera!
@all: We still have Zamfir's problem. That one is indeed a high-school level (you need to know derivatives though).
We also have some open problems by Corribus.
@Death: Will you ever write down what do we mean when we say that "A is equivalent to B"? You are not getting away that easily.
____________
The empty set
|
|
Asheera
Honorable
Undefeatable Hero
Elite Assassin
|
|
posted May 10, 2009 07:27 PM |
|
Edited by Asheera at 19:28, 10 May 2009.
|
Thanks for all the replies
And thanks for that insight dimis, I now do realize that it depends on the states as well
oh and btw:
@Winter:Quote:
Just get those 100% jewels would you?
They're not in game yet but they are in the database so may be implemented. I asked this problem because I want to know if they'll be 'correctly' priced when and if they come out
@Death:Quote:
My solution: hack the servers or game to modify this, or realize it's just a stupid game and uninstall it before you put more emotion into your virtual items. (can't believe I'm actually witnessing the rise of another Xerox )
lmao Death would you say the same if you didn't know it's about RoM or about a single player game?
____________
|
|
dimis
Responsible
Supreme Hero
Digitally signed by FoG
|
posted May 10, 2009 08:25 PM |
|
|
correction
Now that I went through the problem and others' answers, I realize you have one more state, namely L0 (on the left of L1 above). Hence, the values change since above I solved a different problem. The correct values are shown below:
where in the last line you have the expected times T0, T1, T2, T3, T4, and T5 (first as a fraction and then in decimals).
____________
The empty set
|
|
TheDeath
Responsible
Undefeatable Hero
with serious business
|
|
posted May 10, 2009 11:14 PM |
|
|
Why probability+(1+Tx)??? Where does that come from? (why "1+" and why sum them up? )
Quote:
@Death: Will you ever write down what do we mean when we say that "A is equivalent to B"? You are not getting away that easily.
Sorry, what is this about? I kinda forgot (you can send me a HCM if you don't want to pollute the thread with repeating yourself).
____________
The above post is subject to SIRIOUSness.
No jokes were harmed during the making of this signature.
|
|
dimis
Responsible
Supreme Hero
Digitally signed by FoG
|
posted May 11, 2009 05:11 AM |
|
Edited by dimis at 05:13, 11 May 2009.
|
Equivalence
"Earlier" below refers to a post on April 14th. The quote is from a post on April 27th.
Quote:
@Death:
I didn't notice that you were talking about the "if ... then ..." connective earlier when you wrote:
Summary:
True, False --> False
True, True --> True
False, True --> Unknown
False, False--> Unknown
_____________________________
With the first two cases I don't have anything to say. It is obvious that we agree.
Now let's switch the attention to the last case where we have
False, False--> Unknown
I claim that Unknown is not ok. Here is why:
1) Do you agree that
A <==> B (A is equivalent to B)
has the truth table:
True, True --> True
True, False --> False
False, True --> False
False, False --> True
?
2) If you answered Yes, do you agree that when we write
A <==> B (A is equivalent to B)
is the same thing as
B <==> A (B is equivalent to A)
?
(i.e. I can read the "A <==> B" starting from either endpoint)
3) If you answered Yes again, then, do you agree that when we write
A <==> B (A is equivalent to B)
it is the same as if we write
(A ==> B) and (B ==> A)
(i.e. A implies B and B implies A)
?
4) If you answered Yes above, now the trick comes.
By the truth table in question number 1, when A and B are both False, the result is True.
So, by question 3 above, when A and B are both False, the statements
(A ==> B)
(B ==> A)
should evaluate to True, since they are connected in between with an
"and"
and the only way an "and" can produce a True (which is what we need) is if both parts of the "and" are True.
In other words we are forced to accept that
False ==> False
evaluates to True.
Do you agree so far?
So do you agree with these?
____________
The empty set
|
|
TheDeath
Responsible
Undefeatable Hero
with serious business
|
|
posted May 12, 2009 03:10 AM |
|
|
I certainly see what you are saying, but I've never heard of "implication" in binary algebra -- I only heard about it in logic. And to be honest with you, I forgot what it means.
(i.e A implies B or stuff like that)
sorry for late reply, only now I browsed this thread...
____________
The above post is subject to SIRIOUSness.
No jokes were harmed during the making of this signature.
|
|
dimis
Responsible
Supreme Hero
Digitally signed by FoG
|
|
posted May 12, 2009 03:44 AM |
|
Edited by dimis at 04:00, 12 May 2009.
|
Ok. First of all, all these relations (the formal name for all these connectives) can be thought of as mappings (functions) {0,1}^2 --> {0,1}, so Unknown is already not accepted as an answer.
But since you agree with the above, we already determined that
False ==> False
evaluates to True (1). This eliminates one of the two Unknowns. The other "Unknown" is for
False ==> True.
Now, let's look at the cases:
Can this evaluate to False (0)?
Assume that it does (we will reach a contradiction).
Then we have the truth table:
A | B | A ==> B
---------------
T | T | T
T | F | F
F | T | F
F | F | T
But now, there is a problem. How does "A ==> B" differ from "A <==> B" ? These two functions agree on all 4 points where they are defined! And clearly, we as humans, want to say something different when we say "A is equivalent to B" compared to "A implies B". There are no real definitions for these. It is what our intuition directs. And it is reflected on their truth tables. It is the truth table that actually defines a connective. (We just associate a truth table with a connective according to our intuition.) And clearly, we want these two statements to say something different.
As a consequence, that red F above is wrong. It can not be F, because then, formally, we can not distinguish/track, any difference between the statements "A ==> B" and "A <==> B", and we really need to have such an ability (otherwise why do we have two different symbols and two different statements for the same thing?). As a further consequence, this forces that entry to be T. Remember that Unknown was initially suggested so that the possibility of being either T, or F was left open. And we just excluded the possibility of being F! So, it has to be that the red entry is T. As a final consequence, it doesn't matter what B is, when A is False; the statement is trivially characterized as a True statement just by looking at A.
End of that problem I guess. Now regarding Asheera's problem above, should I write more, or is it that you haven't read the paragraph that I have before the equations?
____________
The empty set
|
|
TheDeath
Responsible
Undefeatable Hero
with serious business
|
|
posted May 12, 2009 04:02 AM |
|
|
Yes I have but I googled for Markov Chains and I got wikipedia-style results, equations and unintuitive stuff to learn from. You know, I would prefer it more english/logical first, then the equations, cause otherwise I can't understand a thing.
If you feel like you can explain it more intuitively/logical and how it comes to those equations. Too many symbols in math confuses newbies (and I do not mean newbies at math, but newbies just at the respective subject, like in this case, Markov Chains).
Where does it come from? Why always "1+Tx" in parantheses for example?
____________
The above post is subject to SIRIOUSness.
No jokes were harmed during the making of this signature.
|
|
dimis
Responsible
Supreme Hero
Digitally signed by FoG
|
|
posted May 12, 2009 05:54 AM |
|
|
Right. Well, you can factor out 1 from all these parentheses and you only have just one 1 (no typo). What do I mean? Let's see.
[Btw, I will always refer to the post that has 6 states L1, ..., L6 above, since Asheera actually wanted the same thing for 7 states]
First, let's start with something easy. Look on the far left.
If you toss a coin one time, with probability 1/2 you stay in place, and with probability 1/2 you move right. How many coin tosses do you expect to be required to move one place right? To make it even simpler and intuitive, how many times should you toss a fair coin until it gives you 1 Heads?
The answer is 1 / (1/2) = 2, and in general, if the probability of getting Heads is p, you expect to toss such a coin 1/p times until it gives you one (the first time!) Heads.
You can look up for geometric distribution for this. If nothing really good comes up, I can make a post on properties of coins and coin-tossing. Just let me know.
By the way, since I had the similar problem like you and I was also tired at some point of looking left and right for the appropriate definitions, tools, tricks, and fundamental problems in randomized algorithms, I created some brief notes. You might want to have a look here (the last part about Markov Chains is not well written, but the main ideas really appear earlier).
Anyway, let's come back to the problem at hand.
We are at state L1, and we want to figure out the expected time needed to reach L6.
Clearly, the time required is a random variable (the randomness depends on the coin tosses). So, say the time required is t_1. (subscript 1 because of L1)
Moreover, define T1 = E [t_1] = expected value of t_1.
In other words, T1 will tell you in how many steps on average you reach L6 (starting from L1).
Now, what is the expected value of a random variable?
In a discrete space like this, the definition essentially tells you to sum up all possible values for t_1 weighted by their probability of appearing.
The main trick is that t_1 essentially depends on t_2, where t_2 is the time required to reach L6 starting from L2. And this is true for any sequence of coin tosses.
In other words,
t_1 = t_{1->2} + t_2
i.e. the time is decomposed until you reach state 2 for the first time, and then the time (t_2) which is required from that point on.
So, the expectation is:
E [t_1] = E [ t_{1->2} + t_2 ]
Due to linearity of expectation, the right hand side can be re-written as:
E [t_1] = E [ t_{1->2} ] + E [ t_2 ]
or according to my notation:
T1 = E [ t_{1->2} ] + T2
But what is E [ t_{1->2} ] ? Essentially, this is the expected number of coin tosses (fair coin) until you reach the first time Heads, which is 2. So we have:
T1 = 2 + T2
If you check my solutions, T1 always differs from T2, by exactly 2 (independently of how many states we have! - check both of my answers above).
Now, how is this thing related to what I initially wrote?
Consider any walk on that graph that starts from L1. T1 tells you what is the expected number of steps (until you reach L6). But ANY such walk that starts from L1, will make at least one step (hence the 1), and depending on the coin toss (H/T), will take you either to L1, or to L2. By definition of expectation, you sum up over all such possibilities
(possibilities here = all possible strings of H, T that lead you to L6, each one coming with some probability that Asheera has defined). So we sum up terms of the form Probability(string)*Length(string that leads to L6). But we really don't have to look that far away. Whenever you are in L1 you toss a coin. Either it will take you in L2, or you will remain in L1. Well, if you remain in L1, what is the expected amount of steps to reach L6? Well, nothing has changed really. It is still T1. While if you visit L2, then you expect to reach L6 in time T2. That's the whole idea of expectation.
So, concluding,
* with probability 1/2 the coin gives you Tails and stay in L1.
This justifies the part
0.5(1 + T1)
* and with probability 1/2 the coin gives you Heads and you move on to L2.
This justifies the part
0.5(1 + T2)
So, only with logic, you have:
T1 = 0.5(1+T1) + 0.5(1+T2)
Another way of writing it is:
T1 = 1 + 0.5T1 + 0.5T2
since you are going to spend 1 step anyway , and if it gives you T you still expect to reach L6 in time T1, while with H you expect in time T2.
If you think about it, it is the same thing for a simple fair coin.
You expect to get a Heads with 2 coin tosses.
Say you toss a coin and the outcome is Tails. In how many coin tosses do you expect to see a Heads from now on? The answer is AGAIN 2 (not 1 because you already tossed it once and you failed). That's the whole point.
Similar are the arguments for all the other cases. Just check. It's a one-step lookahead. Hence that 1 appears.
Of course we can be a little bit more formal here, since technically we are exploiting the so-called linearity of expectation, but the intuition (for me) is the one I have above.
____________
The empty set
|
| |
|
|
This thread is pages long: 
