7
$\begingroup$

Important Pre-Requisite Knowledge

On the image board 4chan, every time you post your post gets a 9 digit post ID. An example of this post ID would be $586794945$. A Quad is a post ID which ends with 4 consecutive identical numbers. For example 586794444 and 586796666 is a Quad. A trip is a post ID which ends with 3 identical numbers. For example 586794333 or 586794555 are both trips.

My Question

a) What is the probability of receiving a trips post ID

b) What is the probability of receiving a quads post ID

c) How many posts are necessary (assuming each new post receives a new ID) for 3 trips to show up

These are questions I came up with while on the site and I'm looking to see if my answer is correct. I'm pretty sure I know part a,b. I'm having difficulty with part c though, looking for a way to solve that.

My Work

Part A

Our sample space is all possible posting IDs. Therefore $|S| = 10^{9}$

To calculate our $|E|$ we need to know all possible trips. We first pick our three ending letters (10 ways to do this). Then the $4^{th}$ to last digit must be different from the last 3 so we select it in 9 ways. We then have $10^5$ ways to select the starting 5 digits. Therefore, we have $10*9*10^5$ ways to select trips. Therefore, the probability of selecting a trips is $\frac{10*9*10^5}{10^{9}}$ = .009

Part B

Similar process to part A. We have the same sample space. 10 ways to select the quads. 9 ways to select the $5^{th}$ to last digit, and finally $10^4$ ways to select the remaining 4 digits. Therefore probability of $\frac{10*9*10^4}{10^9}$ = .0009

Part C

Don't really know where to begin. I'm thinking maybe there are $10*9*10^5$ possible trips and $10^9$ total IDs so maybe we have to post $10*9*10^5 - 10^9$ to ensure we get a trips.

$\endgroup$
  • $\begingroup$ Can the first digit be $0$? $\endgroup$ – voldemort Dec 21 '14 at 22:10
  • $\begingroup$ @voldemort yes it can be. $\endgroup$ – Dunka Dec 21 '14 at 22:11
  • 2
    $\begingroup$ Then your solution is correct. $\endgroup$ – voldemort Dec 21 '14 at 22:14
  • $\begingroup$ Check 'em dubs ;) $\endgroup$ – Hasan Saad Jun 11 '15 at 21:37
2
$\begingroup$

a, b)

Be $X$ a random variable that counts the repeating numbers from the right. Take into account that when a post is a Quads is not a Trips.

$\begin{align} P(X=3)&=1\times\frac{1}{10}\times\frac{1}{10}\times\frac{9}{10}\\ &=0.9\%\\ P(X=4)&=1\times\frac{1}{10}\times\frac{1}{10}\times\frac{1}{10}\times\frac{9}{10}\\ &=0.09\% \end{align}$

That means, you choose the rightests number, then have $\frac{1}{10}$ the next one is the same, and so on, until the fourth or the fifth, which you want it to be different.

c)

Take into account the following. If you have a Trips ($xxxxxx111$), the next one will come when you sum $111$, being $xxxxxx222$. There are two exceptions, though. First is when you get through the Quads. Where you'll have to sum $222$ from one to the next one, since one doesn't count. The other is when you are in $xxxxxx999$, where you get the next Trips on your next post, $xxxxxy000$.

Anyway, the mean for that is easier calculated using the probability we just found. If we'd select random number of posts $t$, by mean we'd find $tP(X=3)$ Trips. Let's find for what number of posts, the expected number of Trips is $1$.

$\begin{align} 1&=tP(X=3)\\ &=0.0009t\\ t&=111.1111 \end{align}$

By mean, every $111.1111$ posts you'll have a Trips. For Quads it's equivalent.

$\begin{align} 1&=t'P(X=4)\\ &=0.00009t'\\ t&=1111.111 \end{align}$

By mean, every $1111.111$ posts you'll have a Quads.

$\endgroup$
1
$\begingroup$

A simpler way to answer a and b is to just ignore the rest of the string and consider the final n+1 digits (assuming post numbers in a given thread are effectively random (and thus independent) which for predictive purposes while looking in one thread they are). A. Calling last digits q, r, s, t we have R =/= q: .9 S=q: .1 T = q&s: .1 Multiply ??? Profit B is similar C. Has no finite answer. For any number N there is SOME calculable probability that trips does not occur. Thus for no N can the odds of trips (1- p(no trips)) can never be 1. Analagously, how many times do you have to flip a coin to GUARANTEE heads? Pro tip: you can't.

$\endgroup$
  • $\begingroup$ Oh, I should add, my answer that trips is indeterminate is based on the fact that the supply of Ids is inexhaustible. 4chan either will recycle or add a digit. Given that there are multiple threads, there is no way to ensure all combos appear in any given one. You seem to be assuming that numbers are picked randomly with no repeats within a thread and are confined to the set of 9-digit numbers. Under such assumptions, your calculation for (c) is correct, but I don't think that is a good model for 4chan. $\endgroup$ – user247369 Jun 11 '15 at 4:10
  • $\begingroup$ Welcome to math.SE! Before writing, you should learn how to use the text editor of this site. Also, use the "edit" button to add details to your post, not comments. $\endgroup$ – user228113 Jun 11 '15 at 6:06
1
$\begingroup$

For part C, note that Albert is calculating the expected amount of posts before we see trips. This does not guarantee that trips will show up in that number of posts.

If we want to find the necessary number of posts until we're guaranteed for 3 trips to show up, we can use the Pigeonhole Principle.

Since we're assuming every post ID is unique, and we've discovered there to be $ 10*9*10^5 $ post ids that are trips, then there are $ 10^9 - 9000000 = 991000000$ post ids that are not trips. It's possible (though highly unlikely) that all these non-trip post IDs are attributed before any trips show up. But afterwards, every post that shows up will be trips. Thus $ 991000003 $ posts are necessary to guarantee 3 trips have happened.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.