On ne manque pas de problèmes! C'est ça qui est chouette en interdisciplinaire. Je privilégie ceux qui me plaisent, bien sûr, mais c'est un mélange de plaisir / abordabilité / "rentabilité" (étant en postdoc je n'ai pas le luxe de traiter des sujets trop obscurs peu valorisables dans un dossier)

Il se trouve que je fais des maths appliquées (à la bioinformatique, en l'occurrence). Je cherche la petite bête, le petit coin où il faudrait un peu de maths pour aider les collègues, et après je me lance. De fait, parfois ce que je trouve aide les collègues, mais parfois non.

Peu m'importe, au final, si ça atteint, ou non, des gens, tant que je n'ai pas à rougir de ce que je propose !

Mon idéal à moi, c'est de proposer un problème (à ma portée), de l'attaquer honnêtement et sincèrement, de proposer une solution aussi complète que possible, qui fait le tour du sujet (sans saucissonnage) et, lorsque je n'ai pas à rougir de ce que j'ai à disposition, alors je l'envoie.

Dans l'article, une application c'est la numérotation des permutations à n éléments : tu peux trouver le rang d'une permutation en calculant sa valeur en num. factorielle, et vice-versa. Pour les gens (comme moi) qui aiment l'énumération c'est super cool, en vrai.

And now, for the 25th post, i.e. CHRISTMAS MORNING, the promised thread by Antoine :
bsky.app/profile/npma...

This kind of situation appear elsewhere in the simulations, but it happens randomly after Z2, so it is averaged over all 10^6 simulations and the effect is smoothed. That's why I was speaking of a border effect, as Y1/Z1 is very special by being the only window without prior dependencies

Yeah so basically Y1 is always a rescan, and Y2* (the second selected position) always follows a rescan, so Z2 = Y2* - Y1 is always the gap between a rescan and its successor.

There is some bias as the next minimizer after a rescan is more likely to be far as it follows the min over a whole window

And yes, the result is true when taking the limit to infinity. In the proof of Theorem 1, we establish the following
--- where E[tau_M] / (M-k+1) is the expected specific density of a random sequence of length M (and then M->infty)

You can derive actually an interval for a finite sequence from this

You are right in that eps_i is not *technically* a random variable. And yes, we want the average eps_i to be 0.

We chose to consider the eps_i as some realizations of an underlying random variable eps of mean 0, but it is only for the proof and not a big deal actually.

But as you can see, numerically with Monte Carlo, we obtain that E[Z_i] are somehow around (w+1)/2, so all good.

(and the values E[Z_i] - (w+1)/2 are, equivalently, somewhat around 0)

They're not, actually ! For instance, this is what we (formally) obtain for Z1 and Z2, with random minimizers. For w=10, E[Z1] = 5.5 whereas E[Z2] = 5.87 (there is a good reason for this, I can explain more if you're curious, but basically it is a border effect).

Where the Z_i's i.i.d then it would simply be E[Z1] but we didnt want to assume independence nor identical distribution, as to be as general as possible (also they are not iid in real life)

There are several way to define it actually, but you can think of it as E[E[Z_i]] where Z_i is the i-th gap. So, the average of the average gap.

I would also argue that n / # samples ≠ avg gap.

Take a sequence with n=6, and sample positions 1 and 3.

You get 3 ≠ ((1-0) + (3-1))/2 = 1.5

You need to account for the remaining bits after the last sample. And this implies going to infinity!

The only proper formal definition of density I found (the one I just gave) was in the GreedyMini paper. Other references, as far as I know, defines it informally, which is usually enough, but not when you want to claim a mathematical truth !

Well, usually when things seems trivial, one must be cautious. Since the density is defined as the limit of expected specific density when S tends to infinity, maybe there could have been a trick with the limit. Better safe than sorry, I would say