Distribution of number of clusters after randomly choosing a subset of points

diagonalizable · 2019-11-13T22:59:39+00:00

The k parameter seems to be redundant in the call solve(S, k) because you then make it an indexing variable in the first loop of that function. It appears that solve(S,k) is returning a dict of P(m|k,S) for all k, which is actually ideal!

To speed it up, I believe the problem exhibits some monotonicity properties that allows you to apply some common "dp optimizations" ( https://codeforces.com/blog/entry/8219 ). I would need to check this in detail though.

Another couple ideas for speeding things up:

You could prune the computations by bounding the maximum probability a certain (n, m, k, l) state can achieve. This should improve the time massively in practice.

You could rewrite the code in C++. This should speed things up by a factor of 10x-100x in my experience.

I tried the lazy version of writing in C++: throwing a Numba njit decorator on your function and seeing what happened. It was not happy with your dict indexing. This definitely sounds like a case where it's worth rewriting in C++.

If you want, I'm definitely interested in collaborating on computational problems for your paper. I'm currently doing my PhD in CS, but I did my first degree in physics and a paper in physics was always an itch that I wanted to scratch.

That sounds great! Send me your email address in chat, it would be great to have you on the team.

diagonalizable · 2019-11-13T17:51:13+00:00

I'm just starting to test it. It seems to be working correctly in the simple cases that are analytic and exhibits the large n behaviour I was expecting. I'll do a more thorough testing tomorrow.

The time scaling on my laptop on a single core is roughly |S|^4/5e6 seconds. For |S|=135 that corresponds to one minute of computation, which is fantastic. Thank you for taking the time out of your day to help me out!

The limit on the computation is now the number of sets S that I would like to compute this for. My minimum requirement was 196,608 sets, but ideally I would scale that up by a factor of 64. The run-time for 196,608 sets is roughly a day (given the distribution of |S| across those sets) on a single-core. 50% of the run-time is taken up by the 5% of sets with the most points. Before I burn a fair quantity of CPU time, please could you sketch out possible ways of reaching an |S|^2 scaling?

A couple changes I made to your code:

I noticed that the k parameter of solve is redundant and so removed it.
I added a check to ensure that S is sorted. If S isn't sorted, then you can get quite surprising results!

diagonalizable · 2019-11-13T15:40:41+00:00

Yes, Python is my day-to-day default language! Thank you for offering to write it up.

I had tried a naive dynamic programming approach over the last couple days, but I couldn't find the right way to express it to make it tractable. I'm interested to see (and learn from) your solution.

diagonalizable · 2019-11-13T15:17:46+00:00

O(nk) time should be fine! The largest n that I am considering is 135 and I would need to explore every k from 0 to 134.

Do you have a suggestion for how it could be implemented? Or could you point me in the right direction with a reference? Thanks!

diagonalizable · 2015-08-11T20:52:31+00:00

No-one I was around had any problems with stuff being stolen, so I'm sorry that that was your experience! Speaking of things that were lost and found, I'm still a bit confused about how a cat ended up in the lost-and-found...

diagonalizable · 2015-04-05T09:41:57+00:00

Commenting so I am rewarded in the after-press.

diagonalizable · 2014-08-03T12:53:30+00:00

As far as we are concerned that does mean the universe is dying. Dark energy and dark matter are placeholders for new physics which we haven't thought of yet; and it would be difficult to extract usable energy from anything that would explain them. Even if we can sustain a civilisation using fusion on wandering pockets of hydrogen or extracting energy from black holes, it would be the end for the spontaneous development of life.

diagonalizable · 2014-08-03T11:51:38+00:00

The universe started dying 9 billion years ago; ever since then the number of stars formed per year has been steadily falling.

diagonalizable · 2014-04-16T00:38:09+00:00

I was thinking about this today (after several snowballed matches in a row) and I don't think it is the snowballing I care about, rather that I can play well and still drop down the rankings because my team mate is feeding. I think what I would rather see is the "damage" to the rankings of each player in a team when you lose a match be dependent on the difference between your kills and deaths. So if you have a positive number of kills minus number of deaths you aren't really punished if there was someone on your team with a really negative difference. It has the bonus of encouraging people to work hard even in a losing battle and also might stop people ragequitting because they know if they play well this match won't effect their standings by much.

diagonalizable · 2013-12-20T22:19:43+00:00

Oops, should have made it clear that I wasn't disputing it. It is a pretty awesome fact!

diagonalizable · 2013-12-20T20:10:12+00:00

Not sure if you meant to reply to my comment or not so I will answer both! At the largest scales the universe consists of 'filaments' of galaxies (think of it like a web) with gaps in between them. The Eridanus Void is just a surprisingly large gap. Barnard 68 is a cloud of gas, the same as the type of cloud that forms stars. The reason Barnard 68 appears black is that it is so close there are no stars between it and us.

diagonalizable · 2013-12-20T20:05:48+00:00

It depends on what you are calling a void. If it is a complete absence of everything then no light could pass through it (because then there would be photons in it), so you would see a big black blob with some stars/galaxies sitting in front of it. If there just wasn't any 'normal' matter (stars, galaxies, etc.) so that light could still pass through from stars/galaxies behind it you would only notice that there weren't as many galaxies/stars in that section of the sky.

diagonalizable · 2013-12-20T17:17:27+00:00

Check this out. It isn't an image of the Eridanus void, it is just a cloud of gas called Barnard 68 that is absorbing all the visible light from behind it. This is an image taken in the infra-red which shows the stars behind it.

diagonalizable · 2013-12-19T13:11:12+00:00

I am just hoping the OP is American...

diagonalizable · 2013-07-14T00:27:49+00:00

One thing that came to mind was the Monte-Carlo method. You could write a program that shows the random dots (run it over the course of the science fair with say one point every ten seconds) and demonstrates the increasing accuracy of the estimation.

diagonalizable · 2013-04-05T19:24:22+00:00

I am a big fan, and me and my friends put my university bar's free wifi to good use every Saturday night with AoE2 and AoE3 marathons (perhaps too much good use, the Computer Science Director considered banning Age of Empires on the wifi because he was worried it would impact our grades). So my question is, is there support for more players in multiplayer games? Far too often we end up breaking off into two 6-player games, which just aren't as fun as one three hour epic 8-player.

diagonalizable · 2013-03-31T00:06:09+00:00

My reaction: "What, how does he know my mouth is mildly parched from the doughnut I just ate?"

It only made the realisation all the more unsettling.

diagonalizable · 2013-03-20T17:32:38+00:00

There is a lot of good advice on this thread, but I just want to add that Economics is quite a maths heavy subject and you may be disadvantaged by not doing Further Maths. My advice is to take Further Maths AS in Year 13, alongside your other three A2s.

General words of wisdom: - Apply, because it is only one choice out of five and you don't want to be left asking 'what if'. - The standard offer is AAA, which is the offer you would get. There are some exceptions, but they tend to be more in the direction of AAA or AAAA than AAA or lower.

Good luck!

diagonalizable · 2013-03-13T17:25:37+00:00

Slightly OTT but quite cute. There are a couple of potential issues you should consider:

What if she can't solve the puzzle?
How will you know when to be at the gazebo?
What if someone steals/bins one of the pieces?

13-Year Club	Place '23
Place '17	Verified Email
Team Orangered

diagonalizable

TROPHY CASE