Find optimal number of videoclips to watch (depending on length) to get Maximum points.

Question

Problem: How to find optimal number of video clips to watch (depending on length) to get Maximum points.

Description: I request video clip, then I have two options: to watch it (spend time) and receive points or to skip it and not to receive points (not to spend time).
Timeout between new video is 5s.

(This is statistical histogram where (Y-axis is number of videos, X-axis is video length)

Limitations && Assumptions:
- We don't know videos in advance (that's why I've gathered data to build a statistical histogram to know their probabilities.)
- When we skip video clip we don't lose points.
- We do know video length before watching it.
- We receive points for watching video completely.
- We receive the same amount of points for every video.

So basically we need to skip those videos which are long and watch those videos with an optimal length. (aka to find how to maximize points per unit time)

Answer 1

I will assume the supply of videos is unlimited and each video is worth 1 point (limited supply would make the problem significantly harder).

We want to maximize the points earned per unit time. It is easier to (equivalently) minimize the time needed to earn a point. Since this is random, we will minimize the expected time needed to earn a point. Our strategy would be to watch all videos that are no longer than some maximum time $m$.

So, if we know $m$, what is the time needed to earn a point? First, we have to wait 5s for each video that we get longer than $m$. Then, we need to watch the video that we get that is shorter than $m$.

The probability to get a long video (and thus skip it) can be calculated from the histogram. Lets call that $p_m$. Then, the number of videos we will skip follows a negative binomial distribution with $r=1$ and probability $p_m$. The expected number of skips is thus $\frac{p_m}{1-p_m}$.

Similarly, from the histogram we can compute the expected video length given it is at most $m$.

Thus, if $L$ denoted video length, our time spent per point is $T(m) = 5\sec\frac{p_m}{1-p_m} + \mathbb{E}[L | L \leq m]$.

Now we want to minimize $T(m)$. We can compute it using our histogram if given $m$. While we don't have a closed form expression, we only have a single parameter, $m$, that takes values between 0 and 1000, so it shouldn't be hard to optimize, we can use a simple grid search to find the best $m$.

Extra note: There could be an alternative formulation, where instead of maximizing the points earned per unit time, we have a hard time limit for watching videos and want to maximize the total score. If the time limit is large, the above is a good approximation. But for a small time limit, the problem becomes significantly harder. In that case, the optimal threshold might change with time remaining. We can try to tackle that case by defining two functions $S(t)$, which gives the optimal expected score if we have time $t$, and $m(t)$, the video length threshold as a function of time. Then we have, $S(t) = S(t-5)\mathbb{P}[L>m(t)] + \mathbb{E}[S(t-L) + 1|L\leq m(t)]\mathbb{P}[L\leq m(t)]$. We can then use dynamic programming to find $m(t)$ and $S(t)$.

Addendum: Note that the above assumes that the 5s wait happens only if we skip a video without watching it. Since in fact the 5s delay happens even after we watc ha video, I added 5s to the length of each video.

The above can easily be implemented in python:

times = open('times').readlines()
times = [int(x)+5 for x in times]
def pm(m): return len([x for x in times if x > m]) / len(times) # this computes p_m
def em(m): return np.mean([x for x in times if x <= m]) # This is E[l|l<=m]
def t(m): return 5 * pm(m) / (1 - pm(m)) + em(m)
min(range(min(times), max(times)), key = lambda x:t(x))

The minimum $T$ turns out to be at 54 seconds. Note that this is after adding 5s to the length that I mentioned above, so the answer is 49 seconds.

Note that while 49 seconds technically gives the optimum, all cutoff values between 48 and 53 have pretty much the same scores.

Answer 2

Okay, here's the data, except sorted. Now, we want to maximise points, yes. And we need to watch a video to get, say, 1 point. (You said a constant number of points, I say that since this is the only method and any amount of points is a multiple of however many points this method gives.) So, we've got all of these videos, with an average length of... Okay, so there are 2905 list elements. Subtract 1, divide by 2, add 1, that's the 1453rd element, which is equal to 49. The median is 49. And from a simple program I wrote, the sum of all of the elements is 252464. Nice, two concatenated palindromes, now divide by 2905 and we have a mean average of 86.9! Now, add 5 seconds (the time between videos) to both of these, and we have 54 and 91.9 for the median and mean. Now, you want to skip videos which give you a low number of points, and because we don't need to learn how numbers compare to each other, just to the average, we can toss the median out of the window. So... Wait, this is hard.

Okay, now I've used a spreadsheet, and found all sorts of interesting pieces of metadata, but to no avail. All I can say for now is that anything with less than 87 seconds is probably worth 'watching', and if it's in the bottom 25th percentiles (ie. 40 or less), then go for it. And this bounty of your hard-earned reputation will erase all guilt.

Answer 3

I have written a small simulation tool in Python (code added at the end of this post). It computes the number of videos you can see in one week:

Blue is the mean, red is a measure of the simulation error. Let's zoom in around the peak (by letting x run from 45 to 55, and increasing the number of replications):

This suggests you should watch videos of at most 49 seconds, and skip videos of 50 seconds or longer. This conclusion depends on the input data.

data = """31
31
[removed for brevity]
897"""

data = [int(duration) for duration in data.split("\n")]

import random
def get_random_video():
    return random.choice(data)

def average(x):
    return sum(x) / float(len(x))

def std(x):
    avg = average(x)
    avgsq = average([i*i for i in x])
    return (avgsq - avg*avg) / float(len(x))

simulation_duration = 3600*36 # one week
replications = 10
x = range(31,897)
y = []
y_std = []

for threshold in x:
    points_threshold = []
    for replication in range(replications):
        time = 0
        points = 0
        num_videos = 0
        while time < simulation_duration and num_videos < 100000:
            video = get_random_video()
            if video<=threshold:
                points += 1
                time += video
            time += 5
            num_videos += 1
        points_threshold.append(points)
    y.append( average(points_threshold) )
    y_std.append( std(points_threshold) )

from math import sqrt
y_err_1 = [x[0] - 2*x[1]/sqrt(replications) for x in zip(y,y_std)]
y_err_2 = [x[0] + 2*x[1]/sqrt(replications) for x in zip(y,y_std)]

import matplotlib.pyplot as plt
plt.plot(x,y,'b')
plt.plot(x,y_err_1,'r')
plt.plot(x,y_err_2,'r')
plt.xlabel('watch video if shorter than (s)')
plt.ylabel('expected videos seen per week')
plt.show()

Answer 4

Your strategy clearly has to be to set a length $L$, accept all videos shorter than that and reject all longer videos. Given a proposed $L$ you can compute the average length you will accept, $M$ and the probability $p$ you will reject the next one. Your average time waiting is $5(p+p^2+p^3+\ldots)=\frac{5p}{(1-p)}$ because you wait $5$ seconds with probability $p$, another $5$ seconds with probability $p^2,$ and so on, so your average time to finish a video is $M+\frac{5p}{(1-p)}$

As you accept longer videos, $M$ will increase but $p$ will decrease. You are looking to set $L$ to balance this. As an example, suppose (I am making up the numbers) that if you set $L=100$ the average video you accept is $60$ seconds and you accept $40\%$ of the videos. Your average time to finish one is then $60+\frac {5\cdot 0.4}{1-0.4}\approx 63.333$ seconds. If you increase $L$ to $110$ and you now accept $62\%$ of the videos, the average length you watch is now $\frac {20\cdot 60+105}{21}\approx 62.143$ and the waiting time decreases to $\frac {5\cdot 0.38}{1-0.38}\approx 3.064$. Clearly this is a bad trade and you should look at decreasing $L$ below $100$.

Answer 5

As I understand it there is a 5 second wait for both videos you watch and those you don't watch. Some posters seem to think differently. Using the data as given, a simple What If table in Excel suggested only watching videos of less then 43.

I tried fitting distributions to the histogram but nothing I tried worked too well. But lets say the distribution of video lengths could be approximated by a continuous probability distribution $p(l)$. Then given a cut-off $L$ the number of clips watched would go like $\int_0^L p(l) dl$ and the total time watching them would go like $5 +\int_0^L l p(l) dl$. Create the watch rate by forming the ratio of the two. Differentiating w.r.t. $L$ to find the maximum gives the following equation ($5 +\int_0^L l p(l) dl)=L \int_0^L p(l) dl$. For most feasible distributions this will not have a closed form solution so you are better off sticking to the spreadsheet.