I think this maybe misses the mark a bit on purity and impurity.

---

Your first function is indeed impure but not quite for the reasons you say. Let's remove the call to Math.random() and consider the following:

const increment = (num) => {
  num += 1
  return num
}

Your gut reaction might be to determine this function as impure because there is mutability; the value of num changed before it was returned. "This is a side effect" you might say.

But let's take a moment to consider what a side effect actually is:

In computer science, an operation, function or expression is said to have a side effect if it modifies some state variable value(s) outside its local environment, that is to say has an observable effect besides returning a value (the main effect) to the invoker of the operation.

With this knowledge, we can look at our increment function and determine it has no observable side effects. What happens inside the function has no bearing on the result of our program. Calling increment(1) will always produce 2 and from the perspective of the caller, nothing else happens.

---

On the other hand if we bring back the Math.random() call to give us:

const increment = (num) => {
  num += 1
  return num * Math.random()
}

Now this is impure. That randomness is an observable side effect of running the function. Every time we run increment(1) we get something different.

---

Let's turn our attention to a property of impure functions you mention:

their return value doesn't solely depend on the arguments

This is only partially true. If we take our first function and add a global variable:

const x = 1
const increment = (num) => {
  num += x
  return num
}

then by your definition, this function would be impure. x is known as a free variable, and as long as free variables can't change, then we can say a function that uses them can still be pure providing it has no side effects too.

There are some gotchas with those though, particular because of javascript's semantics.

const obj = { x: 10 }
const increment = (num) => {
  num += obj.x
  return num
}

We can't reasonably assert that this version of implement is pure, because obj.x can change.

---

Hope this maybe clears a few bits up!