3 ms·
Was thinking the formulation sounded weird, as from this naive armchair that seems like a straight mutual information problem. https://en.wikipedia.org/wiki/Mut
by motohagiography 5y ago
Was thinking the formulation sounded weird, as from this naive armchair that seems like a straight mutual information problem. https://en.wikipedia.org/wiki/Mutual_information https://en.wikipedia.org/wiki/Mutual_information
The red/blue beads thing is a metaphor for two random variables (red, blue) and the question seems to be about the information between them. Evenness and oddness is really a proxy for the effect of prior states on future ones. It's very likely I have a comedic misunderstanding of this, but if someone would like to provide the requisite humiliation, I'd be interested in why this interpretation is wrong.
- Sniffnoy 5y agoThe problem described isn't a metaphor or a proxy; it's not about some other thing like mutual information. It's about exactly what it says it is: evenly-spaced (arithmetic) subsequences. More formally, given k, you have the set {1, ..., N}, and you want to produce a map from {1, ..., N} to a two-element set (which we can denote {blue, red}) such that there are no blue arithmetic sequences of length at least 3, and there are no red arithmetic sequences of length at least k. The question then becomes, given k, how large can N be with this remaining possible?