6
$\begingroup$

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) 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)

$\endgroup$
  • $\begingroup$ feel free to ask for more details $\endgroup$ – Artem Bernatskyi Dec 17 '18 at 13:53
  • 1
    $\begingroup$ Please edit to provide an explicit cost/reward function. This should tell us the value to you (in points) of watching a video that lasts $t$ seconds (that may or may not depend on $t$). I assume you know the length of the video before you decide to watch. Then you want to maximize your return in points per time unit. I would start by fitting a gamma distribution to the data on video length. $\endgroup$ – Ethan Bolker Dec 17 '18 at 14:41
  • $\begingroup$ @EthanBolker I am sorry, if i've understood you correctly, I receive reward for the video if i view it completely. Yes, i know video length prior to watching. $\endgroup$ – Artem Bernatskyi Dec 17 '18 at 15:05
  • $\begingroup$ Do you get the same number of points for every video? $\endgroup$ – Ross Millikan Dec 17 '18 at 15:06
  • $\begingroup$ @RossMillikan yes, we get the same points for every video that we have watched till the end $\endgroup$ – Artem Bernatskyi Dec 17 '18 at 15:07
4
+100
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thx, but what will be the result value for large limit of time (for that case that you've said it'll be easy to calculate) ? $\endgroup$ – Artem Bernatskyi Dec 22 '18 at 23:39
  • $\begingroup$ @ArtemBernatskyi If you watch a video, do you need to wait 5s to get the next one, or is the 5s delay only for the case you choose to skip it? $\endgroup$ – Todor Markov Dec 23 '18 at 18:24
  • $\begingroup$ For both cases i need to wait 5s. So if i skip video i need to watch 5s and when I'm waiting for the next video also. $\endgroup$ – Artem Bernatskyi Dec 23 '18 at 18:43
  • 1
    $\begingroup$ @ArtemBernatskyi I'm getting 49 seconds for the optimal threshold. Updated answer with it. This is the same values as shown by LinAlg's simulation. $\endgroup$ – Todor Markov Dec 23 '18 at 19:04
1
$\begingroup$

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:

enter image description here

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): enter image description here

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()
$\endgroup$
  • $\begingroup$ Why one week is 3600*36 ? Because it is 3600*24*7 $\endgroup$ – Artem Bernatskyi Dec 18 '18 at 14:28
  • $\begingroup$ @ArtemBernatskyi I assumed you do not want to do this for more than 36 hours a week. The $x$-location of the peak does not change if you work longer, although the $y$-value does. $\endgroup$ – LinAlg Dec 18 '18 at 15:12
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Ok, you have shown how to calculate median and mean, but this doesn't explain how to find an Optimal length of video clips which we need to watch in order to get maximum number of points. Aka to skip those videos which are long and watch those videos with an optimal length. $\endgroup$ – Artem Bernatskyi Dec 17 '18 at 18:54
  • $\begingroup$ @LinAlg it's not me, you can check it by my reputation change $\endgroup$ – Artem Bernatskyi Dec 17 '18 at 20:19
  • 1
    $\begingroup$ @ArtemBernatskyi sorry about that. I was saying I did not understand why this question was downvoted, so I put it back at +0. $\endgroup$ – LinAlg Dec 17 '18 at 20:27
0
$\begingroup$

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$.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Ultimately, whether the five second wait is only for videos you skip or for all, doesn't change the problem. You can reduce one to the other by adding/subtracting 5 to all video lengths. $\endgroup$ – Todor Markov Dec 18 '18 at 19:44

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.