Problem 323

[Eriks]

Hi,

I don't understand what I should look for in problem 323.

The question is : find $N$ such that all the bits are set to 1 for $i \geq N$.

What I don't understand is :
1. You can NEVER ensure that all the bits are set to 1 since the input is random. Instead, you can get a probability of having this property. In that case, the question would be "what is the min $N$ so that the probability of having all bits set to one is greater than $\lambda$".
2. Since we are looking for an integer index $N$, why do I need digits after the decimal points ?

Am I wrong ? Thanks for helping !

[Hippunky]

You're after the expected value of N - see http://en.wikipedia.org/wiki/Expected_value. The expected value won't be an integer value - which is why you'll need to include figures after the decimal point.

[Eriks]

OK !
English is not my first language and I understood "expected" literally. Thanks for the answer !

[TexasRebel]

If the sequence $y_i$ is truly random isn't there a chance, albeit very slim, that any single bit remains 0 for $N=\infty$?

reaching $x_i = 2^{32}-1$ is not an eventuality unless each 32-bit integer can only be used once.

[RobertStanforth]

Yes, but that happens with probability 0, so that case will not affect the expected value of $N$.

If the sequence $y_i$ is truly random isn't there a chance, albeit very slim, that any single bit remains 0 for $N=\infty$?

reaching $x_i = 2^{32}-1$ is not an eventuality unless each 32-bit integer can only be used once.

[karabonev]

I'm having trouble understanding this problem.

I got the probabilities of a specific outcome calculated but I don't get the concept of "expected value of N".

Can someone provide an example using 3-bit integers?

EDIT:
If my understanding is correct, the expected value of N for 3-bit integers is 2.6678571429

[neverforget]

For this problem, you'll want the definition for expected value of Random variables with countably many outcomes on the Wikipedia page.

An example is not given probably because the question is already clear enough without one, and also because it may give away too much? That said, your answer for 3 bits can be readily contradicted by a naive Monte Carlo simulation.

[karabonev]

I don't see how giving an example for another sequence would give away too much.

Anyway, I wasn't aware of the Monte Carlo method. Using it lead to finding a mistake in my calculations and eventually the right answer.

Thank you, neverforget.

[SAG145]

Can someone please tell me what the first three digits after the point of the solution are?
Also if someone can look at my code (Python) that would be wonderful.

Thanks.

[neverforget]

Can someone please tell me what the first three digits after the point of the solution are?
Also if someone can look at my code (Python) that would be wonderful.

Thanks.

If you just want 3 sig figs, you should just ask Monte Carlo as he can easily help you with that.