Suricrasia Online @SuricrasiaOnline@cybre.space

@elomatreb N would likely range somewhere between 10 to 100, maybe 1000? idk yet but no more than 1000

apparently d-ary trees have more efficient priority-update operations, but slower delete-max operations. since I'll never be doing the latter maybe I could use this

@zardoz I think that this would only put x into the list if it is greater than the maximum value? but I want to put it in if it is *less* than the maximum value. I want to hold the list of smallest objects passed into insert(X)

@zardoz did you mean top = x?

wanted: a data structure that holds a list of N objects and has the following properties

insert(X) - adds X to the list if there is room for it. If there is no room, it compares X to the maximum value currently in the list. If it is less, the maximum value is removed and X is put in its place.
get_list() - returns the list. the order of the elements does not matter

essentially, this data structure stores the smallest N values that were passed into insert(X)

now I've got some efficiency needs

insert(X) should take O(log N) time (or O(1) if amortized), and get_list shouldn't take longer than O(N^2) or something. basically insert(X) gets called a *lot* and get_list only gets called at the very end

also, the data structure shouldn't take more than O(N) space.

I'm thinking I can just use a max heap for this, but I was wondering if there were better options that aren't necessarily heap-based 🤔

running your robot girl body for 8 billion years on the beta decay of a single, pencil-sized rod of Uranium-238

writing some absolutely heinous c tonight

blackle "staying up till 4 am every night this week apparently" mori

Read Decision theory and decision behaviour by Anatol Rapoport

hello welcome to burger king, would you like a whopper or to be entered into a lottery with a 30% chance of getting a whopper and a 70% chance of getting some chicken tenders

@lucidiot
there are VNM utilities though which are neat
https://en.wikipedia.org/wiki/Von_Neumann%E2%80%93Morgenstern_utility_theorem

@lucidiot that's left as an exercise to the reader

anyway decision theory is cool and so is expected utility calculation

you tell the oracle you think that's a bad deal. they roll their eyes and mutter something derogatory about decision theorists. then, they ask you what price you think is fair.

From our earlier calculation, if we know when the banana will be ripe, we are guaranteed 5 units of utility. if we don't, we have to rely on expected utility to give us about 4 units of utility. therefore, the *knowledge* of when the banana will be ripe has 1 unit of utility!

you hatch a scheme in your head. obviously you don't want to say that a fair price is -1 utility, since then you break even and nothing is gained. instead you say to the oracle:

"I'll eat half of a different, underripe banana"

that should be -0.5 units of utility for you. and to the oracle, that sounds like ironic justice. they agree, and you've just gained 0.5 units of utility from the deal!

right now, based on expected utility, you should eat the banana tomorrow. eating it today gives you an expected utility of 2, and tomorrow the expected utility is 4.

now suppose an oracle appears in your kitchen, and tells you they know with 100% certainty if the banana is ripe today or tomorrow. However, they tells you that you must perform an unspeakable act to get the information (a little worse than eating an underripe banana, and you calculate it has a utility of -2)

if you know for certain when the banana will go ripe, you are guaranteed to get 5 units of utility. however, you must experience the unspeakable act of -2, so the true utility is 3, which is less than if you just wait till tomorrow! so even though you will always get to experience the bliss of a ripe banana, you're no better off.

...

there was a cool chapter in my decision theory textbook about how if you have N states of nature with some probability distribution, M possible actions you can take, and an NxM table of utilities for each combination of nature+action, you can quantify the utility of information about the state of nature.

for example. suppose you have a banana on your counter that looks kinda ripe. you have the choice of eating it today or tomorrow. it's either fully ripe and tomorrow it will be overripe, or today it is underripe and tomorrow it will be just right, but you don't know. Though you give it a 50:50 chance.

Let's say you HATE underripe bananas, and give them a utility of -1. If it's just right, that has a utility of 5, if it is overripe, that has a utility of 3. our utility table is:

today tomorrow
today 5 -1
tomorrow 3 5

...

(I didn't actually do the calculation to see what bayes theorem tells us what the posterior likelihood would be I just took 50% for examples sake lmao)

if you believe that you have a 90% likelihood of winning a lottery, and then 100 of your friends lose and you use bayes rule to update your likelihood to 50%, did you just lose information

I'm thinking now about how you can compare the entropy of a prior and posterior distribution, and the difference will be the number of bits of information gained between them. I'm not sure if this is valid 🤔

what is a fractional bit? it's a bit with uncertainty.

For example, if you ask me a yes/no question and you know that half of the time I just answer randomly, and the other half I tell the truth, then my answer will contain 1/2 bits of information.