7,652 reputation
41441
bio website vimeo.com/cculter
location Seattle, WA
age 30
visits member for 1 year, 1 month
seen 10 hours ago

I'm a software developer at Microsoft, working on computer vision! Outside of work, I'm interested in the inverse problem: visualization of interesting structures, such as topological groups and music. I have a soft spot for dynamical systems, including celestial mechanics and dynamical billiards.


1d
comment Simulate a 7-sided die with a 6-sided die
@neverlastn Done!
1d
revised Simulate a 7-sided die with a 6-sided die
add short version
2d
comment Simulate a 7-sided die with a 6-sided die
... Now if we test whether $x\leq y$ for some $y\neq 3a$, then we will extract less than $1$ bit of information from $x$. It's probably something like $-\sum p\log_2(p)$ bits for an appropriate expression $p$, maybe even $p_1=y/6a$. I haven't worked this part out, but anyway, it makes sense that we want the ratio $y/6a$ to be as close to either $0$ or $1$ as possible; we want it to far away from $1/2$. ...So, great, looking forward to the code! If you achieve a 1.086 roll rate in experiment, then I've definitely misunderstood something. :)
2d
comment Simulate a 7-sided die with a 6-sided die
@alex.jordan Here's an explanation that might be simpler. Imagine that for some reason, we need to test whether a uniformly random number $x$ between $1$ and $6a$ is in fact $\leq 3a$. If $x \leq 3a$, then we treat it as a uniformly random number between $1$ and $3a$ and pass it to the next stage in some algorithm. If $x > 3a$, then we treat it as a uniformly random number between $3a+1$ and $6a$ and pass it to some other stage. Either way, $x$ has one less bit of information in it than before. That bit was extracted by the comparison, which succeeds exactly $1/2$ of the time. (continued...)
2d
comment Simulate a 7-sided die with a 6-sided die
@alex.jordan I'm afraid I don't know how to formalize the idea. You can imagine that the variables are undetermined until some aspect is measured. The proof is in the experiment. I've tested your algorithm by running my code with one change: I replaced the expression std::numeric_limits<typeof(_reserveMod)>::max() / InMod with OutMod. My variable _reserveMod is your $t$. The change keeps $t$ as small as possible, rather than as large as possible. As a result, the roll rate jumps from 1.086 to 1.371!
2d
comment Simulate a 7-sided die with a 6-sided die
@neverlastn Oh, and thanks for the suggestion: I modified the answer to take advantage of (_reserveValue - answer) / OutMod == _reserveValue / OutMod and re-ran it for longer.
2d
revised Simulate a 7-sided die with a 6-sided die
take neverlastn's suggestion; show 100x longer experiment; use uniform_int_distribution instead of rand()%
2d
comment Simulate a 7-sided die with a 6-sided die
@alex.jordan There's still a small waste of randomness. When you test whether you're in the last portion of the partition, the test itself extracts information that goes unused. You could imagine keeping track of when the test passes and somehow mixing that information back in. I don't know how exactly to do that... but anyway, since you don't do it, the algorithm must fall short of the ideal rate. You can minimize the information loss by making the test as predictable as possible. That means increasing t to be much, much larger than 7! For details, see my answer.
Aug
18
comment Simulate a 7-sided die with a 6-sided die
I'm not aware of a reference for this particular technique, since I just made it up, but I'd bet that a reference exists somewhere. I think the general class of algorithms is called "rejection sampling" or sometimes the "rejection method".
Aug
18
revised Simulate a 7-sided die with a 6-sided die
dice->die, n-side->n-sided
Aug
18
answered Simulate a 7-sided die with a 6-sided die
Aug
16
comment A countability problem of $\mathbb{R}$
@ThomasAndrews Sure, that's the original prompt given to fishy. I guess I tried too hard to interpret fishy's question in a way that isn't a restatement of the original prompt.
Aug
16
comment A countability problem of $\mathbb{R}$
@egreg OP said "I can't see why $S$ could be countable but not uncountable", so I gave an example.
Aug
16
answered A countability problem of $\mathbb{R}$
Aug
16
comment Is liminf of a product equal to the product of liminfs?
@mathstudent If both sequences are convergent, their termwise product is also convergent.
Aug
16
comment Is $a \circ b = \sqrt{a^2+b^2}$ ever a group?
@MichaelTMckeon The set you defined, $\mathbb{H} = \{x + iy \mid y > 0 ; x,y \in \mathbb{R} \}$, isn't a group under $\circ$. We have to add the identity element $0$, and the imaginary numbers need inverses. The latter can be either the positive or negative reals, and it's better to choose the positives, to be consistent with the usual definition of the square root symbol. Put it all together, and that's why I said "together with the nonnegative real numbers".
Aug
16
answered Is $a \circ b = \sqrt{a^2+b^2}$ ever a group?
Aug
14
comment Is there a name for sum over one set divided by the cardinality of another set?
You probably don't mean that $A$ is a set, since you probably want to count multiple invoices even if they have the same dollar amount, and a set can't do that. You could let $A$ be a sequence or a multiset or even a discrete measure. But I'm being pedantic... could you please give a simple example?
Aug
10
answered Proof: no fractions that can't be written in lowest term with Well Ordering Principle
Aug
10
comment Golden Ratio of Primes (Amateur)
For this project, Apple LLVM 5.1 hosted by Xcode. The code is simple enough that it should be easy to port it to any environment, if it doesn't Just Work as-is.